Как найти перекрывающуюся область между двумя произвольными многоугольниками

Question

Я пытаюсь создать метод, который будет принимать два произвольных списка узлов для объекта и многоугольника отсечения и выводить либо:

а) площадь перекрытия
б) список узлов для результирующего (обрезанного) многоугольника, чтобы я мог вычислить площадь

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

Я совсем не эксперт в этой области, так будет ли работать что-то вроде алгоритма Сазерленда-Ходжмана? Существуют ли какие-либо библиотеки, которые уже делают это, или я лучше всего просто реализую алгоритм, как описано в псевдокоде в Wikipedia ?

Спасибо за помощь!

Answer 1

Существуют ли библиотеки, которые уже делают это ...

Обрезка полигонов - сложная задача. Я бы не рекомендовал пытаться сделать это самостоятельно, если вы не хотите тратить на это много месяцев. В Википедии перечислено несколько библиотек отсечения (и IIRC в этом списке только Clipper бесплатно для использования в коммерческих приложениях): http://en.wikipedia.org/wiki/Boolean_operations_on_polygons#External_links

ps: я допускаю личную предвзятость к Clipper, так как я автор :) Больше информации здесь: http://angusj.com/delphi/clipper.php

Answer 2

Я обнаружил, что использование библиотеки JavaGeom работает очень хорошо. Он интегрирует код из порта Java GPC (который больше не доступен) и, таким образом, допускает произвольные операции многоугольника. Используя SimplePolygon2D и Polygon2DUtils.intersection (), я смог получить нужную операцию.

Answer 3

Попробуйте gpc .

Answer 4

Похоже на Weiler-Atherton - это то, что вам нужно:

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

Ваши полигоны соответствуют этим критериям, верно?Я не знаю насчет реализаций, но, похоже, вам лучше было бы реализовать WA, чем SH, если бы любой из ваших полигонов мог быть вогнутым.

Answer 5

Я пробовал много разных библиотек, и лучше всего работал JTS Topological Suite , который лицензирован исключительно на Java и LGPL2.