计算两个任意形状的并集
我正在开发一个应用程序，我需要能够组合用户绘制的两个重叠的任意形状。这将是对两个形状的联合操作。最终的形状将是两个重叠形状的轮廓。
这些形状以顺时针方式存储为点序列。
理想情况下，我想要一个算法，该算法将采用两个点数组（x，y）并返回结果形状的单个数组。
我一直在阅读关于多边形的布尔运算的维基百科，其中提到了扫线算法，但我无法将其与我的目标联系起来，唉，我不是数学家。
我正在使用 ActionScript 3 开发应用程序，但我熟悉 C#、Java，并且可以选择 C 和 C++。
I'm working on an application, I need to be able to combine two overlapping arbitrary shapes as drawn by the user. This would be a Union operation on the two shapes. The resultant shape would be the silhouette of the two overlapping shapes.
The shapes are stored as a sequence of points in a clockwise manner.
Ideally I'd like an algorithm which will take two arrays of Points (x,y) and return a single array of the resultant shape.
I've been reading Wikipedia on Boolean operations on polygons which mentions the Sweep line algorithm but I can't make the link between this and my goal, alas I'm not a Mathematician.
I'm developing the application in ActionScript 3 but I'm familiar with C#, Java and I can pick my way through C and C++.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
正确实现布尔运算并非易事；幸运的是，有些库已经实现了此功能。
您使用什么语言？如果是 C++，请查看CGAL，计算几何算法库。
Implementing boolean operations correctly is not trivial; fortunately, there are libraries that already implement this functionality.
What language are you using? If it's C++, take a look at CGAL, the Computational Geometry Algorithms Library.
给定两个点列表（A 和 B）
- [ 1 ] A 中的每条线是否与 B 中的线相交
-.- [2] 如果没有（更多）线相交，则不存在重叠
-.- [3] 如果 (A) 中的一条线与 B 中的一条线相交则
-.-.- [4] 将交点添加到输出中
-.-.- [5] A 的下一行是否与 B 相交
-.-.-.- [6] 如果没有，请将其添加到输出（位于 B 内部）转到 5
-.-.-.- [7] 如果是这样，将相交添加到输出并切换列表 A & B goto 2
另请参阅两条线的交点。我不会写代码，抱歉:)
Given two lists of points (A and B)
- [ 1 ] for each line in A does it intersect a line in B
-.- [2] if no (more) lines intersect, there is no overlap
-.- [3] if a line in (A) intersects a line in B then
-.-.- [4] add the point of intersection into output
-.-.- [5] does the next line from A intersect B
-.-.-.- [6] if not, add this to output (it's inside B) goto 5
-.-.-.- [7] if so, add the intersect to output and switch lists A & B goto 2
Also see Intersection Point Of Two Lines. I'm not gonna write the code sorry :)
另请参阅 GPC。
See also GPC.
此算法对您有用吗？
Would this algorithm work for you?
怎么样：
我想如果你继续沿着当前的形状蜿蜒，寻找交叉点，那应该会达到你想要的效果。我认为这也应该能够处理凹形形状......
我确信一旦您掌握了基础知识，您就可以添加很多优化。
How about:
I think if you keep winding along whichever shape is current, looking for intersections, that should do what you want. I think that should cope with concave shapes as well...
I'm sure there are a lot of optimisations you can add once you've got the basics working.
似乎还有一个 javascript api：
https://github.com/bjornharrtell/jsts/
其中似乎实现了 jts 标准，并且有几种不同的实现：
http://tsusiatsoftware.net/jts /jts-links.html#ports
所有这些都应该能够执行联合等：
http://tsusiatsoftware.net/jts/JTSUser/contents.html
但在我看来，csg.js 是最令人印象深刻的项目
https://github.com/evanw/csg.js
There seems to be also a javascript api:
https://github.com/bjornharrtell/jsts/
which seems to implement the jts standard and has several differnt implementations:
http://tsusiatsoftware.net/jts/jts-links.html#ports
all of them should be able to perform union etc:
http://tsusiatsoftware.net/jts/JTSUser/contents.html
But csg.js is the most impressive project IMO
https://github.com/evanw/csg.js