Discretization

Meshes.discretize — Function

discretize(geometry, [method])

Discretize geometry with discretization method.

If the method is omitted, a default is used as a function of the geometry. Geometries over the 🌐 manifold are refined until the segments are shorter than a maximum length.

source

Meshes.discretizewithin — Function

discretizewithin(boundary, method)

Discretize geometry within boundary with boundary discretization method.

source

Meshes.simplexify — Function

simplexify(object)

Discretize object into simplices using an appropriate discretization method.

Notes

This function is sometimes called "triangulate" when the object has parametric dimension 2.

source

Meshes.DiscretizationMethod — Type

DiscretizationMethod

A method for discretizing geometries into meshes.

source

FanTriangulation

Meshes.FanTriangulation — Type

FanTriangulation()

The fan triangulation algorithm for convex polygons. See [https://en.wikipedia.org/wiki/Fantriangulation] (https://en.wikipedia.org/wiki/Fantriangulation).

source

hexagon = Hexagon((0.,0.), (1.,0.), (1.,1.),
                  (0.75,1.5), (0.25,1.5), (0.,1.))

mesh = discretize(hexagon, FanTriangulation())

fig = Mke.Figure(size = (800, 400))
viz(fig[1,1], hexagon)
viz(fig[1,2], mesh, showsegments = true)
fig

The algorithm is described in the first chapter of Devadoss & Rourke 2011, and is based on a theorem derived in 1899 by the German mathematician Max Dehn. See https://en.wikipedia.org/wiki/Two_ears_theorem.

Because the algorithm relies on recursion, it is mostly appropriate for polygons with small number of vertices.

References

Devadoss, S & Rourke, J. 2011. [Discrete and computational geometry] (https://press.princeton.edu/books/hardcover/9780691145532/discrete-and-computational-geometry)

source

# polygonal area
polyarea = PolyArea([(0.22926679, 0.47329807), (0.23094065, 0.44913536), (0.2569517, 0.38217533),
                     (0.3072999, 0.272418), (0.34814754, 0.18421611), (0.37949452, 0.11756973),
                     (0.4013409, 0.07247882), (0.41368666, 0.048943404), (0.42597583, 0.031655528),
                     (0.4382084, 0.0206152), (0.45038435, 0.015822414), (0.4625037, 0.017277176),
                     (0.47175184, 0.02439156), (0.47812873, 0.03716557), (0.4816344, 0.055599205),
                     (0.48226887, 0.07969247), (0.48172843, 0.10446181), (0.4800131, 0.12990724),
                     (0.47712287, 0.15602873), (0.47305775, 0.18282633), (0.47093934, 0.20558843),
                     (0.47076762, 0.22431506), (0.47254258, 0.23900622), (0.47626427, 0.24966191),
                     (0.47768936, 0.25845313), (0.47681788, 0.26537988), (0.4736498, 0.27044216),
                     (0.46818516, 0.27363995), (0.4613889, 0.27232954), (0.45326096, 0.2665109),
                     (0.44380143, 0.256184), (0.43301025, 0.24134888), (0.4246466, 0.22978415),
                     (0.41871038, 0.22148979), (0.4152017, 0.21646582), (0.4141205, 0.21471222),
                     (0.41227448, 0.21589448), (0.40966362, 0.22001258), (0.40628797, 0.22706655),
                     (0.40214747, 0.23705636), (0.40200475, 0.24653101), (0.40585983, 0.25549048),
                     (0.41371268, 0.2639348), (0.4255633, 0.2718639), (0.4378565, 0.28495985),
                     (0.4505922, 0.30322257), (0.46377045, 0.32665208), (0.47739124, 0.35524836),
                     (0.5046394, 0.36442512), (0.5455148, 0.35418236), (0.60001767, 0.32452005),
                     (0.66814786, 0.27543822), (0.7186763, 0.24664374), (0.75160307, 0.23813659),
                     (0.76692814, 0.2499168), (0.7646515, 0.28198436), (0.7769703, 0.29925033),
                     (0.8038847, 0.3017147), (0.84539455, 0.28937748), (0.9015, 0.26223865),
                     (0.94408435, 0.24899776), (0.9731477, 0.24965483), (0.98869, 0.26420987),
                     (0.9907113, 0.29266283), (0.9849871, 0.31338844), (0.97151726, 0.32638666),
                     (0.950302, 0.3316575), (0.9213412, 0.32920095), (0.8798396, 0.34078467),
                     (0.8257972, 0.36640862), (0.7592141, 0.40607283), (0.6800901, 0.4597773),
                     (0.6450007, 0.49104902), (0.6539457, 0.49988794), (0.7069251, 0.48629412),
                     (0.803939, 0.45026752), (0.877913, 0.4226481), (0.9288472, 0.40343583),
                     (0.9567415, 0.39263073), (0.961596, 0.39023277), (0.9419039, 0.40523484),
                     (0.89766514, 0.43763688), (0.8288798, 0.48743892), (0.7355478, 0.55464095),
                     (0.6655121, 0.60063523), (0.6187727, 0.6254217), (0.5953296, 0.62900037),
                     (0.5951828, 0.6113712), (0.57516366, 0.60261106), (0.53527224, 0.6027198),
                     (0.4755085, 0.6116975), (0.3958725, 0.6295441), (0.33913234, 0.6398651),
                     (0.30528808, 0.6426605), (0.2943397, 0.6379303), (0.30628717, 0.6256744),
                     (0.32149008, 0.6093727), (0.33994842, 0.5890249), (0.36166218, 0.5646312),
                     (0.38663134, 0.5361916), (0.3919681, 0.520893), (0.3776725, 0.5187355),
                     (0.34374446, 0.52971905), (0.29018405, 0.5538437), (0.25439468, 0.5678829),
                     (0.2363764, 0.5718367), (0.23612918, 0.56570506), (0.25365302, 0.549488),
                     (0.2733971, 0.5246488), (0.29536137, 0.49118724), (0.3195459, 0.4491035),
                     (0.34595063, 0.39839754), (0.3647463, 0.3590396), (0.37593287, 0.33102974),
                     (0.37951034, 0.31436795), (0.37547874, 0.30905423), (0.36070493, 0.3204269),
                     (0.33518887, 0.348486), (0.29893062, 0.3932315), (0.25193012, 0.45466346)])

mesh = discretize(polyarea, DehnTriangulation())

fig = Mke.Figure(size = (800, 400))
viz(fig[1,1], polyarea)
viz(fig[1,2], mesh, showsegments = true)
fig

HeldTriangulation

Meshes.HeldTriangulation — Type

HeldTriangulation([rng]; shuffle=true)

Fast Industrial-Strength Triangulation (FIST) of polygons.

This triangulation method is the method behind the famous Mapbox's Earcut library. It is based on a ear clipping algorithm adapted for complex n-gons with holes. It has O(n²) time complexity where n is the number of vertices. In practice it is very efficient due to heuristics implemented in the algorithm.

The option shuffle is used to shuffle the order in which ears are clipped. It improves the quality of the triangles, which can be very sliver otherwise. Optionally, specify the random number generator rng.

References

Held, M. 1998. [FIST: Fast Industrial-Strength Triangulation of Polygons] (https://link.springer.com/article/10.1007/s00453-001-0028-4)
Eder et al. 2018. [Parallelized ear clipping for the triangulation and constrained Delaunay triangulation of polygons] (https://www.sciencedirect.com/science/article/pii/S092577211830004X)

source

mesh = discretize(polyarea, HeldTriangulation())

fig = Mke.Figure(size = (800, 400))
viz(fig[1,1], polyarea)
viz(fig[1,2], mesh, showsegments = true)
fig

DelaunayTriangulation

Meshes.DelaunayTriangulation — Type

DelaunayTriangulation([rng])

Constrained Delaunay triangulation of polygons. Optionally, specify the random number generator rng.

References

Cheng et al. 2012. [Delaunay Mesh Generation] (https://people.eecs.berkeley.edu/~jrs/meshbook.html)

Notes

Wraps DelaunayTriangulation.jl. For any internal errors, file an issue at DelaunayTriangulation.jl

source

mesh = discretize(polyarea, DelaunayTriangulation())

fig = Mke.Figure(size = (800, 400))
viz(fig[1,1], polyarea)
viz(fig[1,2], mesh, showsegments = true)
fig

As can be seen in the following example, all discretization methods for Polygon automatically work in the presence of holes:

outer = [(0.18142937, 0.54681134), (0.38282228, 0.107781954), (0.43220532, 0.013640274),
         (0.48068276, 0.019459315), (0.48322055, 0.11583236), (0.46696007, 0.2230227),
         (0.48184678, 0.2656454), (0.45998818, 0.2784367), (0.4168235, 0.2190962),
         (0.4124987, 0.21208182), (0.39593673, 0.2520411), (0.44333926, 0.28375763),
         (0.4978224, 0.3981428), (0.7703431, 0.20181546), (0.7612364, 0.33008572),
         (0.9856581, 0.2215304), (0.99374324, 0.3353423), (0.9688778, 0.38663587),
         (0.59554976, 0.655444), (0.59496254, 0.58492756), (0.27641845, 0.656314),
         (0.3242084, 0.6072907), (0.42408508, 0.49353212), (0.20984341, 0.59003067)]

inners = [[(0.87789994, 0.32551613), (0.5614043, 0.540334), (0.9494598, 0.39622766)],
          [(0.2799388, 0.52516246), (0.38555774, 0.32233855), (0.36943135, 0.30108362)]]

polyarea = PolyArea([outer, inners...])

mesh = discretize(polyarea, DelaunayTriangulation())

fig = Mke.Figure(size = (800, 400))
viz(fig[1,1], polyarea)
viz(fig[1,2], mesh, showsegments = true)
fig

RegularDiscretization

Meshes.RegularDiscretization — Type

RegularDiscretization(n1, n2, ..., np)

A method to discretize primitive geometries with n1×n2×...×np elements sampled regularly along each parametric dimensions. The adequate number of points is calculated for each type of geometry and passed to RegularSampling.

source

sphere = Sphere((0.,0.,0.), 1.)

mesh = discretize(sphere, RegularDiscretization(10,10))

viz(mesh, showsegments = true)

ManualSimplexification

Meshes.ManualSimplexification — Type

ManualSimplexification()

Simplexify convex geometries manually using indices of vertices.

source

box = Box((0., 0., 0.), (1., 1., 1.))

mesh = discretize(box, ManualSimplexification())

viz(mesh, colors = 1:nelements(mesh))