1
$\begingroup$

I have a random polygon, convex or non-convex, defined by its vertices and two random points outside of the polygon (A and B) all of them defined in ${\rm I\!R}^{2}$, how can I get an optimized path, the shortest path, from the point A to point B rounding the polygon, i.e., the path cannot go through the polygon, it is important to note that the polygon is defined as a set of points, its vertices, where the first one and last one are equals and counter-clockwise, i.e., joining the points you get a counter-clockwise polygon.

$\endgroup$
  • $\begingroup$ Can polygon be not convex? $\endgroup$ – Vladislav Mar 12 '19 at 13:20
  • $\begingroup$ Not necessarily, I know that if it's convex is easier, that's the problem, but I can simplify the problem by substituting the non-convex polygon by its convex hull, but I prefer to not do that. $\endgroup$ – Rodrigo Mar 12 '19 at 13:26
  • $\begingroup$ A set of points does not define a polygon. $\endgroup$ – Yves Daoust Mar 12 '19 at 16:31
0
$\begingroup$

I would think you can use the convex hull generated by $A$, $B$ and the polygon. Clearly then $A$, $B$ are located on the boundary of the convex hull. Then $A$, $B$ dissect the boundary in 2 parts. Choose the part which is shorter than the other.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, but I am searching for a more optimized path, do you know an article that can be useful? $\endgroup$ – Rodrigo Mar 12 '19 at 13:12
  • $\begingroup$ Not clear to me what you have in mind. I thought "optimized path" = "shortest path", but it seems that I am wrong. Could you elaborate this in your Q ? $\endgroup$ – Maksim Mar 12 '19 at 13:50
  • $\begingroup$ I do not know if calculate the convex hull for a polygon that has more than 500 vertices is slow, but your right about that is the shortest path, I did not specified that in my comment, for the moment I am searching for the shortest path. $\endgroup$ – Rodrigo Mar 13 '19 at 8:35
0
$\begingroup$

I’ll assume the following

  1. An “optimized path” is the shortest path in the Euclidean sense
  2. The polygon is equal to the convex hull of the given vertices

By rotation and scaling, we can assume that $A$ and $B$ lie on the $x$-axis, with $A$ strictly to the left of $B$. Let $V$ denote the given set of vertices.

Partition $V$ into $V^+$ and $V^-$, the set of vertices that lie above and below the $x$-axis, respectively.

Sort the vertices in $V^+$ by increasing $x$-coordinate (ties are broken by increasing $y$-coordinate). Label these vertices $v_0,v_1,\dots,v_{n+}$. Starting at $v_0$, move along until you find the vertex $v_k$ such that every vertex $v_0,\dots,v_{k-1}$ lies below the line connecting $A$ and $v_k$, but $v_k$ lies strictly above the line connecting $A$ and $v_{k+1}$. The first leg of the path is the straight line connecting $A$ to $v_k$.

Next, starting at $v_k$, continue moving through the list until you find a vertex $v_\ell$ such that every vertex $v_{\ell+1},\dots,v_{n+}$ lies strictly below the line connecting $v_\ell$ and $B$, but $v_\ell$ lies strictly above the line connecting $v_{\ell-1}$ to $B$. The next section of the path is the path from $v_k$ to $v_{k+1}$ to ... to $v_\ell$.

The final segment of the path is the straight line connecting $v_\ell$ to $B$.

Repeat the above for $V^-$, and pick the shorter of the two resulting paths.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It's an interesting algorithm for convex polygons, thanks. $\endgroup$ – Rodrigo Mar 13 '19 at 8:31

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.