Given a simple 2D polygon P = ( M1 .. Mn ) and a point M, is it always possible to construct a new simple polygon P' by "adding" M to P as a new vertex?

If so, is this always possible without altering the order of P's vertices?

I think that the answer to those 2 questions is yes, but I tried to prove it, and failed.

My approach was to try to define some kind of distance between M and each of P's side, whereby the "closest" such side would be the one to break to insert M as a new vertex. Obviously, the usual orthogonal distance from a point to a line doesn't work.

The larger context is a drawing program I am writing where I allow the user to add vertices to her polygons, but where I strive to keep the polygons simple.

(simple polygon: a polygon where no two sides cross).

PS: English is a foreign language to me, especially when talking maths. I apologize if my question comes across as awkwardly worded.


A counterexample is the (nonconvex) octagon with vertices

(1,2), (1,3), (2,-1), (3,-1),
(-1,-2), (-1,-3), (-2,1), (-3,1)

You cannot add the point (0,0) between any two of the points without creating an intersection.

  • $\begingroup$ So this is a counter example to my second question. But obviously, if you are allowed to reorder P's vertices (as I intended in my question, but probably failed to convey), this is different $\endgroup$ Sep 8 '11 at 19:46
  • $\begingroup$ Well, if you can reorder vertices arbitrarily, then the question is just whether an arbitrary finite set of points can be the vertices of a simple polygon. It think it is clear that they can, except if they are all collinear -- pick a center in the interior of the convex hull of the points, and then order the points according to the angle between them and the center. $\endgroup$ Sep 8 '11 at 20:15
  • $\begingroup$ Yes. I can see that. The remaining problem is a programming problem, not a math problem: since my program must - at least some times -disturb (reorder vertices) the polygon when adding (and for other user actions, removing or translating) a vertex, what is the least disturbing way to do it (for some definition of "least disturbing", e.g. leave as many vertices as possible in the same order)? $\endgroup$ Sep 9 '11 at 7:43

A keyword that will help you search for ideas is polygonization. I wrote a paper on the topic, whose idea would likely provide you with a suitable algorithm, but it is perhaps too complicated for your purposes. I will illustrate the algorithm on Henning's clever counterexample.

You want to connect $(0,0)$, the centroid of his polygon, to the closest side. Introduce two new pseudovertices on that side and stretch the boundary out to reach it (left figure below). Now remove the two pseudovertices, letting the boundary snap back like a rubber band—twang! Unfortunately now the boundary self-touches on the left and you no longer have a simple polygon (middle figure). At the offending vertex, "twang" again, to remove the double boundary contact. The result is shown in the right figure, which is perhaps the best one could hope for under the circumstances.
If you want to pursue this further, despite its intricacy, see "Connecting Polygonizations via Stretches and Twangs."

  • $\begingroup$ This is very much relevant to my issue, including other operations such as removing or moving a vertex. Thanks for your paper, that I will study carefully. $\endgroup$ Sep 10 '11 at 8:37

It is true as long as $M$ and $P$ are separated by a line. In this case, at least one side of $P$ is completely visible from $M$ and you can then replace this side by two sides going through $M$.

In general, a set of line segments that do not cross (except possibly at their extremes) can be partially sorted with respect to a point far away without cycles. This order can be found using a polar line sweep centered at that point.

See for instance Optimal point location in a monotone subdivision, TR available here.

  • $\begingroup$ Thanks for the link. Very useful. Of course, my user has no reason to keep M and P separated by a line... $\endgroup$ Sep 8 '11 at 19:51

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.