Leaderboard

https://github.com/mapbox/concaveman https://github.com/sadaszewski/concaveman-cpp it’s not automatic in that it requires parameters depending on the point distribution. concavity: A relative measure of concavity. A value of 1 provides a detailed shape, while Infinity results in a convex hull. lengthThreshold: Determines the minimum segment length considered for further detailing, with higher values leading to simpler shapes. Chomped through this 280k point set import traceback from pyrx import Ap, Db, Ed, Ge # --- Command for PyRx --- @Ap.Command() def doit0(): try: ps, ss = Ed.Editor.select([(Db.DxfCode.kDxfStart, "POINT")]) pnts = Ge.Point3dArray([Db.Point(id).position() for id in ss]) hull_points = pnts.concaveHull(0.8, 100) db = Db.curDb() pl = Db.Polyline(hull_points) pl.setDatabaseDefaults() pl.setClosed(True) pl.setColorIndex(2) db.addToModelspace(pl) except Exception: traceback.print_exc()

This is a great guide working with Delaunator. https://mapbox.github.io/delaunator/ It explains the relationship between half-edges and triangles. in short the triangles are created in an order, you can iterate the triangles while being aware of the adjacent triangles. A [-1] in the half edge list means that edge is on the outside hull.

The algorithm is fast because it returns a list of indexes, to your original array, of the points that make up the triangle, it also returns a list of half edges from pyrx import Ap, Db, Ed, Ge, Gi import traceback @Ap.Command() def doit(): try: filter = [(Db.DxfCode.kDxfStart, "POINT")] ps, ss = Ed.Editor.selectPrompt( "\nSelect points: ", "\nRemove points: ", filter ) if ps != Ed.PromptStatus.eNormal: return pnts = Ge.Point3dArray([Db.Point(id).position() for id in ss]) d = Ge.Delaunator(pnts) print(d.triangles()) print(d.halfedges()) except Exception: print(traceback.format_exc()) [0, 4, 3, 2, 1, 0, 0, 1, 4, 3, 2, 0] [8, -1, 11, -1, 6, 10, 4, -1, 0, -1, 5, 2]