相关疑难解决方法(0)

假设平面上有许多凸多边形,也许是地图.这些多边形可以相互碰撞并共享边缘,但不能重叠.

为了测试两个多边形P和Q是否重叠,首先我可以测试P中的每个边缘以查看它是否与Q中的任何边相交.如果找到了交叉点,我声明P和Q相交.如果没有相交,那么我必须测试P完全被Q包含的情况,反之亦然.接下来,有P == Q的情况.最后,情况是共享一些边缘,但不是全部.(最后两种情况可能被认为是相同的一般情况,但这可能并不重要.)

我有一个算法,可以检测两个线段相交的位置.如果这两个段是共线的,则不会认为它们与我的目的相交.

我是否正确列举了这些案例？有关这些案件的测试建议吗？

请注意,我不是要找到交叉的新凸多边形,我只想知道交叉是否存在.有许多记录良好的算法可以找到交集,但我不需要经过所有的努力.