Как пересечь два многоугольника?

Question

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

Входные данные:2 многоугольника (A и B) в 2D, заданные в виде списка ребер [(x0, y0, x1, y2), ...] каждый.Точки представлены парами doubles.Я не знаю, даются ли они по часовой стрелке, против часовой стрелки или вообще в каком-либо направлении.Я делай знайте, что они не обязательно выпуклые.

Выходной сигнал:3 многоугольника, представляющие A, B и пересекающийся многоугольник AB.Любой из которых может быть пустым (?) полигоном, например null.

Подсказка по оптимизации:Эти многоугольники представляют границы помещения и этажа.Таким образом, граница комнаты обычно полностью пересекается с границей этажа, если только она не принадлежит другому этажу в той же плоскости (ага!).

Я отчасти надеюсь, что кто-то уже сделал это на c # и позволит мне использовать их стратегию / код, поскольку то, что я нашел до сих пор по этой проблеме, довольно сложно.

Редактировать:Так что, похоже, я не совсем струсил из-за того, что падаю в обморок от перспективы сделать это.Я хотел бы здесь переформулировать желаемый результат, поскольку это особый случай и может упростить вычисления:

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

РЕДАКТИРОВАТЬ 2:В настоящее время я использую GPC (Общий многоугольный клипер) библиотека, которая делает это действительно простым!

Answer 1

Что, я думаю, ты должен сделать

Не пытайтесь делать это самостоятельно, если вы, возможно, можете помочь этому.Вместо этого используйте один из множества доступных алгоритмов пересечения полигонов, которые уже существуют.

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

http://www.cs.man.ac.uk /~тоби/gpc/

Что я на самом деле сделал, так это использовал алгоритм пересечения полигонов, который является частью библиотек Java2D.Возможно, вы можете найти что-то подобное в собственных библиотеках MS на C # для использования.

Есть и другие варианты, а также;ищите "polygon clipper" или "обрезка полигонов", поскольку те же базовые алгоритмы, которые обрабатывают пересечение полигонов, также, как правило, применимы для общих случаев обрезки.

Как только у вас действительно появится библиотека обрезки полигонов, вам просто нужно вычесть полигон B из полигона A, чтобы получить первую часть выходных данных, и пересечь полигоны A и B, чтобы получить вторую часть выходных данных.

Как свернуть свой собственный, для безнадежных мазохистов

Когда я рассматривал возможность создания своего собственного, я обнаружил, что алгоритм Вейлера-Атертона обладает наибольшим потенциалом для общего вырезания полигонов.Я использовал следующее в качестве ссылки:

http://cs1.bradley.edu/public/jcm/weileratherton.html

http://en.wikipedia.org/wiki/Weiler-Atherton

Детали, как говорится, слишком подробны, чтобы включать их сюда, но я не сомневаюсь, что вы сможете найти ссылки на Weiler-Atherton на долгие годы.По сути, вы разбиваете все точки на те, которые входят в конечный полигон или выходят из конечного полигона, затем формируете график из всех точек, а затем перемещаетесь по графику в соответствующих направлениях, чтобы извлечь все нужные фрагменты полигона.Изменяя способ определения и обработки полигонов "входа" и "выхода", вы можете добиться нескольких возможных пересечений полигонов (AND, ИЛИ, XOR и т.д.).

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

Answer 2

Араш Партоу Быстрый гео библиотека содержит реализации многих интересных алгоритмов в вычислительной геометрии.Пересечение полигонов - одно из них.Он написан на Pascal, но в нем реализована только математика, поэтому он довольно удобочитаем.Обратите внимание, что вам, безусловно, нужно будет немного предварительно обработать края, чтобы расположить их в порядке по часовой стрелке или против нее.

ETA:Но на самом деле, лучший способ сделать это - не делать этого.Найдите другой способ решения вашей проблемы, который не включает в себя произвольные пересечения полигонов.

Answer 3

Если вы программируете в .NET Framework, возможно, вам захочется взглянуть на класс SqlGeometry, доступный в сборках .NET, поставляемых как Типы системной среды CLR Microsoft SQL Server

Класс SqlGeometry предоставляет Пересечение способ

SqlGeometry g1 = SqlGeometry.Parse("POLYGON ((...))");
SqlGeometry g2 = SqlGeometry.Parse("POLYGON ((...))");
SqlGeometry intersection = g1.STIntersection(g2);

Answer 4

Возможно, вы также захотите взглянуть на NetTopologySuite - Сетевой топологический пакет или даже попробуйте импортировать его в Sql server 2008 и его пространственные инструменты.

Answer 5

Многоугольник полностью описывается упорядоченным списком точек (P1, P2, ..., Pn).Ребрами являются (P1 - P2), (P2 - P3), ..., (Pn - P1).Если у вас есть два многоугольника A и B, которые перекрываются, будет точка An (из списка точек, описывающих многоугольник A), которая находится в пределах области, окруженной многоугольником B, или наоборот (точка B находится в A).Если такая точка не найдена, то полигоны не перекрываются.Если такая точка найдена (т.е.Ai) проверьте соседние точки многоугольника A(i-1) и A(i+1).Повторяйте до тех пор, пока не найдете точку за пределами области или не будут проверены все точки (тогда первый полигон полностью лежит внутри второго полигона).Если вы нашли точку снаружи, то вы можете вычислить точку пересечения.Найдите соответствующее ребро многоугольника B и следуйте за ним с помощью resersed roles = теперь проверьте, лежат ли точки многоугольника B внутри многоугольника A.Таким образом, вы можете создать список точек, которые описывают перекрывающийся многоугольник.При необходимости вы должны проверить, идентичны ли полигоны, (P1, P2, P3) === (P2, P3, P1).

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

нарозед

Answer 6

Попробуйте использовать для этого ГИС-инструменты, такие как ArcObjects, TopologySuite, GEOS, OGR и т.д.Я не уверен, доступны ли все эти дистрибутивы для .net, но все они делают то же самое.

Answer 7

Клипер - это бесплатная программа с открытым исходным кодом библиотека обрезки полигонов (написана на Delphi и C ++), которая делает именно то, что вы просите - http://sourceforge.net/projects/polyclipping/

В моем тестировании Clipper работает значительно быстрее и гораздо менее подвержен ошибкам, чем GPC (смотрите более подробные сравнения здесь - http://www.angusj.com/delphi/clipper.php#features).Кроме того, несмотря на наличие исходного кода как для Delphi, так и для C ++, библиотека Clipper также включает скомпилированную DLL, чтобы упростить использование функций обрезки и на других языках (Windows).

Answer 8

Это академический документ объясняет, как это сделать.

Answer 9

Если вы осмелитесь взглянуть на чужой код GPL C ++, вы сможете увидеть, как они делают это в Inkscape:

http://bazaar.launchpad.net /~inkscape.dev/inkscape/trunk/view/head:/src/2geom/shape.cpp (строка 126)