hxGeomAlgo

Small collection of geometry algorithms in Haxe 3. (link to AS3 port)

online swf demo

Marching Squares (Contour Tracing)

Based on:

• http://devblog.phillipspiess.com/2010/02/23/better-know-an-algorithm-1-marching-squares/ (C# - by Phil Spiess)
• http://www.tomgibara.com/computer-vision/marching-squares (Java - by Tom Gibara)

Ramer-Douglas-Peucker (Polyline Simplification)

Based on:

• http://karthaus.nl/rdp/ (JS - by Marius Karthaus)
• http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment (JS - Grumdrig)

Ear Clipping (Triangulation and Poly Decomposition)

Based on:

• http://www.box2d.org/forum/viewtopic.php?f=8&t=463&start=0 (JSFL - by mayobutter)
• http://www.ewjordan.com/earClip/ (Processing - by Eric Jordan)
• http://en.nicoptere.net/?p=16 (AS3 - by Nicolas Barradeau)
• http://blog.touchmypixel.com/2008/06/making-convex-polygons-from-concave-ones-ear-clipping/ (AS3 - by Tarwin Stroh-Spijer)
• http://headsoft.com.au/ (C# - by Ben Baker)

Bayazit (Poly Decomposition)

Based on:

• http://mnbayazit.com/406/bayazit (C - by Mark Bayazit)

Visibilty Polygon and Homogeneous Coords (2D)

Based on:

• http://www.cs.ubc.ca/~snoeyink/demos/convdecomp/VPDemo.html (Java - by Jack Snoeyink)

Snoeyink-Keil (Minimum Convex Decomposition)

Based on:

• http://www.cs.ubc.ca/~snoeyink/demos/convdecomp/MCDDemo.html (Java - by Jack Snoeyink & Mark Keil)
• J. Mark Keil, Jack Snoeyink: On the Time Bound for Convex Decomposition of Simple Polygons. Int. J. Comput. Geometry Appl. 12(3): 181-192 (2002)

Connected Components Labeling and Contour Tracing (w/ Holes)

Based on:

• Fu Chang, Chun-jen Chen, Chi-jen Lu: A linear-time component-labeling algorithm using contour tracing technique (2004)

Visvalingam-Whyatt (Polyline Simplification)

Based on:

• Visvalingam M., Whyatt J. D.: Line generalisation by repeated elimination of the smallest area (1992)
• http://bost.ocks.org/mike/simplify/ (JS - by Mike Bostock)
• https://github.com/jonasmalacofilho/dheap (Haxe - by Jonas Malaco Filho)
• http://en.wikipedia.org/wiki/Binary_heap (Binary (Min)Heap)

Tess2 (Tesselation to Triangles and Convex Polygons, Poly Boolean Ops)

Based on:

• GLU Libtess (by Eric Veach, July 1994)
• tess2.js (JS - by Mikko Mononen, Aug 2013)

IsoContours (Contour Tracing)

Based on:

• http://en.wikipedia.org/wiki/Marching_squares
• https://github.com/deltaluca/nape (Haxe - by Luca Deltodesco)
• https://github.com/scikit-image/scikit-image (Python - by scikit-image team)

Credits

hxGeomAlgo is based on the work of many developers and it wouldn't exist if it weren't for them. See the CREDITS file for details.

License

hxGeomAlgo is developed by Giuseppe Di Mauro (azrafe7) and released under the MIT license (except for Tess2.hx). See the LICENSE file for details.