2

Inside a large polygon (say the USA boundaries) I need to find the shortest path that will encompass smaller polygons
(say the following cities: Kansas city, St Louis, Memphis, Oklahoma City)

By shortest I mean with the less nodes as possible. (then will the smaller inner surface)

A 'not-that-bad' result will be the bounding rectangle that comprises the 4 cities
A better one will be a triangle (3 nodes < 4) New York, San Antonio, Seattle
An even better would be the triangle Minneapolis, Louisville, El Paso because surface is less than previous one

Exemple For non US

imagine a large rectangle 0,0 => 1000,1000
inside 4 points 490,490 ; 490,510 ; 510,510 ; 510,490
a good result : rectangle 490,490 => 510,510
a better result : large triangle 490,0 490,490 1000,490
an even better : small triangle 490,490 ; 530,490 490,530

Is there a well known algorithm for this ?

3
  • 1
    Sounds like homework. Show us what you've tried or tried to learn or google and not found. Jul 2, 2015 at 22:16
  • Are you looking for line simplification?
    – rwong
    Jul 2, 2015 at 23:27
  • This is not homework. (Or yes this is DIY home work). What I've tried ? Paper and pen. I would start to compute the convex hull. Then for each segment I would create a rect bounding box that goes through this segment. If the bounding box fits inside the main polygon then I got a 4nodes path. If not, then I will : intersect bounding box with surrounding polygon, simplify the spikes of surrounding polygon that goes into my bounding box. Then I'll keep the path with the less node.
    – frenchone
    Jul 3, 2015 at 8:29

1 Answer 1

2

You say, "encompass smaller polygons," but then you seem to treat these polygons as points. If they are indeed effectively points, as opposed to extended polygons, then you are seeking to solve the Traveling Salesman Problem, or TSP, which is a heavily studied (and difficult) problem.

Your instance is not a pure TSP, because you have a bounding, constraining polygon. This version is known in the literature as the geodesic convex hull inside a polygon. There is a paper by Toussaint on this topic that I cannot identify at the moment, but maybe these terms could help your search.

3
  • Yes they are polygon (like boundaries of the cities)
    – frenchone
    Jul 3, 2015 at 7:45
  • Even if they were polygons this would not look like the salesman to me. I don't want to go through the cities I want to encompass them.
    – frenchone
    Jul 3, 2015 at 7:53
  • I'll have a (deeper) look at it. Right now it looks quite promising
    – frenchone
    Jul 3, 2015 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.