创建数据集以便最终集成到网站的MySQL和Google Maps API中？(la多边形点,碰撞定理等)

Question

在过去的几个月里,我一直在自学PHP,PDO和SQL,并建立了一个基本的动态网站,其中包含用户注册/电子邮件激活/登录注销功能,遵循PHP/SQL最佳实践.现在我坚持下一个任务......

我创建了一个巨大的正方形/多边形数据集(300万+),每个纬度和经度的1分钟,存储在一个PHP数组中,有一组坐标(左上角).为了推断一个方形的形状,我只需向每个方向添加0.016度(~1分钟)并生成其他3个坐标.

我现在需要检查所述阵列中的每个多边形是否至少在美国的一部分土地上....即,如果要生成我完成的数据集的图形输出并查看圣弗朗西斯科海岸线,他们会看到类似这样.

它类似于多边形点问题,除了它处理另一个多边形而不是一个点,另一个多边形是一个国家边界,我不只是看交叉点.我想检查一下:

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

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

如果它符合这三个条件中的任何一个,我想保留正方形.如果它无论如何都不与大多边形相互作用(即它在水面上),则丢弃它.

我以为大的多边形将是美国的shapefile,或者是一个KML文件,我可以从中删除坐标以创建一个非常复杂的多边形.

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

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

Answer 1

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

\n\n

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

\n\n

2) 为美国创建一组轴对齐边界框 (AABB) 矩形：一个用于阿拉斯加和每个阿拉斯加岛屿，一个用于每个夏威夷岛屿，一个用于美国大陆，一个用于美国海岸附近的每个小岛。美国大陆（例如北卡罗来纳州的秃头岛、加利福尼亚州海岸外的卡塔利娜岛）。每个边界框被定义为一个矩形，其角是形状的最小和最大纬度和经度。我的猜测是会有几百个。例如，对于夏威夷大岛，纬度为 18\xc2\xb055\xe2\x80\xb2N 到 28\xc2\xb027\xe2\x80\xb2N，经度为 154\xc2\xb048\xe2\ x80\xb2W 到 178\xc2\xb022\xe2\x80\xb2W。大多数全局纬度/经度对都在此步骤中被丢弃，因为它们不在这几百个边界框中的任何一个中。例如，位于 10\xc2\xb020\'W、30\xc2\xb040\'N（位于非洲拉斯帕尔马斯附近的大西洋中的一个点）的边界框不会与夏威夷重叠，因为 10\xc2\xb020\' W 小于 154\xc2\xb048\xe2\x80\xb2W。这一点很容易用 Python 编写。

\n\n

3) 如果纬度/经度对确实与数百个 AABB 矩形之一重叠，则需要针对AABB 矩形内的单个多边形对其进行测试。为此，强烈建议使用 Minkowski Difference (MD)。请先仔细阅读本网站：

\n\n

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

\n\n

特别是，请查看页面中间的“多边形与多边形”演示，并稍微尝试一下。当你这样做时，你会发现当你获取两个形状的MD时，如果该MD包含原点，那么这两个形状是重叠的。因此，您需要做的就是获取两个多边形的 Minkowski Difference，这本身会产生一个新的多边形（演示中的 B - A），然后查看该多边形是否包含原点。

\n\n

4）网上有很多关于实现MD的算法的论文，但我不知道你是否有能力阅读论文并将其转化为代码。由于获取两个多边形（您正在测试的纬度/经度矩形，以及与纬度/经度矩形重叠的边界框中包含的多边形）的 MD 是很棘手的向量数学，并且您已经告诉我们您的经验水平还不高，我建议使用已经实现MD的库，或者更好的是实现碰撞检测。

\n\n

例如：

\n\n

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

\n\n

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

\n\n

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

\n\n

如果您无法自己移植它，也许您可​​以联系我在此处包含的 2 个链接的作者中的任何一个 - 他们都在 Flash 中实现了 MD 算法，也许您可​​以许可源代码。

\n\n

5) 最后，假设您已经处理了碰撞检测，您可以简单地在数据库中存储一个关于纬度/经度对是否属于美国的布尔值。一旦完成，我毫不怀疑您将能够对您的 Google 地图作品进行您想要的操作。

\n\n

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

\n\n

我希望这能让您朝着正确的方向开始！

\n