计算复杂（自相交）多边形的面积
我正在制作一个程序，通过单击一系列点来选择画布内的区域。单击的点通过一些线以这种方式链接：每个新点都与第一个和最后一个点链接。我正在寻找一种计算所得多边形面积的算法。
允许交叉，这就是复杂性，因此算法必须通过根据单击的点的有序序列找到多边形并计算其面积来管理这种情况。
经过多次搜索，我发现最好的是这个 http://sigbjorn.vik.name/projects /Triangulation.pdf，但我需要在Processing.js中更容易实现的东西。
I'm making a program that selects an area within a canvas by clicking a sequence of points. The points clicked are linked by some lines this way: every new point is linked with the first and the last ones. I'm looking for an algorithm that computes the area of the resulting polygon.
Intersections are allowed, and here is the complexity, so the algorithm must manage this case by finding the polygon according to the ordered sequence of points clicked and calculating its area.
After many searches, the best I've found is this http://sigbjorn.vik.name/projects/Triangulation.pdf, but I would need something easier to implement in Processing.js.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
首先将线段相交的地方剪掉。如果输入集很小，您可以简单地检查每一对。否则使用 R 树。然后计算约束（Delaunay）三角剖分。然后使用射线射击确定内部三角形并求出它们的面积。
哈
First cut the line segments where they intersect. If the input set is small, you can simply check every pair. Otherwise use an R-Tree. Then compute a constrained (Delaunay) Triangulation. Then determine the inner triangles using rayshooting and sum up their areas.
hth