search

noinia / hgeometry

HGeometry is a library for computing with geometric objects in Haskell. It defines basic geometric types and primitives, and it implements some geometric data structures and algorithms.
121 stars 40 forks source link

Approximate Convex Decomposition in O(n) with the Hertel/Mehlhorn algorithm #226

Open mrehayden1 opened 5 months ago

mrehayden1 commented 5 months ago

I'm thinking about tacking this for some work on navigation meshes.

I was wondering, should we allow the user to choose an arbitrary triangulation and pass that to the decomposition algorithm?

noinia commented 5 months ago

Cool! Briefly looking at the Hertel/Mehlhorn paper the algorithm is essentially this right?:

Observe that OPT ~ r/2 + 1 since one partitioning edge is necessary for each concave angle. We shall partition P into at most 2r + I convex subpolygons. To do this, scan the n-3 triangulation edges one by one. Drop an edge if it divides two convex angles. Call edge e essential for point p if it cannot be dropped because it divides a concave angle at point p. It is easy to show that not more than two triangulation edges are essen- tial for each point with concave angle.

In that case, I think its probably easiest to just expose a function with type "PlaneGraph s point PolygonEdgeType PolygonFaceData -> PlaneGraph s point PolygonEdgeType PolygonFaceData "

and directly use the input PlaneGraph from the result of triangulate. E.g. so that someone can indeed use whatever way the triangulation was constructed. The above function should not be too hard to write I think; since it involves just filtering the edges and calling a function to reconstruct the planeGraph.