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(典型的多边形点解决方案)可以完成第二部分的技巧.

我希望这能为您提供正确的方向！