如何判断两个非零宽度的线段是否相交

Question

一条线段可以由一对点定义。有众所周知的算法可以找到在2D空间中两条线段是否相交。但如果我们通过给线段添加宽度使其变得更加棘手呢？

想象一下，你有一条由一对点和一个宽度定义的线段。你最终得到的是一个矩形，其边不一定与坐标轴对齐。（因此您不能使用标准的“矩形重叠”函数。）确定两个这样的线段是否重叠的最佳方法是什么？

- Mason Wheeler

---

我假设这不仅仅针对一对线段 - 相反，您正在寻找类似于经典扫描线算法的东西？ - Ram Rajamony

@Ram：我不熟悉“经典扫描线算法”。 - Mason Wheeler

这是一个链接，通过维基百科提供。http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf - Ram Rajamony

所以我问这个问题是因为如果你只关心两条线段的“盒子”，那么你可以将其视为十六个单独的交点问题，对吧？如果任意两对线相交，则“盒子”相交。或者我误解了问题？ - Ram Rajamony

Answer 1

我建议使用分离轴定理来判断旋转矩形（粗线段）是否重叠。这种方法快速简单。

- MBo

Answer 2

一条带宽度的线可以看作是两条平行线，它们之间相隔你所说的宽度。因此，每条带有宽度的线对应着四条线。只需计算这4条线中是否有任何交点，就完成了，不是吗？

更新：有评论指出这将忽略重叠的平行线。我认为这是它会忽略的所有情况，因此可以将其作为特殊情况处理。

- Stochastically

---

这将会漏掉重叠的平行线。 - BevynQ

@BevynQ 说得好。但我认为这是唯一遗漏的部分，所以我已经编辑了我的答案，包括你的观点。 - Stochastically

它也会错过近似平行重叠的线条。 - AndrewC

@Stochastically 这些是线段，而不是无限长的直线。请参考这张图片了解我所说的内容。粗蓝色和粗绿色的线不是平行的并且重叠在一起，但是它们两侧的（细红色和细黄色）平行线却没有交叉。 - AndrewC

@AndrewC 我相信我可以编写一些代码，从无限直线情况的四边形开始，然后限制为截断部分（即线段），以判断它们是否相交，这就是这里所问的全部。 我做的很多编程都是数学导向的。与我过去使用的一些复杂数值技术相比，这并不觉得难。但我不知道这种方法的效率会如何。新的想法，也许旋转会有所帮助实现。 - Stochastically