<分区>
Possible Duplicate:
A simple algorithm for polygon intersection
我正在寻找有关如何快速计算两个任意方向的四边形(无预设角角或边长限制)的交集的大纲。我不是只是想检查它们是否相交,而是希望获得构成相交区域的点。我知道一般来说,多边形相交并不是一个小问题,并且有可用的库可以很好地完成工作。
但由于在这种特殊情况下我只关心四个边的形状,我想知道是否有一种快速方法可以使用而无需在我的应用程序中包含整个附加库。
到目前为止我想到的是:
- 在两个形状上相对于彼此运行“多边形中的点”
- 将每个多边形的每条边相互相交
上述两个步骤是否最终让我得到了构成结果相交区域的所有点?有没有更好的使用方法?
此外,如果我能得到构成结果区域的点的正确顺序,那将是很好。这不是强制性的——如果您知道任何聪明/快速的方法来做这件事(凸包?)我会很感激任何建议。