可能重复:
多边形交集的简单算法
我正在寻找一个关于如何快速计算两个任意定向四边形的交点的概述(没有预设的拐角或边长约束).我不是要简单地检查它们是否相交,而是希望得到构成所得交叉区域的点.我知道通常多边形交叉不是一个小问题,并且有可用的库可以做得很好.
但是因为在这个我只关注四面形状的特殊情况下,我想知道是否有一种快速方法可以使用,而不需要在我的应用程序中包含一个完整的附加库.
到目前为止,我所想到的只有:
上述两个步骤是否最终得到了构成最终交叉区域的所有点？有更好的方法可以使用吗？
如果我能得到构成结果区域的点的正确排序,那也很好.这不是强制性的 - 如果你知道任何聪明/快速的方法(凸壳？)我会感激任何建议.
你没有说明2个quadriliterals是凸的还是没有; 如果是,你可以使用常规的凸多边形交集算法,如http://www.iro.umontreal.ca/~plante/compGeom/algorithm.html
从我可以收集到的,它不需要任何奇特的数据结构或操作,因此它应该不难实现.