c++ - 计算两个四边形相交的方法？

Question

可能重复：
多边形相交的简单算法

我正在寻找有关如何快速计算两个任意方向的四边形的交集的大纲（没有预设的角角或边长限制）。我不是要简单地检查它们是否相交，而是希望得到构成结果相交区域的点。我知道通常多边形相交不是一个微不足道的问题，并且有一些可用的库可以做得很好。

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

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

1. 在两个形状上相对于彼此运行“多边形中的点”
2. 将每个多边形的每条边彼此相交

上述两个步骤是否最终让我得到了构成结果交叉区域的所有点？有没有更好的使用方法？

如果我能得到构成结果区域的点的正确顺序，那将是很好的。这不是强制性的——如果你知道任何聪明/快速的方法来做这件事（凸壳？）我会很感激任何建议。

Answer 1

您没有说明 2 个四边形是否是凸的；如果是，您可以使用正则凸多边形相交算法，例如http://www.iro.umontreal.ca/~plante/compGeom/algorithm.html

据我所知，它不需要任何奇特的数据结构或操作，因此实现起来应该不难。

Answer 2

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

并不是所有的四边形都是凸的。两个非凸四边形的相交会导致几个不连贯的多边形，只有它们的点会给你带来很少的好处，但如果这是你需要的，请继续与每对边相交。这将比任何一般方法更容易和更快

即使对于凸形，哑蛮力方法也可能更快。您必须进行一些测试以找出最适合您的方法。