search

locationtech / jts

The JTS Topology Suite is a Java library for creating and manipulating vector geometry.
Other
1.98k stars 443 forks source link

Dynamic ConvexHull implementation #457

Closed ShivKJ closed 5 years ago

ShivKJ commented 5 years ago

Hi,

Can we get implementation of a dynamic/incremental convexhull in which, later on we can add points to convexHull and modify/getNew convexHull ?

dr-jts commented 5 years ago

This would be a nice addition to JTS. Can't promise any timeline on this, however.

From a quick scan of the web there seems to be a surprising dearth of Java incremental convex hull algorithms. The ESRI geometry library has one, but that code comes with a lot of strings attached. It's based on Knuth's treehull algorithm, so that's a potential basis for implementation.

Note that you could use the current JTS ConvexHull algorithm in an incremental fashion, by maintaining the hull of the current point set, and recomputing it including added points when needed. Obviously this is not going to have theoretically optimal performance, but the average case performance might be acceptable, especially if it includes a fast check for the case when the added point lies inside the current convex hull (i.e. using IndexedPointInAreaLocator).