6
$\begingroup$

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.

  • 0
    convexity not required2011-09-09

3 Answers 3

7

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.

  • 0
    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)?2011-09-09
4

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.
Twanging
If you want to pursue this further, despite its intricacy, see "Connecting Polygonizations via Stretches and Twangs."

  • 0
    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.2011-09-10
2

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.

  • 0
    Thanks for the link. Very useful. Of course, my user has no reason to keep M and P separated by a line...2011-09-08