Discretization

Dehn1899

Meshes.Dehn1899Type
Dehn1899()

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/Twoearstheorem.

Because the algorithm relies on recursion, it is only appropriate for small polygonal areas. Currently, the implementation does not support holes.

References

source
using Meshes
using Plots

# 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),
                     (0.22926679, 0.47329807)])

mesh = discretize(polyarea, Dehn1899())

plot(plot(polyarea), plot(mesh))

FIST

Meshes.FISTType
FIST(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.

References

source
mesh = discretize(polyarea, FIST())

plot(plot(polyarea), plot(mesh))

As can be seen in the following example, FIST is also suitable for polygonal areas with 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),
         (0.18142937, 0.54681134)]

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

polyarea = PolyArea(outer, inners)

mesh = discretize(polyarea, FIST())

plot(plot(polyarea), plot(mesh))