Finding a representative mean INTERIOR point for a non-convex polygon

Question

I am trying to solve a travelling salesman problem in c++, but i have to traverse the shortest distance between a set of poylgons instead of a set of points. To do so, i am trying to represent each polygon by a representative "mean" interior point so that i can do a TSP on these mean interior points.

It is easy for me to find a mean interior point in a convex polygon because it is simply the arithmetic mean point (and will always lie inside for a convex polygon), but this approach will not work for a concave polygon because it will not necessarily be interior to the polygon.

Help on this? Thanks. :-)

Answer 1

How about:

1. Triangulate polygon (order N log(N))
2. Pick triangle with largest area (say) (order N)
3. Pick your point at the barycenter of that triangle. (const)

Since the true barycenter of the whole non-convex polygon is (potentially) outside the polygon I don't think there is another definition for a "representative" point that makes more sense to me than this.

Answer 2

One idea is to construct the convex hull of each polygon and then use the center of the convex hull. To understand the idea is like if you wrap any polygon with a rubber band, this give you an envelop you can use to find the point of interest. I believe you should be able to compute that using CGAL. But if you do this for every polygon it is not going to be super fast. If you build a triangulation then you can efficiently find the closest interior point of the original polygon to the center point of its convex hull as an additional step.

btw I think that the proper way to find the point center of a Convex polygon is to find the Chebyshev center and this correspond to solving a linear system which you can also do using CGAL. The linear programming problem for finding the Chebyshev center of a convex polygon is well defined in the Boyd book.