我创建了一个巨大的正方形/多边形数据集(300万),每1分钟的纬度和数字.经度大小,存储在具有一组坐标的PHP数组中(左上角).为了推断一个方形的形状,我只需向每个方向添加0.016度(~1分钟)并生成其他3个坐标.
我现在需要检查所述阵列中的每个多边形是否至少在美国的一部分土地上….即,如果要生成我完成的数据集的图形输出并查看圣弗朗西斯科海岸线,他们会看到像this这样的东西.
它类似于多边形点问题,除了它处理另一个多边形而不是一个点,另一个多边形是一个国家边界,我不只是看着交叉点.我想检查一下：
>多边形/正方形与多边形相交. (想想海岸线/边境).
>多边形/正方形位于多边形内. (想想美国大陆).
>多边形/正方形包含多边形的一部分. (想想小岛).
这用粗略绘制的图像说明：
如果它符合这三个条件中的任何一个,我想保持正方形.如果它无论如何都不与大多边形相互作用(即它在水面上),则丢弃它.
我认为大多边形将是美国的形状文件,或者是KML文件,我可以从中删除坐标以创建非常复杂的多边形.
然后,我想我会将这些匹配的正方形和方形ID传递给csv文件,以便集成到包含每个方块的一组坐标的MysqL表中(事实上,我甚至不确定处理表的最佳实践在MysqL中的那个大小,但我会在需要时得到它).最终的目标是使用谷歌地图API通过Javascript开发地图,在我正在编码的网站上的地图上显示这些方块(显然只在视点内显示方块,以确保我不会将我的数据库纳入死亡).我很确定我也必须首先通过PHP传递这些信息.但与实际制作所述数据集的任务相比,所有这些似乎都相对容易.
这显然是无法手工完成的,因此需要自动化.我知道一点Python,那会有帮助吗？关于从哪里开始的任何其他提示？有人愿意为我写一些代码吗？
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与poly”演示,并稍微玩一下.当你这样做时,你会看到当你获取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!
如果你自己无法移植它,也许你可以联系我在这里包含的2个链接的作者 – 他们都在Flash中实现了MD算法,也许你可以许可源代码.
5)最后,假设您已经处理了碰撞检测,您可以简单地在数据库中存储一个布尔值,以确定纬度/经度对是否属于美国.完成后,我毫不怀疑您可以按照自己的方式使用Google地图.
因此,总而言之,这里唯一的难点是：1)实现碰撞检测GJK算法,或者2)编写一个算法,首先计算你的纬度/长度对和包含在内的陆地多边形之间的Minkowski差值你的AABB,然后再看看MD多边形是否包含原点.如果使用这种方法,Ray Casting(典型的多边形点解决方案)可以完成第二部分的技巧.
我希望这能为您提供正确的方向！
