7

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

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

我现在需要检查所述阵列中的每个多边形是否至少在美国的某些土地上......即如果要生成我完成的数据集的图形输出并查看旧金山海岸线，他们会看到这样的东西。

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

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

用我粗略绘制的图像说明了这一点：

这并不容易！

如果它符合这三个条件中的任何一个，我想保留正方形。如果它无论如何都不与大多边形交互（即它在水面上），则丢弃它。

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

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

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

4

2 回答 2

3

我认为this other question回答了你正在尝试做的很大一部分

如何确定两个凸多边形是否相交？

另一部分是，如果您使用的是数据库，我会从两个集合（地图多边形的集合和您生成的其他多边形的集合）加载您视点附近的所有多边形，然后在这个较小的一组多边形，您可以生成一组应覆盖在地图上的所有多边形的列表。

于 2013-03-01T00:21:48.420 回答
3

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

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 差分 (MD)。请先彻底检查本网站：

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

特别是，请查看页面中间的“poly vs poly”演示，并试一试。当你这样做时，你会看到当你取两个形状的 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!

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

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

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

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

于 2013-03-01T01:23:18.587 回答