Создание набора данных для возможной интеграции в MySQL и Google Maps API для веб-сайта? (а-ля точка в многоугольнике, теорема о столкновении и т. д.)

Вот решение, которое будет эффективным и максимально простым в реализации. Заметьте, я говорю не просто, а максимально просто. Это сложная проблема, как оказалось.

1) Получите данные полигонов США с помощью шейп-файлов или KFL, которые дадут набор форм полигонов (сухопутных массивов), каждый из которых определяется списком вершин.

2) Создайте набор прямоугольников ограничивающей рамки с выравниванием по оси (AABB) для Соединенных Штатов: по одному для Аляски и каждого острова Аляски, по одному для каждого Гавайского острова, по одному для континентальной части Соединенных Штатов и по одному для каждого маленького острова у побережья США. континентальная часть США (например, остров Болд-Хед в Северной Каролине, Каталина у побережья Калифорнии). Каждая ограничивающая рамка определяется как прямоугольник с углами, которые являются минимальной и максимальной широтой и долготой для формы. Я предполагаю, что их будет несколько сотен. Например, для большого острова Гавайи широта простирается от 18°55′ северной широты до 28°27′ северной широты, а долгота — от 154°48′ западной долготы до 178°22′ западной долготы. Большинство ваших глобальных пар широта/долгота отбрасываются на этом шаге, так как они не находятся ни в одной из этих нескольких сотен ограничительных рамок. Например, ваша ограничительная рамка на 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/

В частности, взгляните на демо "poly vs poly" в середине страницы и немного поиграйте с ним. Когда вы это сделаете, вы увидите, что когда вы берете MD двух фигур, если эта MD содержит начало координат, то две формы перекрываются. Итак, все, что вам нужно сделать, это взять разность Минковского двух полигонов, которая сама по себе дает новый полигон (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!

Если вы не можете портировать это самостоятельно, возможно, вы могли бы связаться с одним из авторов двух ссылок, которые я включил здесь - они оба реализовали алгоритм MD во Flash, возможно, вы могли бы лицензировать исходный код.

5) Наконец, предполагая, что вы обработали обнаружение коллизий, вы можете просто сохранить в базе данных логическое значение, указывающее, является ли пара широта/долгота частью Соединенных Штатов. Как только это будет сделано, я не сомневаюсь, что вы сможете делать все, что хотите, со своей частью Google Maps.

Итак, подводя итог, единственной сложной частью здесь является либо 1) реализация алгоритма обнаружения столкновений GJK, либо, альтернативно, 2) написание алгоритма, который сначала вычислит разницу Минковского между вашей парой широта/долгота и многоугольником земли, содержащимся внутри ваш AABB, а затем, во-вторых, посмотрите, содержит ли этот многоугольник MD начало координат. Если вы используете этот подход, Ray Casting (типичное решение «точка в полигоне») сделает свое дело со второй частью.

Я надеюсь, что это даст вам начало в правильном направлении!

Я думаю, что этот другой вопрос отвечает на большую часть того, что вы пытаетесь сделать.

Как определить, пересекаются ли два выпуклых многоугольника?

Другая часть заключается в том, что если вы используете базу данных, я бы загрузил все полигоны рядом с вашей точкой обзора из обоих наборов (набор полигонов карты и набор других сгенерированных вами полигонов), а затем запустил вышеуказанный алгоритм на этом меньшем набор полигонов, и вы можете создать список всех полигонов в вашем наборе, которые должны быть наложены на карту.