计算两个四边形交点的方法？

Question

可能重复：
A simple algorithm for polygon intersection

我正在寻找如何快速计算两个任意取向四边形的交叉点的轮廓（没有预设角角或边长约束）。我是而不是只是简单地检查它们是否相交，但是希望获得组成相交区域的点。我知道一般来说多边形相交不是一个小问题，并且有可用的图书馆能够很好地工作。

但是，由于在这种特殊情况下，我只关注四个边形，我想知道是否有一个快速方法可以使用，而不需要在我的应用程序中包含整个额外的库。

到目前为止，所有我想的是：

1. 运行在两个形状“多边形点”相对于每个多边形的相互
2. 交叉边缘相互

通过上述两个步骤确定地获得组成交汇区域的所有点吗？有没有更好的方法来使用？

如果我能得到构成结果区域的点的正确排序，那么它也会是不错。这不是强制性的 - 如果你知道有什么聪明/快捷的方法来做这个（凸包？），我会很感激任何建议。

Answer 1

你没有说明2个quadriliterals是凸的还是不是;如果是的话，你可以使用常规的凸多边形交集算法，如http://www.iro.umontreal.ca/~plante/compGeom/algorithm.html

从我可以收集的信息来看，它不需要任何外来的数据结构或操作，所以它不应该很难实现。

Answer 2

凸多边形相交相对比较容易。谷歌它，SO和其他地方都有很多资源。

不是所有的四边形都是凸起的。两个非凸四边形的相交可能会导致多个不连续的多边形，只是它们的点会给你很少的点，但如果这就是你需要的，继续前进并相交每对边。它比任何一般方法都容易和快速

即使对于凸形，哑哑力方法可能会更快。你必须做一些测试来找出最适合你的东西。