locationtech / spatial4j

LocationTech Spatial4j: A Geospatial Library for Java
https://projects.eclipse.org/projects/locationtech.spatial4j
936 stars 168 forks source link

Compute polygon approximation of geodetic circle #57

Open dsmiley opened 10 years ago

dsmiley commented 10 years ago

Given a geodetic circle, produce a polygon that encloses (i.e. circumscribes) the true circle shape. It should take an additional input that is the maximum error distance between the edge of the true circle and any given vertex; the smaller this error distance is, the more points will be needed to approximate the circle. Furthermore, the polygon must fit within the bounding box of the circle.

I've seen code that instead produces a series of points along the circle at fixed angles but that produces a shape that does not include some of the outer edge of the circle. To add further detail to this task, the polygon is projected directly in lat-lon space (just as polygons are done now in Spatial4j.

If this task were done about perfectly, then the outer polygon's sides would all be tangent to the circle so as to minimize cumulative error. If that proves too challenging then I've worked out a loose algorithm for solving this task but doesn't produce perfectly tangent edges except for the edges coinciding with the bounding box.

dsmiley commented 10 years ago

FYI Evana is working on this here: https://github.com/Evana13G/spatial4j