1

我正在制作一个程序,通过单击一系列点来选择画布内的一个区域。单击的点通过一些线以这种方式链接:每个新点都与第一个和最后一个点链接。我正在寻找一种计算所得多边形面积的算法。

交叉点是允许的,这就是复杂性,因此算法必须通过根据单击点的有序序列找到多边形并计算其面积来管理这种情况。

经过多次搜索,我发现最好的是http://sigbjorn.vik.name/projects/Triangulation.pdf,但我需要在 Processing.js 中更容易实现的东西。

4

1 回答 1

0

首先切割它们相交的线段。如果输入集很小,您可以简单地检查每一对。否则使用 R-Tree。然后计算约束(Delaunay)三角剖分。然后使用光线拍摄确定内部三角形并总结它们的面积。

hth

于 2011-12-31T17:28:13.207 回答