Discretization
Meshes.discretize
— Functiondiscretize(geometry, [method])
Discretize geometry
with discretization method
.
If the method
is ommitted, a default algorithm is used with a specific number of elements.
Meshes.discretizewithin
— Functiondiscretizewithin(boundary, method)
Discretize geometry within boundary
with boundary discretization method
.
Meshes.simplexify
— Functionsimplexify(object)
Discretize object
into simplices using an appropriate discretization method.
Notes
This function is sometimes called "triangulate" when the object
has parametric dimension 2.
Meshes.DiscretizationMethod
— TypeDiscretizationMethod
A method for discretizing geometries into meshes.
FanTriangulation
Meshes.FanTriangulation
— TypeFanTriangulation()
The fan triangulation algorithm for convex polygons. See https://en.wikipedia.org/wiki/Fan_triangulation.
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
![Example block output](c1a7517a.png)
DehnTriangulation
Meshes.DehnTriangulation
— TypeDehnTriangulation()
Max Dehns' triangulation proved in 1899.
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
# 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
![Example block output](cfd64bfc.png)
HeldTriangulation
Meshes.HeldTriangulation
— TypeHeldTriangulation([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
mesh = discretize(polyarea, HeldTriangulation())
fig = Mke.Figure(size = (800, 400))
viz(fig[1,1], polyarea)
viz(fig[1,2], mesh, showsegments = true)
fig
![Example block output](8134f081.png)
DelaunayTriangulation
Meshes.DelaunayTriangulation
— TypeDelaunayTriangulation()
Constrained Delaunay triangulation of polygons. Optionally, specify the random number generator rng
.
References
- Cheng et al. 2012. Delaunay Mesh Generation
Notes
Wraps DelaunayTriangulation.jl. For any internal errors, file an issue at DelaunayTriangulation.jl
mesh = discretize(polyarea, DelaunayTriangulation())
fig = Mke.Figure(size = (800, 400))
viz(fig[1,1], polyarea)
viz(fig[1,2], mesh, showsegments = true)
fig
![Example block output](3685d118.png)
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
![Example block output](438416be.png)
RegularDiscretization
Meshes.RegularDiscretization
— TypeRegularDiscretization(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
.
sphere = Sphere((0.,0.,0.), 1.)
mesh = discretize(sphere, RegularDiscretization(10,10))
viz(mesh, showsegments = true)
![Example block output](7dbd2857.png)
ManualSimplexification
Meshes.ManualSimplexification
— TypeManualSimplexification()
Simplexify convex geometries manually using indices of vertices.
box = Box((0., 0., 0.), (1., 1., 1.))
mesh = discretize(box, ManualSimplexification())
viz(mesh, colors = 1:nelements(mesh))
![Example block output](23060f3f.png)