Algorithm to add new point to a polygon

In the application I am developing I have polygons as show in the picture

My data structure is d开发者_运维问答ouble-linked list as follows.

RzCurve {
   RzNode *head;
};


RzNode{
      double x;
      double y;
      RzNode *next;
      RzNode *prev;
}

I want to implement an algorithm which allows user to add a new Node by clicking mouse.

Any tips on this?

Regards, umanga

I would probably go through all line segments, calculate the distance of the point to the line segment, and insert the point between the end points of the line segment with the shortest distance to the new point. Further I would only consider line segments where the line through the new point and perpendicular to the line through the end points of the line segment intersects the line segment.

I would go though all pairs of corners, compute the bisector to the 2 angles. If the clicked point falls into the semi-plane defined by the 2 bisectors and the segment between the 2 angles, then your point must be added to the current segment (i.e. the new point gets connected to the 2 corners under exam).

You have to be careful with concave polygons. If the 2 bisectors intersect outside the polygon, the point must be added to the current segment only if it falls inside the triangle defined by bisectors and segment.

Example:

alt text http://img265.imageshack.us/img265/2098/134073347.png