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

7
votes

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. :-)

2
c++algorithmvisual-c++graphics
How do you represent your polygons? I have added the tag algorithm because this is basically algorithmic problem. What kind of complexity can you afford? – Boris Strandjev
What would be your definition of mean INTERIOR point? – Xyand
Why does it have to be an interior point? I would imagine you either want to find an approximation, in which case I don't understand why interior is neccessary. Or a shortest path in general, in which case I would not use mean representatives, but get rid of polygons alltogether and transform the problem into TSP directly. – Fiktik
You might be interested into Straight Skeletons. – pmr
@Boris right now I am looking for a good solution and can afford upto a maximum of N^3. – Ananth Saran

2 Answers

3
votes

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.

1
votes

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.