算法新点添加到多边形

在应用程序中，我发展我有多边形的展现在画面

我的数据结构是双链表如下。

RzCurve { 
    RzNode *head; 
}; 


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

我想实现一个算法，允许用户通过点击鼠标来添加一个新的节点。

对此有任何提示？

问候， umanga

我可能会去通过所有线段，计算distance of the point to the line段，并插入到新点的距离最短的线段的端点之间的点。此外，我只考虑线段，其中通过新点的线和垂直于通过线段的端点的线与线段相交。

2010-07-23 09:30:26

考虑的是，“进一步”的部分减少了点线的距离的复杂性 - 你将不必从点考虑距离终点。这*可能*也会给出相当于从Mau回答的结果，但更容易实施。 – phkahler 2010-07-26 21:24:47

我会穿过所有的角落对，计算平分线的2个角度。如果点击的点落入由2个平分线定义的半平面和2个角度之间的线段，则必须将该点添加到当前线段（即新点连接到检查下的2个角）。

你必须小心凹多边形。如果2个平分线相交于多边形之外，则只有当它落入由平分线和线段定义的三角形内时，该点才必须添加到当前线段。

例子：

2010-07-23 09:59:12 Mau

毛，有链接到图像？似乎是无效的。 – 2010-07-26 06:41:28

@umanga：链接断了，对不起。现在修复。 – Mau 2010-07-26 08:43:49

回答