CODEWITHSUNDEEP
algorithmgoogle-mapsgeometry
Nicolas
Nicolas

Reputation: 2367

Place a marker arbitrarily inside a polygon in Google Maps

There is a lot of documentation around how to detect if a marker is within a polygon in Google Maps. However, my question is how can I arbitrarily place a marker inside a polygon (ideally as far as possible from the edges)

I tried calculating the average latitude and longitude of the polygon's points, but this obviously fails in some non-concave polygons.

I also thought about calculating the area's center of mass, but obviously the same happens.

Any ideas? I would like to avoid trial-and-error approaches, even if it works 99% of the time.

Upvotes: 2

Views: 267

Answers (1)

Darren Engwirda
Darren Engwirda

Reputation: 7015

There are a few different ways you could approach this, depending on what exactly you're overall goal is.

One approach would be to construct a triangulation of the polygon and place the marker inside one of the triangles. If you're not too worried about optimality you could employ a simple heuristic, like choosing the centroid of the largest triangle, although this obviously wont necessarily give you the point furthest from the polygon edges. There are a number of algorithms for polygon triangulation: ear-clipping or constrained Delaunay triangulation are probably the way to go, and a number of good libraries exist, i.e. CGAL and Triangle.

If you are interested in finding an optimal placement it might be possible to use a skeleton based approach, using either the medial-axis or the straight skeleton of the polygon. The medial-axis is the set of curves equi-distant from the polygon edges, while the straight skeleton is a related structure. Specifically, these type of structures can be used to find points which are furthest away from the edges, check this out for a label placement application for GIS using an approach based on the straight skeleton.

Hope this helps.

Upvotes: 2

Related Questions