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

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

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

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

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

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

РЕДАКТИРОВАТЬ. Поэтому кажется, что я не совсем цыпленок, чтобы потерять слабость в перспективе сделать это. Здесь я хотел бы указать желаемый результат, поскольку это особый случай и может упростить вычисление:

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

EDIT2. В настоящее время я использую библиотеку GPC (General Polygon Clipper), которая делает это очень простым!

Ответ 1

Я думаю, что вам следует делать

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

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

http://www.cs.man.ac.uk/~toby/gpc/

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

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

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

Как катиться самостоятельно, для безнадежно мазохистского

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

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

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

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

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

Ответ 2

Arash Partow FastGEO библиотека содержит реализации многих интересных алгоритмов в вычислительной геометрии. Одним из них является пересечение многоугольников. Это написано на Паскале, но оно только реализует математику, поэтому оно довольно читаемо. Обратите внимание, что вам, безусловно, потребуется немного обработать края, чтобы получить их по часовой стрелке или против часовой стрелки.

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

Ответ 3

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

Класс SqlGeometry предоставляет метод STIntersection

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

Ответ 4

Вы также можете посмотреть NetTopologySuite или даже попробовать импортировать его на сервер Sql 2008 и использовать его пространственные инструменты.

Ответ 5

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

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

Ответ 6

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

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

narozed

Ответ 7

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

Ответ 8

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

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

Ответ 9

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