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

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

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

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

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

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

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

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

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


c# polygon intersection
person Daren Thomas    schedule 06.10.2009    source источник
comment
Это сложнее, чем вы думаете. Как вы планируете изобразить получившуюся форму? Имейте в виду, что два входа могут (а) вообще не пересекаться, (б) частично пересекаться, что приводит к выпуклой или вогнутой замкнутой форме, (в) полностью пересекаются, что приводит к форме с ДВУМЯ границами (т. Е. Бублику), где вы должны найти способ представить внутреннюю и внешнюю часть формы.   -  person Jon Seigel    schedule 06.10.2009
comment
Действительно, Джон прав. Ваша проблема плохо сформулирована; результирующий набор может не быть многоугольником, и поэтому выходные данные функции не должны быть многоугольником. Что вы хотите сделать в случае, если полученная фигура не связана? Представьте, например, С-образный многоугольник, пересекающий I-образный многоугольник, в результате чего получается двоеточие.   -  person Eric Lippert    schedule 06.10.2009
comment
спасибо, придется хорошенько подумать и придумать решение. Не думал об этом раньше ...   -  person Daren Thomas    schedule 06.10.2009
comment
И, как указал DreamWalker, невыпуклый многоугольник нельзя определить так, как вы описываете. Поместите четыре точки в квадрат, а затем одну точку в центре: вы можете создать четыре разных многоугольника в форме Pacman из этой конфигурации. Ваша проблема в нынешнем виде не решаема.   -  person StriplingWarrior    schedule 06.10.2009
comment
StriplingWarrior, вы в курсе, что я указываю края, а не только точки?   -  person Daren Thomas    schedule 07.10.2009
comment
Большинство алгоритмов для выполнения того, что вы описываете, полагаются на правило обмотки, чтобы сделать это возможным, поэтому первым шагом, вероятно, должно быть соединение всех ребер в упорядоченный набор точек с известной намоткой (чаще всего по часовой стрелке, но я видел против часовой стрелки также). Когда у вас есть упорядоченный набор точек, вы можете использовать точечные произведения и правило правой руки, чтобы быстро (хорошо в O (m * n)) найти, находится ли какая-либо точка из многоугольника A внутри многоугольника B. Это необходимое предварительное условие для определить, какую геометрию на выходе вы можете получить.   -  person Daniel Pryden    schedule 08.10.2009
comment
Вам также может быть полезно прочитать Теорию множеств точек. На этой странице описывается реализация пакета топологии JTS: docs.codehaus.org/display/GEOTDOC/. JTS делает то, что вы хотите, но написан на Java. Вы можете попробовать GEOS (порт JTS на C ++) или NetTopologySuite, упомянутый ниже: stackoverflow.com/questions/1526352/   -  person Daniel Pryden    schedule 08.10.2009
comment
В этом научном документе объясняется, как это сделать как для выпуклых, так и для невыпуклых многоугольников: gvu.gatech.edu/~jarek/graphics/papers/   -  person Charles Bretana    schedule 05.10.2011

Ответы (9)


arrow_upward
11
arrow_downward

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

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

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

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

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

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

person jprete    schedule 06.10.2009
comment
только что пересмотрел это. В конечном итоге я использовал библиотеку gpc (верхняя ссылка). это невероятно. - person Daren Thomas; 11.04.2012

arrow_upward
17
arrow_downward

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

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

person David Seiler    schedule 06.10.2009
comment
Если вы сделаете это, будьте предельно осторожны и не меняйте ничего в алгоритме исходного кода. Если возможно, получите компилятор Pascal-to-C или скомпилируйте его в библиотеку, которую вы можете использовать, вместо того, чтобы пытаться переводить код самостоятельно. - person jprete; 06.10.2009

arrow_upward
14
arrow_downward

Если вы программируете в .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);
person mloskot    schedule 11.11.2009
comment
Это неправильный ответ, поэтому он получил отрицательный ответ? Если это так, укажите, где это ошибка. - person mloskot; 04.02.2010
comment
я согласен! что не так с этим решением? Я лично делаю все свои пространственные вещи в БД ... но если вам нужно сделать это в коде, используйте тот же код :) - person Pure.Krome; 04.10.2010

arrow_upward
3
arrow_downward

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

person oharab    schedule 06.10.2009
comment
+1 за это. Я искал порт JTS для .NET, и, похоже, он отвечает всем требованиям. - person Daniel Pryden; 08.10.2009

arrow_upward
3
arrow_downward

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

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

person Angus Johnson    schedule 06.06.2010

arrow_upward
2
arrow_downward

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

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

нарезанный

person narozed    schedule 07.10.2009

arrow_upward
2
arrow_downward

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

person George Silva    schedule 08.10.2009
comment
К вашему сведению, OGR (из GDAL / OGR) использует библиотеку GEOS (trac.osgeo.org/geos) , поэтому нет никакой разницы в реализации вычислительной геометрии между этими двумя. - person mloskot; 03.02.2010

arrow_upward
2
arrow_downward

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

person Charles Bretana    schedule 05.10.2011

arrow_upward
2
arrow_downward

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

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

person fortran    schedule 06.10.2009