为网站创建数据集，最终集成到MySQL和Google Maps API中？（类似于点-多边形，碰撞定理等）

Question

我在过去几个月里学会了PHP、PDO和SQL，并按照最佳实践构建了一个基本的动态网站，包括用户注册/电子邮件激活/登录注销功能。现在我卡在了下一个任务上……

我创建了一个巨大的数据集，包含三百万以上的正方形/多边形，每个大小为1分钟的纬度和经度，在PHP数组中存储有单个坐标（左上角）。为了推断出类似正方形的形状，我只需在每个方向上添加0.016度（约1分钟）并生成其他3个坐标。

现在我需要检查该数组中的每个多边形是否至少覆盖美国的一部分土地……即如果将我的完成数据集产生图形输出并查看旧金山海岸线，他们会看到类似于this的东西。

这类似于点与多边形问题，但它处理的是另一个多边形而不是点，另一个多边形是一个国家边界，我不仅仅是在寻找交集。我想要检查：

• 一个多边形/正方形与另一个多边形相交（比如海岸线/边界）。
• 一个多边形/正方形在另一个多边形内部（比如美国大陆）。
• 一个多边形/正方形包含另一个多边形的一部分（比如小岛）。

下面是我简陋的示意图：

如果符合以下三个条件之一，我想保留这个正方形。如果它与大多边形没有任何交互（即它在水上），则丢弃它。

我想大多边形将是美国的一个shapefile，或者是一个KML文件，我可以从中剥离出坐标，从而创建一个非常复杂的多边形。

然后，我想将这些匹配的正方形和正方形ID传递给一个包含每个正方形坐标集的MySQL表格（实际上，我甚至不确定在MySQL中处理那么大的表的最佳实践，但需要时我会解决）。最终目标是使用Google Maps API通过Javascript开发地图，在我编写的网站上显示这些正方形（显然，只显示视野内的正方形，以确保不过度使用数据库）。我相当确定我必须先通过PHP传递这样的信息。但与实际制作数据集的任务相比，所有这些似乎都相对简单。

这显然是无法手动完成的，因此需要自动化。我知道一些Python，那有用吗？其他关于从哪里开始的提示？是否有人愿意为我编写一些代码？

- marked-down

---

在哪个投影下呈现的正方形？是墨卡托投影吗？请注意，墨卡托投影中相等大小的正方形在不同纬度上具有不同的大小。另外请注意，在地理投影中，每个纬度上的正方形数量也会不同。此外，请考虑仅保存一个角的坐标，您可以根据需要计算其他角的坐标。 - Olexa

很可能是墨卡托投影，我相信这就是Google地图的编码方式。你提到的坐标系很有道理...但是我该如何首先生成多边形呢？ - marked-down

如果多边形中的任何一个点在矩形内部，或者矩形的任何一个角落在多边形内部，则矩形与多边形相交。请参考以下链接以检查一个点是否在多边形内部：https://dev59.com/p3VC5IYBdhLWcg3wrDJd。当然，检查一个点是否在矩形内部要容易得多（只需比较坐标）。 - Olexa

到目前为止，我没有太多的线索。我有一个PHP数组，其中包含每个正方形分钟的单个左上坐标。它的布局如下：Array => (0 => (0 => latCoords 1 => longCoords), 1 => (0 => latCoords 1=> longCoords))等等。我一直在查看一些形状文件/钥匙孔标记文件，但似乎没有我需要的分辨率，并且在近距离查看时太过锯齿状。 - marked-down

我并不太了解这个问题的具体细节（数据结构等），但我想知道是否检查正方形中是否“没有任何东西”比检查多边形可能部分“在”正方形中的所有情况更容易。我还没有详细考虑过这个问题，但我觉得这种方法可能会减少任务的复杂性（至少在你的脑海中 :-P）。 - kutschkem

Answer 1

我认为这个问题的另一个答案可以回答你所尝试做的大部分内容。

另外一个需要注意的是，如果您正在使用数据库，则应该从两个集合中加载所有靠近视点的多边形（地图多边形和您生成的其他多边形），然后在这些较小的多边形集合上运行上述算法，并生成您应该在地图上覆盖的所有多边形的列表。 参考链接：如何确定两个凸多边形是否相交？

- Daniel Williams

---

将此与查找凸边界多边形的方法相结合，您就可以得到一个近似解（我怀疑美国陆地是凸的 :-P）。 - kutschkem

Answer 2

这里有一个高效的解决方案，尽可能简单易行。需要注意的是，我并不是说这很简单，而是尽可能简单。事实证明，这是个棘手的问题。

1）使用Shapefiles或KFL获取美国多边形数据，将得到一组由顶点列表定义的多边形形状（陆地质量）。

2) 为美国创建一组轴对齐的边界框（AABB）矩形：一个用于阿拉斯加和每个阿拉斯加岛，一个用于每个夏威夷岛屿，一个用于大陆美国，以及一个用于大陆美国沿海的每个小岛（例如，北卡罗来纳州的鲍德头岛，加利福尼亚州海岸的卡塔利娜岛等）。每个边界框都定义为一个矩形，其角是形状的最小和最大纬度和经度。我的猜测是会有几百个这样的矩形。例如，对于夏威夷的大岛，纬度范围为18°55′N至28°27′N，经度范围为154°48′W至178°22′W。在此步骤中，大多数全球纬度/经度对都被丢弃，因为它们不在那几百个边界框中的任何一个中。例如，您在大西洋拉斯帕尔马斯附近的10°20'W，30°40'N（一个点）的边界框不与夏威夷重叠，因为10°20'W小于154°48′W。这部分可以很容易地用Python编码。

3) 如果经纬度对与数百个AABB矩形之一重叠，则需要将其针对该AABB矩形内的单个多边形进行测试。为此，强烈建议使用Minkowski Difference（MD）。请先彻底查看此网站：

http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/

请注意页面中间的“多边形对多边形”演示，试着操作一下。当你这样做时，你会发现，当你对两个形状进行MD运算时，如果MD包含原点，则这两个形状是重叠的。所以，你需要做的就是取出两个多边形的明科夫斯基差，这本身会得到一个新的多边形（在演示中为B - A），然后查看该多边形是否包含原点。

4) 有许多关于实现MD算法的论文在线上，但我不知道你是否有能力阅读论文并将其转化为代码。由于对两个多边形进行MD运算（即你正在测试的经纬度矩形和包含在边界框中重叠的多边形）需要复杂的向量数学，而你告诉我们你的经验水平还不高，因此我建议使用已经实现MD甚至更好的碰撞检测库。例如：

http://physics2d.com/content/gjk-algorithm

在这里，您可以看到相关的伪代码，您可以将其移植到Python中：

if aO cross ac > 0 //if O is to the right of ac
    if aO dot ac > 0 //if O is ahead of the point a on the line ac
        simplex = [a, c]
        d =-((ac.unit() dot aO) * ac + a)
    else // O is behind a on the line ac
        simplex = [a]
        d = aO
else if ab cross aO > 0 //if O is to the left of ab
    if ab dot aO > 0 //if O is ahead of the point a on the line ab
        simplex = [a, b]
        d =-((ab.unit() dot aO) * ab + a)
    else // O is behind a on the line ab
        simplex = [a]
        d = aO
else // O if both to the right of ac and to the left of ab
    return true //we intersect!

如果您自己无法移植这个程序，也许您可以联系我在这里提供的两个链接中的任何一位作者 - 他们都在Flash中实现了MD算法，也许您可以获得源代码许可证。

最后，假设您已经处理了碰撞检测，您可以简单地在数据库中存储一个布尔值，表示纬度/经度对是否属于美国。完成后，我相信您将能够按照自己的意愿使用Google Maps功能。

因此，总之，这里唯一困难的部分是要么1）实现GJK算法进行碰撞检测，或者2）编写一个算法，首先计算您的纬度/经度对与包含在AABB内的陆地多边形之间的Minkowski差异，然后第二步查看该MD多边形是否包含原点。如果您使用这种方法，射线投射（典型的点在多边形中的解决方案）将与第二部分一起完成。

希望这能为您指明正确的方向！

- J.T. Taylor

---

谢谢你...你已经为我概括了问题的几个步骤！我认为我需要阅读很多数学知识，然后正确编写代码是另一回事，所以我可能会尝试联系你提供的资源的一些作者。再次感谢！ - marked-down

太棒了，很高兴你觉得有帮助！一旦你编写了MD或GJK算法，你可以考虑将其放在GitHub上，因为它将是一个非常有用的代码片段，我相信目前在开源社区中还不存在。如果你这样做了，你可能会成为一个英雄！ - J.T. Taylor