0

Am looking for something that is incremental (with accessible state). So that likely means some merge method is exposed.

So in general I want to start with a set of points, that has a ConvexHull calculated and add a point to it (which trivially has itself as a convex hull). Was looking for alternatives to BowyerWatson through convex hull merges. Not sure if this is a bad idea. Not sure if this should be a question in CS except it's about finding a real solution in the python echosystem.

I see some related content here.

Merging two tangled convex hulls

And Qhull (scipy Delaunay and ConvexHull use this) has a lot of options I do not yet understand

http://www.qhull.org/html/qh-optq.htm

mathtick
  • 6,487
  • 13
  • 56
  • 101
  • Why not use scipy's incremental ConvexHull.add_points(points) ? – Iddo Hanniel Mar 24 '22 at 12:29
  • Interesting. I wonder if there is a way to copy/reuse the previous ConvexHull or if that manipulates state. – mathtick Mar 31 '22 at 16:49
  • From documentation: "You need to specify incremental=True when constructing the object to be able to add points incrementally. Incremental addition of points is also not possible after close has been called." From this I understand that while the library uses inner structures for the incremental construction, it does not give you access to them. There is also no documented copy constructor, which strengthens this belief. – Iddo Hanniel Apr 03 '22 at 10:46

1 Answers1

1

You can use Andrew's modification of the Graham scan algorithm.

Here is a reference to some short python code implementing it.

What makes it suited for your needs is that after the points are sorted in xy-order, the upper and lower hulls are computed in linear time. Since you already have the convex hull (possibly both convex hulls), the xy-sorting of the convex hull points will take linear time (e.g., reverse the lower hulls and merge-sort four sorted lists). The rest of the algorithm will take linear time (in the number of points on the convex hulls, which may well be much smaller than the original number of points).

All the functionality for this implementation is in the code referenced above, and for the merge you can use the code from this SO answer or implement your own.

Iddo Hanniel
  • 1,636
  • 10
  • 18
  • I see it says 2d only there for Andrew's modification ... but I'm guessing (have only skimmed at this point) that it's just a matter of adapting the search order (notions like clockwise) or something like that for higher dims? – mathtick Apr 04 '22 at 07:38
  • I am not aware of an extension of Andrew's algorithm (or Graham scan) for higher dimensions. – Iddo Hanniel Apr 04 '22 at 15:36