2
$\begingroup$

Let v_{0},...,v_{N-1} be N points in a Cartesian xy plane defining the vertices of closed polygon (i.e. v_{N} = v_{0}). Let P_{0} a point lying inside the polygon, point that is not known a priori.

I am looking for a robust algorithm to sort the list v_{0},...,v_{N-1} clockwise/counterclockwise in respect of P_{0}. I know that, if the polygon is convex, the following algorithm works well:

  1. compute P_{0} as the mean of v_{0},...,v_{N-1};
  2. compute the angle defined by atan2 = (y_i-y_0/x_i-x_0) for every vertex and save it into an array;
  3. sort the vertices using the array of the angle as the key.

I am wondering if exist an algorithm able to deal with all kind of polygon, also non-convex.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Is the data not stored in a form that permits traversal? $\endgroup$
    – Richard
    Feb 16, 2019 at 18:08
  • $\begingroup$ what do you mean? @Richard $\endgroup$
    – John Snow
    Feb 17, 2019 at 8:54
  • 3
    $\begingroup$ So you have a list of vertices, say v1,v2,v3,...,vn, and for each vertex the coordinates. Does your list also mean that the polygon has sides v1-v2, v2-v3,...,vn-v1 ? Does sort counterclockwise the vertices mean the same as walking the perimeter of the polygon in a counterclockwise direction ? $\endgroup$
    – High Performance Mark
    Feb 17, 2019 at 15:43
  • $\begingroup$ I have a list of vertices v_1,..., v_n but I don not known the sides because the vertices are not sorted properly; so that, if I compute v_1-v_2, ..., v_n-v_{n-1}, v_n-v_1 those value are unreasonable results. I want to sort the vertices clock/counterclockwise in order to make the perimeter "walkable" in a direction. @ High Performance Mark $\endgroup$
    – John Snow
    Feb 17, 2019 at 17:53
  • 2
    $\begingroup$ Better to edit your question than to cram further explanation into the comment. Leaving that to one side, even a set of only 4 vertex positions does not unambiguously define a convex polygon, it's not at all clear to me that the data you have is enough for the operation of the algorithm you seek. $\endgroup$
    – High Performance Mark
    Feb 17, 2019 at 18:40

1 Answer 1

Reset to default
4
$\begingroup$

As @HighPerformanceMark mentioned in the comments if the set of vertices $V=\{v_0,\ldots,v_{N-1}\}$ is the only information you have about your non-convex polygon, you did not define it uniquely. One can find a non-convex polygon defined by $V$, but not the one.

Below, is the example (certainly non-minimal, but that is the first I drew) of two different six-sided polygons defined by exactly the same set of vertices. In polygon $S_A$, the vertices are ordered counter-clockwise, while $S_B$ is not so lucky.

enter image description here

So, in order for an algorithm to work, you will either get some non-convex polygon (in this example, $P_0\in S_A, S_B$; however, $P_1\in S_B$, but $P_1\notin S_A$), but I can hardly imagine an application that allows for non-uniqueness. Or provide some additional information about your "desired" non-convex polygon – and list of edges come to mind right away. When the edge list is present, you probably don't need that algorithm in the first place, or the reordering becomes trivial by traversing the edge list.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Many thanks @AntonMenshow. So I need also the edge list. You said that "When the edge list is present, you probably don't need that algorithm in the first place, or the reordering becomes trivial by traversing the edge list." Can you explain in more details this strategy? thanks $\endgroup$
    – John Snow
    Feb 18, 2019 at 6:32
  • $\begingroup$ @JohnSnow I mean if you have an edge-list $E=\{e_0,\ldots,e_{N-1}\}$ that will say (on the example of my polygon $S_B$): $e_0=\{v_1,v_5\}$,$e_1=\{v_0,v_3\}$, $e_2=\{v_5,v_0\}$ , $e_3=\{v_3,v_2\}$, $e_4=\{v_2,v_4\}$, $e_5=\{v_4,v_1\}$ – you can just start from $e_0$, rename $v_1$ into $v^\prime_0$ and $v_5$ into $v^\prime_1$. Then then find the next edge that has $v_5$ as a starting point. It is $e_2$ and proceed until everything is processed. Tha algorithm does not even require consecutive ordering of edges in an edge list $E$ (which will be probably consecutive when you get it anyway). $\endgroup$
    – Anton Menshov ♦
    Feb 18, 2019 at 7:29
  • $\begingroup$ Thanks @AntonMenshow. Done it and it seems working. $\endgroup$
    – John Snow
    Feb 18, 2019 at 19:30

Your Answer

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

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