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["NDSolve`FEM`"];
ashape = alphaShapes2DC[points, alphaparameter];
bmesh = NDSolve`FEM`ToBoundaryMesh@ashape;
Return@MeshPrimitives[MeshRegion@bmesh, 1];
]
circumRadius2D =
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,
tricoords, triradii, getExternalFaces},
alphacriteria[triangle_, radius_, rmax_] :=
Pick[triangle, UnitStep@Subtract[rmax, radius], 1];
getExternalFaces[facets_] := MeshRegion[points, facets];
If[Head[del] === EmptyRegion, del, tris = MeshCells[del, 2];
tricoords = MeshPrimitives[del, 2][[All, 1]];
triradii = circumRadius2D@tricoords;
getExternalFaces@alphacriteria[tris, triradii, crit]]]
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
Head@DelaunayMesh@pts1
Head@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
tr1 = circumRadius2D@tc1;
tr2 = circumRadius2D@tc2;
Length@tr1
Length@tr2
alphacriteria[triangle_, radius_, rmax_] :=
Pick[triangle, UnitStep@Subtract[rmax, radius], 1];
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.
tr2
are positive, finite reals? $\endgroup$