Линии к полигонам

11

Мне не удалось найти «имя» алгоритма, который позволял бы преобразовывать линии в полигоны. Поскольку эта проблема пересекает ГИС и области вычислительной геометрии и информатики. Я не уверен, что еще добавить в смесь. Я не хочу приводить список того, что я искал, так как я также хотел бы знать, что другие люди считают своим первым критерием поиска.

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

Извините за любые расплывчатые описания, но, как я уже сказал, я не хочу направлять возможные решения по пути, который я уже посетил, поскольку меня интересует «первая мысль» так же, как и окончательное решение.

polygon algorithm geometry-conversion Герман Каррильо
источник
Могут ли линии совпадать? Могут ли линии пересекаться? (то есть он чистый?) Если это так, я надеюсь, что вызов этого процесса не будет слишком специфичным для приложения.
Кирк Куйкендалл
Линии совпадений Кирка и другие «дефекты» были бы удалены до создания полигонов ... Я пытаюсь найти «имя алгоритма», которое, я уверен, было реализовано в различных пакетах ГИС (например, arcgis). Итак, короче говоря, учтите, что все вырожденные условия были рассмотрены, и у вас остались чистые линии (2 точечные линии), которые совпадают в узлах, которые вы должны иметь возможность строить полигоны. Ключ в том, что линии существуют, вырожденных условий нет, и промежуточное пространство необходимо преобразовать в полигоны. Спасибо
Точки на плоскости или на сфере?
Кирк Куйкендалл
Кирк ... На плоскости, метрика х, у координаты, а не сферические координаты. Например, скажем, у вас есть отрезки, которые будут формировать диаграмму Вороного, но все, что у вас есть, это сегменты, которые формируют это, а не фактическая структура данных, которая привела к этому. Короче говоря, каждый сегмент связан, и каждый сегмент уникален.

Ответы:

4

Возможно, "заполнить область"? Смотрите здесь и здесь .

редактировать

Другая возможность - ограниченная триангуляция . (Ссылка на апплет Java, который позволяет рисовать график с помощью мыши, а затем иллюстрирует алгоритм развертки плоскости для его триангуляции.) Результат любой такой триангуляции, независимо от того, как она выполняется, может быть легко обработан для создайте нужные полигоны: просто объедините все соседние треугольники, которые имеют только что созданное ребро.

пример

Исходный график:

Исходный график

Триангулированный график:

введите описание изображения здесь

Whuber
источник
Билл собирается голосовать, так как я не сталкивался с этим ... не желая ограничивать другие комментарии от людей в различных дисциплинах.
Хотя в основном это касается растровых заливок, это самый близкий ответ. У меня до сих пор нет имени алгоритма, если он не присоединен ни к растру, ни к вектору, но алгоритм «развертки» может быть достаточным, но я не могу понять, почему координаты сортируются по Y, а не по X ( что легко реализовать на большинстве языков).
@ Дан Сортировка по y или x несущественна, как вы предлагаете. Вы также правы в том, что задействованы алгоритмы плоской развертки или развертки линии, но, к сожалению, это общий метод, который охватывает почти все процедуры вычислительной геометрии, поэтому он не подходит для поиска специально для вашего алгоритма. Обратите внимание, что эта конкретная проблема не является чисто теоретико-графовой, потому что она включает в себя вложение полилинейного комплекса в плоскость (или сферу), и поэтому хороший алгоритм должен хранить информацию о внедрении: вот почему это действительно проблема заполнения области в душе.
whuber
5

В теории графов эта операция называется вычислением граней . Это связано с вычислением двойственного заданного графа.

Например, в Java-библиотеке GeOxygène у графа (называемого CarteTopo ) есть метод getFaces для извлечения его лица .

Это называется полигонизация в JTS

жюльен
источник
Хорошие ссылки. Тем не менее, все они предполагают, что проблема @ Дана уже решена: возможность назвать график «плоским» означает, что вы уже определили полигональные грани. Он хочет знать, как происходит преобразование произвольного набора дуг (в плоскости) в планарный граф честности к доброте. Это требует построения представления его «топологии», такой как DCEL.
whuber
Спасибо большое, ты - источник знаний! Интересно, как кто-то может быть таким блестящим.
Жюльен
4

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

В частности, алгоритм «сопоставления концов» RepRap обрабатывает множество патологических случаев.

Увы, программное обеспечение RepRap предполагает, что каждый угол имеет четное число ребер, идущих к нему - 2 линии, идущие к углу на нормальном объекте; 4 линии, идущие вместе, когда угол одного объекта касается угла другого объекта и т. Д. Я не знаю, насколько сложно было бы адаптировать этот алгоритм для обработки диаграмм вороной, которые обычно имеют 3 ребра, идущие к каждому углу.

Дэвид Кэри
источник
+1 Интересная находка! Однако обратите внимание: хотя это программное обеспечение выглядит способным решать многие проблемы, связанные с соединением линий в полигоны, оно может сделать слишком много : похоже, оно также пытается упростить функции, что может быть нежелательным побочным эффектом. (Например, это может разрушить топологическую целостность.)
whuber
3

Вы изучили кодовую базу GRASS для решения вашей проблемы? -> http://old.nabble.com/Polyline-to-Polygon-operation-td20257839.html

oeon
источник
1
Спасибо ... но я не ищу конкретное «упакованное» решение, а лежащий в основе алгоритм и / или его название, которое будет соответствовать различным областям ГИС, Comp Geom и / или Comp Sci ...
Я думал о том, чтобы конкретно посмотреть на исходный код двух упомянутых процессов в моей ссылке, может помочь вам.
oeon
Я думаю, что мне нужно было бы установить программное обеспечение, чтобы увидеть код, так как я не вижу никаких записей на этих страницах, если я что-то упустил.
1
Вы можете просмотреть источник GRASS онлайн: trac.osgeo.org/grass/browser
underdark
@underdark Спасибо за указатель. Насколько я могу судить main.cпо v.typeисточнику, все, что происходит, - это то, что функции помечаются как границы: никакой фактической обработки не происходит. В ретроспективе это не слишком удивительно: если (я не знаю точно) объекты поддерживаются полной 2D-топологической информацией, то все вычисления для определения полигональных областей автоматически выполняются при создании или импорте объектов и сохраняются на протяжении всего процесса. все операции геообработки.
whuber
3

алло

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

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

Вторая часть, которая заключается в «преобразовании линий в многоугольники», в большей степени зависит от формата, чем представление полигонов / линий. Я имею в виду переход от:

LINESTRING (1 1, 2 2)
LINESTRING (2 2, 2 1)
LINESTRING (2 1, 1 1)

чтобы:
POLYGON ((1 1,2 2,2 1,1 1))

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

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

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

В PostGIS функция называется ST_Polygonize. Эта функция создает все возможные многоугольники из заданных вами линий линий.

Это выполняется GEOS, поэтому вы можете найти алгоритмы в коде GEOS и JTS.

Просто некоторые мысли

/ Никлас

Никлас Авен
источник
1

Вы можете попробовать поискать алгоритм «Вперед». Мне сказали, что это общий характер, но единственные обсуждения, которые я когда-либо читал, всегда были связаны с arcgis. Может быть, посмотрите на ссылки, приведенные в этих примечаниях к лекции для впереди звезды.

Кирк Куйкендалл
источник
1
Я прокомментирую здесь, хотя этот комментарий также касается некоторых других предложенных решений: проблема не может быть представлена ​​в сети (или на графике). Требуется информация о том, как линии связаны внутри двухмерной поверхности . Таким образом, представления звезд вперед / назад будут бесполезны; нужен DCEL или что-то подобное.
whuber
@whuber - Я предполагал, что комментарий Дэна о том, что все «дефекты» были удалены, подразумевал, что линии были чистыми. Как таковая, должна быть возможность свести это к задаче обхода графа нахождения всех циклов в графе. Сначала я подумал, что «Впередая звезда» поможет в алгоритмах, которые обходят график, делая самый крутой поворот вправо в каждом узле. Тем не менее, если посмотреть немного больше, то, кажется, есть лучшие способы stackoverflow.com/questions/261573/… Но, тем не менее, это предполагает, что проблему можно переформулировать в виде графика.
Кирк Куйкендалл
1
Поиск циклов в графе - это не то же самое, что поиск граней в плоском графе. Рассмотрим абстрактный граф с вершинами {a, b, c, d} и ребрами {a, b}, {a, c}, {b, c}, {b, d}, {c, d}. Основа для циклов состоит из a-> b-> d-> c-> a и a-> b-> c-> a. В плоском вложении a -> (0,1), b -> (2,2), c -> (2,0), d -> (3,1) (где все ребра являются отрезками), цикл a-> b-> d-> c-> a не является гранью, но если мы переместим d в (1,1), это будет гранью. Это показывает, почему понятие «лицо» требует, чтобы граф был встроен в плоскость, и почему грани не могут быть вычислены исключительно из абстрактной структуры графа.
whuber