Как обнаружить внутренние вершины в группах из 2d полигонов? (Например, ZIP-коды для определения территории)
Я ищу метод, желательно на PHP, для анализа группы полигонов для обнаружения внешних границ группы.
В частности, это приложение для Google Maps v3, которое предоставляет территории. Каждый полигон на территории является почтовым индексом. Я пытаюсь обнаружить и нарисовать только границу территории. Вот макет того, что я пытаюсь выполнить:
Проблемы, с которыми я сталкиваюсь при решении этой проблемы:
- Почтовые коды на каждой территории могут быть (и часто) несмежными (см. Красную и зеленую территории в приведенном выше примере).
- ZIP-коды не обязательно выпуклые, поэтому технология выпуклого корпуса не будет работать (может быть, я ошибаюсь?)
- Хотя это похоже на изображение выше, вершины редко действительно избыточны от одного ZIP к другому. Каждая координата lat / lon (т.е. каждая вершина многоугольника) имеет 10 десятичных точек точности. Я уже пробовал и отклонял метод округления, поскольку он никогда не создавал чистый набор данных, который по-прежнему напоминал оригинальную форму.
С положительной стороны эти территории никогда не меняются после их создания. Поэтому этот процесс можно запустить в автономном режиме, чтобы вычислить и сохранить полученные полисы.
Уточнение: мои данные хранятся на уровне почтового индекса. Каждый ZIP-код определяется одним или несколькими большими наборами координат lat / lon. Каждая координата lat / lon определяет одну вершину в многоугольнике Карт Google. Как и в случае с большими территориями, каждый ZIP-код может быть или не быть выпуклым, и он может быть или не быть единственным непрерывным многоугольником. Большая территория просто хранится в виде списка ZIP-кодов; для территорий не сохраняется многоугольных данных – вот что я пытаюсь решить здесь.
Большое спасибо заранее за любые указатели в правильном направлении.