logo标签列表

一条直线与一个凹多边形的交点 3D

performancealgorithmcomputational-geometry
3
我的问题是如何判断一个凸多边形或凹多边形与一个矩形多边形在3D空间中是否有非空交集。每个多边形由有序轮廓点集定义（如果点p1在点p2之后/之前，则存在边p1-p2）。
很容易找到两个多边形平面的交线，因此问题在于找到一条直线和有限多边形的交点，并确定得到的交点是否有公共部分。我找到了关于直线和凸多边形相交的算法，但我找不到任何关于凹多边形一般情况的算法。
有什么建议吗？ 谢谢。
3个回答
1

找到平面交线与两图形每条边的交点。从那里开始，只需查看线上点的顺序以检查是否有重叠即可解决问题。

当然，它们共面的特殊情况是完全不同的问题...

0
通常情况下，凹多边形的相交/包含等查询没有快速解决方案。
一般的解决方案是将多边形三角剖分成一系列凸三角形，然后使用这些三角形运行相交测试。
0

如果您可以依赖于多边形是平面的，您可以先将线与平面相交，然后将交点转换为平面的坐标系。

假设您还转换了多边形的所有顶点，现在的问题是确定2D交点是否在2D多边形内。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接