c++ - 检查多边形是否在 C++ 中相交

Question

我有两个多边形，其最小值和最大值、纬度和经度如下:

Polygon A: minimum_latitude=2.089 degree, maximum_latitude=2.93 degree, minimum_longitude=-122.95 degree, maximum_longitude=-122.85 degree

Polygon B: minimum_latitude=2.1 degree, maximum_latitude=2.83 degree, minimum_longitude=-121.95 degree, maximum_longitude=-120.85 degree

如何在 C++ 中检查多边形 A 是否与多边形 B 相交(或包含在其中)？

我的纬度和经度是度数。我是否需要将它们转换为弧度以检查多边形是否相交？

检查交集的一种方法是检查多边形 B 的最小纬度是否位于多边形 A 的最小纬度和最大纬度之间，反之亦然？这是正确的检查方法吗？我是否需要将纬度和经度转换为弧度以执行相交测试。

Answer 1

不需要任何外部库等。

1. 按照 Constantin 的建议，通过范围检查排除不相交的多边形
2. 通过在两个方向上再次进行简单的范围检查，检查 poly1 的任何点是否在 poly2 的内部。如果有它们相交，如果全部相交则包含它。
3. 控制相反的一组 2
4. 使用 2 和 3 的结果准备候选线，然后从一个多边形发送一条射线到另一个多边形的线。如果有任何命中，它们是相交的。

就是这样。

这是最简单快捷的方法。如果您想要通过使用排序数据或八叉树等进行多项优化是可能的。