Is it always possible to simply expand a simple 2D polygon with any point? 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: 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.
A: 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."
A: 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.
