У меня проблема с двумерной вычислительной геометрией / ГИС, которая, на мой взгляд, должна быть распространена, и я надеюсь найти какой-нибудь существующий код / библиотеку для использования.
Проблема состоит в том, чтобы проверить, какое подмножество большого набора (тысяч) маленьких полигонов пересекается с одним большим полигоном. (Под «маленьким» и «большим» я подразумеваю количество пространства, которое покрывают многоугольники, а не количество точек, которые их определяют, хотя в целом предположим, что число точек, определяющих многоугольник, примерно пропорционально его геометрическому размеру И чтобы дать чувство меры, представьте, что «большой» - это многоугольник для штата в Соединенных Штатах, а «маленький» - как многоугольник для города.)
Предположим, что простое решение, использующее стандартную функцию CheckIfPolygonsIntersect (P, p), которая вызывается для каждого маленького многоугольника p относительно одного большого многоугольника P, слишком медленное. Кажется, что есть способы предварительно обработать большой многоугольник, чтобы сделать проверку пересечения для большинства маленьких многоугольников тривиальной. В частности, кажется, что вы могли бы создать небольшой набор прямоугольников, которые частично / почти заполняют большой многоугольник. Точно так же вы можете создать небольшой набор прямоугольников, которые частично / почти заполняют область ограничительной рамки большого многоугольника, которая на самом деле не находится внутри большого многоугольника. Тогда подавляющее большинство ваших маленьких полигонов может быть тривиально включено или исключено: если они полностью выходят за границу прямоугольника большого полигона, они исключаются. Если они полностью находятся внутри границы одного из внутренних-ограничивающих-прямоугольных-но-наружных-многоугольных участков, они исключаются. Если какой-либо из их пунктов находится в пределах одного из внутренних правил, они включены. И только если ничего из вышеперечисленного не применимо, вы должны вызывать функцию CheckIfPolygonsIntersect (P, p).
Это известный алгоритм? Знаете ли вы о существующем коде для вычисления разумного набора внутренних / внешних прямоугольников для произвольных (выпуклых или вогнутых) многоугольников? Прямоугольники не должны быть идеальными во всех случаях; они просто должны заполнить большую часть многоугольника и большую часть внутренней прямоугольной области, но внешней области многоугольника.
Вот простой план того, как я могу вычислить эти прямоугольники:
- возьмите ограничивающий прямоугольник большого многоугольника и нарисуйте, скажем, сетку точек 10x10 над ним
- для каждой точки, определить, находится ли она внутри или снаружи многоугольника
- «растут» каждую точку в прямоугольник, итеративно расширяя ее в каждом из четырех направлений, пока одно из ребер прямоугольника не пересекает одно из ребер многоугольника, и в этом случае вы зашли слишком далеко (это на самом деле было бы сделано в итерация типа «бинарный поиск», так что всего за несколько итераций вы можете найти правильное количество для расширения в каждом направлении, и, конечно, возникает вопрос, максимизировать ли края по одному или согласованно друг с другом)
- любая еще не развернутая точка сетки, которая покрывается расширением другой точки, просто исчезает
- когда все точки были расширены (или исчезли), у вас есть набор внутренних и внешних прямоугольников
Конечно, некоторые сумасшедшие вогнутые формы для большого многоугольника могут привести к появлению плохих / маленьких прямоугольников. Но если предположить, что полигоны в основном разумны (например, они были формами штатов США), кажется, что вы получили бы хороший набор прямоугольников и могли бы значительно оптимизировать те тысячи проверок пересечения, которые вы впоследствии сделаете .
Есть ли имя (и код) для этого алгоритма?
Редактировать: Я уже использую квад-дерево для определения маленьких многоугольников, которые могут пересекаться с ограничивающим прямоугольником большого многоугольника. Таким образом, проблема заключается в проверке того, какой из тех многоугольников действительно пересекается с большим многоугольником.
Спасибо за любую помощь.