Как пересекаются два полигона?

Question

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

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

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

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

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

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

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

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

Answer 1

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

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

Answer 2

Если вы программируете в .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);

Answer 3

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 4

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

Answer 5

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

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

Answer 6

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

Answer 7

Полигон полностью описывается упорядоченным списком точек (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

Answer 8

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

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

Answer 9

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