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 ?

  • 1
    Sounds like homework. Show us what you've tried or tried to learn or google and not found. – Michael Durrant Jul 2 '15 at 22:16
  • Are you looking for line simplification? – rwong Jul 2 '15 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 '15 at 8:29

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.

  • Yes they are polygon (like boundaries of the cities) – frenchone Jul 3 '15 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 '15 at 7:53
  • I'll have a (deeper) look at it. Right now it looks quite promising – frenchone Jul 3 '15 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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