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.
Best Answer
A counterexample is the (nonconvex) octagon with vertices
You cannot add the point (0,0) between any two of the points without creating an intersection.