php - 为网站最终集成到 MySQL 和 Google Maps API 中创建数据集？ (多边形中的点、碰撞定理等)

Question

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

我创建了一个巨大的正方形/多边形数据集(超过 300 万)，每 1 分钟的纬度和经度大小，存储在具有一组坐标(左上角)的 PHP 数组中。要推断出类似正方形的形状，我只需在每个方向上添加 0.016 度(约 1 分钟)并生成其他 3 个坐标。

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

它类似于多边形中的点问题，除了它处理的是另一个多边形而不是一个点，另一个多边形是国家边界，我不只是在看交叉点。我想检查是否:

• 多边形/正方形与多边形相交。 (想想海岸线/边界)。
• 多边形/正方形位于多边形内部。 (想想美国大陆)。
• 多边形/正方形包含多边形的一部分。 (想想小岛)。

这是用我粗略绘制的图像来说明的:

如果满足这三个条件中的任何一个，我就想保留这个方 block 。如果它无论如何都不与大多边形交互(即它在水面上)，则丢弃它。

我当时认为大多边形将是美国的 shapefile，或者我可以从中去除坐标以创建非常复杂的多边形的 KML 文件。

然后，我想我会将这些匹配的正方形和正方形 ID 通过 传递到一个 csv 文件以进行整合 到包含每个正方形的一组坐标的 MySQL 表中(事实上，我甚至不确定在 MySQL 中处理这种大小的表的最佳实践，但我会在需要时讨论)。最终的目标是通过 Javascript 使用 Google Maps API 开发 map ，以在我正在编码的网站上的 map 上显示这些方 block (显然只在视点内显示方 block 以确保我不会对我的数据库征税至死).我很确定我也必须首先通过 PHP 传递此类信息。但与实际制作所述数据集的任务相比，所有这些似乎都相对容易。

这显然是手工无法完成的事情，因此需要自动化。我知道一点 Python，那会有帮助吗？关于从哪里开始的任何其他提示？有人愿意为我写一些代码吗？

Answer 1

这是一个高效且实现起来尽可能简单的解决方案。请注意，我不是说简单，而是尽可能简单。事实证明，这是一个棘手的问题。

1) 使用 Shapefile 或 KFL 获取美国多边形数据，这将产生一组多边形形状(陆地 block )，每个形状由一个顶点列表定义。

2) 为美国创建一组轴对齐边界框 (AABB) 矩形:一个用于阿拉斯加和每个阿拉斯加岛屿，一个用于每个夏威夷岛，一个用于美国大陆，一个用于每个小岛美国大陆的海岸(例如，北卡罗来纳州的秃头岛，加利福尼亚海岸外的卡塔利娜)。每个边界框都被定义为一个矩形，其角是形状的最小和最大纬度和经度。我的猜测是会有几百个这样的。例如，夏威夷的大岛，纬度为 18°55′N 至 28°27′N，经度为 154°48′W 至 178°22′W。您的大多数全局纬度/经度对在这一步都会被丢弃，因为它们不在这几百个边界框中的任何一个中。例如，您位于西经 10°20'、北纬 30°40'(大西洋中靠近非洲拉斯帕尔马斯的一个点)的边界框不与夏威夷重叠，因为西经 10°20' 小于西经 154°48' .这一点很容易用 Python 编写。

3) 如果纬度/经度对确实与数百个 AABB 矩形之一重叠，则您需要针对 AABB 矩形内的单个多边形对其进行测试。为此，强烈建议使用闵可夫斯基差分 (MD)。请先彻底查看此网站:

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

特别是，请查看页面中间的“多边形与多边形”演示，并稍微玩一下。当您这样做时，您会看到当您获取 2 个形状的 MD 时，如果该 MD 包含原点，则这两个形状重叠。因此，您需要做的就是获取 2 个多边形的 Minkowski 差分，它本身会产生一个新的多边形(演示中为 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 算法，也许您可​​以许可源代码。

5) 最后，假设您已经处理了碰撞检测，您可以简单地将一个 bool 值存储在数据库中，以判断纬度/经度对是否属于美国。一旦完成，我相信您将能够随心所欲地使用您的 Google map 作品。

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

我希望这能让您朝着正确的方向迈出第一步!