What is causing this function to work for some amount of points, but not more?

Here's what I'm doing. I calculate a bunch of xy points scattered within some range, and then I have some functions that calculate the "boundary" of those points. If you're familiar with this area, it's not a convex hull, it's concave, so there's no unique solution until you tell it how much you want it to "squeeze" into the points (just a parameter I choose).

Here are the functions I'm using (I didn't make them; I don't understand how they work more than superficially):

GetBoundaryMesh[points_, alphaparameter_] := Module[{ashape, bmesh},
Needs["NDSolveFEM"];
ashape = alphaShapes2DC[points, alphaparameter];
bmesh = NDSolveFEMToBoundaryMesh@ashape;
Return@MeshPrimitives[MeshRegion@bmesh, 1];
]

Compile[{{v, _Real, 2}},
With[{a = Norm[v[[1]] - v[[2]]], b = Norm[v[[1]] - v[[3]]],
c = Norm[v[[2]] - v[[3]]]}, (a b c)/
Sqrt[(a + b + c) (b + c - a) (c + a - b) (a + b - c)]],
RuntimeOptions -> "Speed", RuntimeAttributes -> {Listable},
Parallelization -> True];

alphaShapes2DC[points_, crit_] :=
Module[{alphacriteria, del = Quiet@DelaunayMesh@points, tris,
getExternalFaces[facets_] := MeshRegion[points, facets];
If[Head[del] === EmptyRegion, del, tris = MeshCells[del, 2];
tricoords = MeshPrimitives[del, 2][[All, 1]];


Here's an example of it working correctly. There are 441 points here:

pts = {{0.31320000000000003, 0.33030000000000004}, {0.3178,
0.3346}, {0.3239, 0.3397}, {0.3309,
0.34450000000000003}, {0.3375, 0.3471}, {0.3411,
0.3453}, {0.3385, 0.338}, {0.3275, 0.3257}, {0.3093,
0.3114}, {0.28900000000000003, 0.29960000000000003}, {0.2733,
0.2934}, {0.26580000000000004, 0.2931}, {0.2656,
0.29660000000000003}, {0.26980000000000004, 0.3018}, {0.276,
0.3073}, {0.2826, 0.3123}, {0.2888,
0.31670000000000004}, {0.29450000000000004, 0.3206}, {0.2994,
0.32380000000000003}, {0.3037, 0.3266}, {0.3075,
0.3289}, {0.31420000000000003, 0.3311}, {0.34850000000000003,
0.36050000000000004}, {0.38380000000000003,
0.3759}, {0.38880000000000003, 0.3552}, {0.3257,
0.2954}, {0.24750000000000003, 0.25520000000000004}, {0.2281,
0.2607}, {0.24070000000000003, 0.2787}, {0.2577,
0.2937}, {0.27190000000000003, 0.3045}, {0.2828,
0.3121}, {0.29100000000000004, 0.31770000000000004}, {0.2974,
0.3219}, {0.3024, 0.32530000000000003}, {0.3065,
0.3281}, {0.31010000000000004, 0.3305}, {0.31320000000000003,
0.3326}, {0.316, 0.33440000000000003}, {0.3185,
0.336}, {0.32080000000000003, 0.3372}, {0.3229,
0.3382}, {0.31620000000000004, 0.33280000000000004}, {0.4194,
0.4033}, {0.5552, 0.4091}, {0.2089,
0.1464}, {0.19310000000000002, 0.2359}, {0.2419,
0.2826}, {0.26880000000000004, 0.30260000000000004}, {0.2841,
0.313}, {0.2937, 0.31920000000000004}, {0.30010000000000003,
0.32330000000000003}, {0.3047, 0.3262}, {0.30820000000000003,
0.3286}, {0.3111, 0.3306}, {0.3136,
0.33240000000000003}, {0.3159, 0.3341}, {0.31820000000000004,
0.3357}, {0.3204, 0.3373}, {0.3225, 0.3387}, {0.3247,
0.33990000000000004}, {0.3267, 0.3408}, {0.3285,
0.34140000000000004}, {0.31520000000000004, 0.3302}, {0.3831,
0.35100000000000003}, {0.2886, 0.277}, {0.25320000000000004,
0.2853}, {0.2747, 0.306}, {0.2893, 0.3164}, {0.298,
0.3219}, {0.3034, 0.3252}, {0.307,
0.3274}, {0.30970000000000003, 0.3291}, {0.3118,
0.3305}, {0.31370000000000003, 0.33190000000000003}, {0.3155,
0.33330000000000004}, {0.3173, 0.3347}, {0.3191,
0.3362}, {0.3211, 0.3377}, {0.32330000000000003,
0.3392}, {0.3255, 0.3407}, {0.3277,
0.34190000000000004}, {0.32980000000000004, 0.3428}, {0.3317,
0.3432}, {0.30770000000000003, 0.32370000000000004}, {0.2872,
0.29300000000000004}, {0.2743, 0.2908}, {0.2831,
0.3039}, {0.29300000000000004, 0.31370000000000003}, {0.2997,
0.3195}, {0.30410000000000004, 0.323}, {0.307,
0.3252}, {0.30910000000000004, 0.3269}, {0.3108,
0.32830000000000004}, {0.3124, 0.3296}, {0.314,
0.331}, {0.3156, 0.3325}, {0.3175, 0.3342}, {0.3196,
0.3361}, {0.3219, 0.338}, {0.3244, 0.3401}, {0.3271,
0.342}, {0.3299, 0.3436}, {0.3325, 0.3447}, {0.3347,
0.3451}, {0.3054, 0.3244}, {0.2782,
0.2944}, {0.27540000000000003, 0.2903}, {0.2812,
0.2954}, {0.2876, 0.3015}, {0.2928,
0.30670000000000003}, {0.2967, 0.31070000000000003}, {0.2997,
0.3138}, {0.3022, 0.3165}, {0.3045,
0.3191}, {0.30670000000000003, 0.3216}, {0.309,
0.3244}, {0.3116, 0.3275}, {0.3146, 0.331}, {0.3181,
0.33490000000000003}, {0.3219, 0.33890000000000003}, {0.3261,
0.343}, {0.3305, 0.3467}, {0.33480000000000004,
0.3496}, {0.3386, 0.3514}, {0.3417,
0.3517}, {0.30810000000000004, 0.3274}, {0.2867,
0.3089}, {0.2805, 0.3014}, {0.2806,
0.3}, {0.28300000000000003, 0.3018}, {0.2863,
0.3054}, {0.2901, 0.31020000000000003}, {0.2943,
0.316}, {0.2989, 0.32270000000000004}, {0.304,
0.33030000000000004}, {0.30960000000000004, 0.3385}, {0.3158,
0.3472}, {0.3225, 0.3559}, {0.3295, 0.3639}, {0.3366,
0.3708}, {0.34340000000000004,
0.37570000000000003}, {0.34950000000000003, 0.3783}, {0.3546,
0.378}, {0.3582, 0.3749}, {0.36010000000000003,
0.36920000000000003}, {0.3598, 0.3613}, {0.3113,
0.33030000000000004}, {0.30820000000000003, 0.3408}, {0.3116,
0.3553}, {0.3183, 0.3709}, {0.32630000000000003,
0.3855}, {0.3345, 0.3976}, {0.34240000000000004,
0.4067}, {0.34940000000000004, 0.4123}, {0.3556,
0.4146}, {0.3608, 0.4138}, {0.36510000000000004,
0.4103}, {0.36860000000000004, 0.4046}, {0.3713,
0.397}, {0.37320000000000003, 0.3879}, {0.3743,
0.37770000000000004}, {0.3743, 0.3667}, {0.37320000000000003,
0.3553}, {0.3705, 0.3438}, {0.3662,
0.3326}, {0.36010000000000003, 0.32220000000000004}, {0.3519,
0.313}, {0.3149, 0.33380000000000004}, {0.3548,
0.3986}, {0.391, 0.44480000000000003}, {0.4143,
0.4617}, {0.4249, 0.45580000000000004}, {0.4268,
0.4384}, {0.42410000000000003, 0.4172}, {0.4192,
0.39630000000000004}, {0.4131, 0.3771}, {0.40640000000000004,
0.36010000000000003}, {0.39930000000000004,
0.34540000000000004}, {0.3917, 0.33280000000000004}, {0.3835,
0.3221}, {0.37460000000000004, 0.3133}, {0.3649,
0.3064}, {0.3543, 0.3012}, {0.343, 0.2979}, {0.3311,
0.2962}, {0.3189, 0.2963}, {0.3068,
0.2979}, {0.29560000000000003, 0.3008}, {0.3195,
0.33840000000000003}, {0.42900000000000005, 0.4531}, {0.4974,
0.47190000000000004}, {0.511, 0.431}, {0.49310000000000004,
0.3808}, {0.4631, 0.3407}, {0.4305,
0.31370000000000003}, {0.3995, 0.2973}, {0.3718,
0.2886}, {0.3477, 0.28500000000000003}, {0.32730000000000004,
0.2849}, {0.3105, 0.2871}, {0.2969,
0.2908}, {0.28650000000000003, 0.2953}, {0.27890000000000004,
0.3005}, {0.27390000000000003, 0.3059}, {0.27140000000000003,
0.3113}, {0.271, 0.31670000000000004}, {0.2723,
0.32170000000000004}, {0.2752, 0.3264}, {0.2793,
0.3304}, {0.32230000000000003,
0.33740000000000003}, {0.46340000000000003, 0.4056}, {0.524,
0.3577}, {0.4824, 0.2838}, {0.3971,
0.2439}, {0.32430000000000003, 0.2388}, {0.2798,
0.2497}, {0.2579, 0.26430000000000003}, {0.25,
0.2777}, {0.24960000000000002, 0.2887}, {0.25320000000000004,
0.29760000000000003}, {0.2585, 0.3048}, {0.2645,
0.31070000000000003}, {0.27080000000000004, 0.3158}, {0.277,
0.3204}, {0.28300000000000003, 0.3245}, {0.2889,
0.32830000000000004}, {0.2947, 0.33180000000000004}, {0.3002,
0.33490000000000003}, {0.3055, 0.3376}, {0.3105,
0.3398}, {0.3184, 0.32680000000000003}, {0.374,
0.2702}, {0.3296, 0.18130000000000002}, {0.2379,
0.1565}, {0.1967, 0.1922}, {0.2003, 0.2328}, {0.2175,
0.26130000000000003}, {0.2351, 0.2798}, {0.2499,
0.2921}, {0.2617, 0.3007}, {0.2712,
0.30710000000000004}, {0.279, 0.3123}, {0.2856,
0.3168}, {0.29150000000000004, 0.3209}, {0.2968,
0.3249}, {0.3019, 0.32880000000000004}, {0.3068,
0.3326}, {0.3116, 0.3362}, {0.31620000000000004,
0.33940000000000003}, {0.32070000000000004, 0.3421}, {0.3247,
0.3441}, {0.31, 0.319}, {0.25880000000000003,
0.2124}, {0.189, 0.1651}, {0.1733, 0.183}, {0.1928,
0.21710000000000002}, {0.2175, 0.2447}, {0.2379,
0.2641}, {0.2533, 0.27790000000000004}, {0.265,
0.2883}, {0.2741, 0.29660000000000003}, {0.2816,
0.3037}, {0.2881, 0.3103}, {0.29400000000000004,
0.3166}, {0.29960000000000003,
0.32280000000000003}, {0.30510000000000004, 0.3289}, {0.3106,
0.33480000000000004}, {0.3161, 0.34040000000000004}, {0.3215,
0.3453}, {0.3265, 0.3493}, {0.3312, 0.3521}, {0.3351,
0.3534}, {0.303, 0.3201}, {0.22460000000000002,
0.24500000000000002}, {0.19490000000000002,
0.22660000000000002}, {0.2034, 0.2373}, {0.22210000000000002,
0.2544}, {0.2399, 0.2707}, {0.25470000000000004,
0.2848}, {0.26680000000000004,
0.29710000000000003}, {0.27690000000000003, 0.308}, {0.2857,
0.318}, {0.29350000000000004, 0.32730000000000004}, {0.3009,
0.336}, {0.3078, 0.3441}, {0.3145,
0.35150000000000003}, {0.3209, 0.3579}, {0.327,
0.36310000000000003}, {0.3326, 0.3667}, {0.3376,
0.36860000000000004}, {0.3418, 0.3687}, {0.34500000000000003,
0.3668}, {0.34700000000000003, 0.3633}, {0.3024,
0.326}, {0.2494, 0.31270000000000003}, {0.24020000000000002,
0.32170000000000004}, {0.2508, 0.337}, {0.266,
0.3513}, {0.28040000000000004, 0.3629}, {0.2927,
0.3718}, {0.3028, 0.3784}, {0.3113, 0.3831}, {0.3184,
0.38630000000000003}, {0.3245,
0.38820000000000005}, {0.32980000000000004,
0.38880000000000003}, {0.3345, 0.38830000000000003}, {0.3386,
0.38670000000000004}, {0.3421, 0.3839}, {0.3452,
0.3801}, {0.3477, 0.37520000000000003}, {0.3496,
0.3695}, {0.3508, 0.3629}, {0.3512, 0.3558}, {0.3506,
0.3482}, {0.30770000000000003, 0.33290000000000003}, {0.3049,
0.3995}, {0.3174, 0.44830000000000003}, {0.3307,
0.4682}, {0.33990000000000004, 0.46780000000000005}, {0.3452,
0.45780000000000004}, {0.3481,
0.44470000000000004}, {0.34950000000000003, 0.4313}, {0.3503,
0.4189}, {0.3509, 0.4077}, {0.3514, 0.3976}, {0.3519,
0.3884}, {0.35250000000000004, 0.3799}, {0.3531,
0.372}, {0.3537, 0.3644}, {0.3541,
0.35710000000000003}, {0.3543,
0.35000000000000003}, {0.35400000000000004, 0.3431}, {0.3531,
0.3365}, {0.35150000000000003, 0.3301}, {0.3488,
0.3242}, {0.31470000000000004, 0.3392}, {0.3754,
0.4692}, {0.40750000000000003, 0.5152}, {0.41300000000000003,
0.5028}, {0.4072, 0.4727}, {0.39880000000000004,
0.443}, {0.3909, 0.4181}, {0.3841, 0.398}, {0.3785,
0.382}, {0.3739, 0.369}, {0.37020000000000003,
0.3582}, {0.36710000000000004, 0.3492}, {0.3644,
0.3415}, {0.3619, 0.33490000000000003}, {0.35950000000000004,
0.3291}, {0.35710000000000003, 0.3242}, {0.3543,
0.32}, {0.3512, 0.3165}, {0.34740000000000004,
0.31370000000000003}, {0.34290000000000004, 0.3116}, {0.3376,
0.3103}, {0.31970000000000004, 0.3402}, {0.4184,
0.44780000000000003}, {0.456, 0.4526}, {0.45530000000000004,
0.4208}, {0.44160000000000005, 0.3881}, {0.4258,
0.3627}, {0.41100000000000003, 0.3442}, {0.3982,
0.331}, {0.38720000000000004, 0.3215}, {0.37770000000000004,
0.31470000000000004}, {0.3695, 0.3099}, {0.3623,
0.3065}, {0.3558, 0.3044}, {0.34990000000000004,
0.3033}, {0.3443, 0.30310000000000004}, {0.33890000000000003,
0.3037}, {0.3336, 0.305}, {0.32830000000000004,
0.307}, {0.3229, 0.30960000000000004}, {0.3173,
0.31270000000000003}, {0.31170000000000003, 0.3161}, {0.3205,
0.3335}, {0.4072, 0.3511}, {0.43910000000000005,
0.3247}, {0.4358, 0.29710000000000003}, {0.4183,
0.2798}, {0.3976, 0.2716}, {0.3785,
0.2691}, {0.36200000000000004, 0.27}, {0.3482,
0.2726}, {0.33690000000000003, 0.2762}, {0.3274,
0.2803}, {0.3196, 0.2848}, {0.3131,
0.2897}, {0.30770000000000003, 0.2949}, {0.3032,
0.3005}, {0.29960000000000003, 0.3063}, {0.2967,
0.3124}, {0.29460000000000003, 0.3185}, {0.2931,
0.3245}, {0.2922, 0.33}, {0.29200000000000004,
0.33490000000000003}, {0.318,
0.32480000000000003}, {0.36210000000000003,
0.26230000000000003}, {0.3655, 0.2159}, {0.34750000000000003,
0.19770000000000001}, {0.3246, 0.2001}, {0.3048,
0.2122}, {0.2903, 0.22740000000000002}, {0.2806,
0.2426}, {0.2746, 0.2565}, {0.2713, 0.2691}, {0.27,
0.28040000000000004}, {0.2702, 0.2908}, {0.2716,
0.3004}, {0.27390000000000003, 0.3095}, {0.27690000000000003,
0.3181}, {0.2806, 0.3261}, {0.2848,
0.33340000000000003}, {0.2894, 0.33990000000000004}, {0.2942,
0.3452}, {0.29910000000000003, 0.3493}, {0.3039,
0.3519}, {0.3138, 0.31980000000000003}, {0.3068,
0.2265}, {0.2746, 0.18100000000000002}, {0.24350000000000002,
0.1777}, {0.226, 0.197}, {0.2212,
0.22260000000000002}, {0.22440000000000002,
0.24700000000000003}, {0.2316, 0.26780000000000004}, {0.2404,
0.2851}, {0.2495, 0.29960000000000003}, {0.2584,
0.3119}, {0.267, 0.3224}, {0.2752, 0.3317}, {0.2831,
0.3397}, {0.2906, 0.3467}, {0.2977,
0.35250000000000004}, {0.3045,
0.35700000000000004}, {0.31070000000000003,
0.36010000000000003}, {0.3164, 0.3617}, {0.3214,
0.3617}, {0.3257, 0.3603}};

bdrymesh = GetBoundaryMesh[pts, .04];
eplg = {{PointSize[.01], Point[pts]}, bdrymesh};
ListPlot[{}, Epilog -> eplg, PlotRange -> {{0, .7}, {0, .6}}]


This produces this image, which is what I want:

However, if I do the same exact thing, but with 676 points, it doesn't work. Code is here because I've apparently run out of characters in this window (is there a better way to do this?).

It still plots the points, but can't plot the boundary because it wasn't calculated:

There doesn't appear to be anything crazy about those points. The errors it gives are:

MeshPrimitives is not a Graphics primitive or directive.


I'm just not really sure where to begin with diagnosing this because it's working for nearly the exact same input. My best guess is that the computation increases really quickly with input size, and something is basically crapping out when the number is increased too much.

Does anyone know what I could try to fix or diagnose it?

EDIT: Okay, I've gone a little deeper to find the location of the problem, but not what's causing it exactly. I basically manually went through the functions, outside of the functions, step by step, at each step evaluating the results that came from using one set of pts vs the other (I'm calling the first set of (working) points pts1, the second (non-working) set pts2, from the two examples above).

dm1 = DelaunayMesh@pts1
dm2 = DelaunayMesh@pts2

t1 = MeshCells[dm1, 2];
t2 = MeshCells[dm2, 2];

tc1 = MeshPrimitives[dm1, 2][[All, 1]];
tc2 = MeshPrimitives[dm2, 2][[All, 1]];
Dimensions@tc1
Dimensions@tc2

Length@tr1
Length@tr2

ac1 = alphacriteria[t1, tr1, .04]
ac2 = alphacriteria[t2, tr2, .04]
Dimensions@ac1
Dimensions@ac2


They are behaving the same up until this point. At this point ac1 and ac2 are both lists of Polygon[{p1,p2,p3}] where those p's are points from pts1 or pts2, respectively, I believe.

Here's where it stops working. When getExternalFaces[] is called (really just MeshRegion), the first one evaluates to a mesh that appears graphically on my screen, while the second one appears as a MeshRegion[] expression. This is where they diverge so must be the source of the problem, but I have no idea why this happens.

getExternalFaces[facets_, points_] := MeshRegion[points, facets];
ef1 = getExternalFaces[ac1, pts1]
ef2 = getExternalFaces[ac2, pts2]


Any ideas as to why this could be happening? Thanks.

• Just a wild guess: have you checked that all entries of tr2 are positive, finite reals? – user484 Jan 2 '17 at 21:18
• @Rahul, I'm pretty sure they are, but I believe I've actually solved it. I'm going to make sure and then post an answer I guess. – YungHummmma Jan 2 '17 at 21:25

Well, I feel stupid, but at least I figured it out.

The parameters passed to MeshRegion are MeshRegion[{points},{meshcells}], where the points are my xy points and the meshcells are Polygons that refer to those points by their indices in the points list.

On a whim I tried taking a MeshRegion of a subset of the meshcells, because the points all seemed like reasonable points and the Polygons themselves looked good, and it worked:

MeshRegion[pts2, ac2[[1 ;; 500]]]


So, I poked around, changing those indices, and eventually found the trouble. Almost all index bounds work, except for these:

ac2[[771 ;; 773]]


which cause it to do the mess it was before. This is because, if we search for duplicates:

Select[Split@Sort@pts2, Length@# > 1 &]
{{{0.3219, 0.3382}, {0.3219, 0.3382}}}

Position[pts2, {0.3219, 0.3382}]
{{75}, {124}}


Two points are the same. And:

ac2[[771 ;; 773]]
{Polygon[{124, 312, 100}], Polygon[{387, 312, 124}],
Polygon[{75, 175, 312}]}


They all have index 312, and all either have index 75 or 124, so they all share two points.

To be honest I don't know why this is a problem, but it's an easy fix, just delete duplicates before I pass it to this function.

All fixed!