Есть произвольный 2D многоугольник заданный своими вершинами Xi,Yi. Известно что многоугольник замкнутый и что вершины заданы у него последовательно. Многоугольник может иметь самопересечения, быть невыпуклым и порядок обхода (по часовой или против часовой стрелки) его вершин неизвестен.
Нужно найти внешний контур многоугольника.
Заранее спасибо.
With Best Regards
Hybernaculum
Your own personal Jesus
Someone to hear your prayers
Reach out and touch faith
Здравствуйте, Hybernaculum, Вы писали:
H>Есть произвольный 2D многоугольник заданный своими вершинами Xi,Yi. Известно что многоугольник замкнутый и что вершины заданы у него последовательно. Многоугольник может иметь самопересечения, быть невыпуклым и порядок обхода (по часовой или против часовой стрелки) его вершин неизвестен. H>Нужно найти внешний контур многоугольника.
Правда моя задача несколько сложнее и в более общем виде.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re[2]: контур произвольного многоугольника
От:
Аноним
Дата:
12.07.05 02:55
Оценка:
Здравствуйте, McSeem2, Вы писали:
MS>Правда моя задача несколько сложнее и в более общем виде.
В моём случае нужно найти один многоугольник, который
являлся бы внешним контуром исходного. Замкнутые дырки
внутри исходного многоугольника в моём случае игнорируются.
Здравствуйте, Аноним, Вы писали:
А>В моём случае нужно найти один многоугольник, который А>являлся бы внешним контуром исходного. Замкнутые дырки А>внутри исходного многоугольника в моём случае игнорируются.
Данная задача напоминает нахождение выпуклой оболочки — convex hull (но не convex hull!).
1. Находим все точки пересечения и добавляем их в общий массив.
2. Сортируем все точки по X.
3. Идем по нижней границе в отсортированном массиве от начала к концу. Добавляем точку i. Далее, если точка i находится ниже прямой, определяемой точками (i-2,i-1), то выкидываем точку i-1, иначе — оставляем.
4. Идем по верхней границе, аналогично нижней, от конца к началу, но с условиями "наоборот".
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, Hybernaculum, Вы писали:
H>Всем привет!
H>Помогите решить задачу:
H>Есть произвольный 2D многоугольник заданный своими вершинами Xi,Yi. Известно что многоугольник замкнутый и что вершины заданы у него последовательно. Многоугольник может иметь самопересечения, быть невыпуклым и порядок обхода (по часовой или против часовой стрелки) его вершин неизвестен. H>Нужно найти внешний контур многоугольника.
H>Заранее спасибо.
H>With Best Regards H>Hybernaculum
А интересует именно решение задачи или алгоритм должен быть оптимальнее некоторого, уже имеющегося ?
Года 2 назад, я решал похожую задачу, только там было несколько таких многоугольников, и требовалось найти контур их объединения. С учетом образующихся дырок. Задачу то я решил, но вот насчет оптимальности моего решения есть очень большие сомнения. Если интересно, я раскопаю ту задачу.
MS>Данная задача напоминает нахождение выпуклой оболочки — convex hull (но не convex hull!). MS>1. Находим все точки пересечения и добавляем их в общий массив. MS>2. Сортируем все точки по X. MS>3. Идем по нижней границе в отсортированном массиве от начала к концу. Добавляем точку i. Далее, если точка i находится ниже прямой, определяемой точками (i-2,i-1), то выкидываем точку i-1, иначе — оставляем. MS>4. Идем по верхней границе, аналогично нижней, от конца к началу, но с условиями "наоборот".
Пардон, я свалял дурака — задача гораздо сложнее. Но что-то в этом есть, особенно в сортировке по какому-либо критерию — я чувствую
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
_D>А интересует именно решение задачи или алгоритм должен быть оптимальнее некоторого, уже имеющегося ?
Меня интересует более-менее оптимальное решение задачи.
IMHO, задачу можно решить вот так:
1. найти все точки самопересечений и добавить их в исходный многоугольник
2. MaxПлощадь = 0
3. Контур = { пустой }
5. для всех точек искодного многоугольника:
{
a. найти для данную точки все циклы без самопересечений
b. для каждого из циклов
{
b.1 посчитать площадь S
b.2 если |S| > MaxПлощадь, тогда { MaxПлощадь = S, Контур = этот цикл }
}
}
но это жутко медленный вариант, типа поиска площади методом монте-карло
зато 100% результат
With Best Regards
Hybernaculum
Your own personal Jesus
Someone to hear your prayers
Reach out and touch faith
Здравствуйте, Hybernaculum, Вы писали: H>Есть произвольный 2D многоугольник заданный своими вершинами Xi,Yi. Известно что многоугольник замкнутый и что вершины заданы у него последовательно. Многоугольник может иметь самопересечения, быть невыпуклым и порядок обхода (по часовой или против часовой стрелки) его вершин неизвестен. H>Нужно найти внешний контур многоугольника.
Вот, что мне ответил Gernot Hoffmann (довольно известный "Zee German" в comp.graphics.algorithms):
Maxim,
this is a well known problem, as described in the
PostScript Language Reference Manual.
Different rules deliver different results e.g. for
the star or the donut, as demonstrated.
One solution is the strict definition of an 'outer
contour', as defined by this algorithm:
1. Find a starting point on the contour which is
not inside e.g. by searching by a scanline from
far left (edge of bounding box).
2. Go once around in ccw direction and go always
to the right at a bifurcation.
This delivers a contour without holes, which can be
treated by any of the standard methods.
Here it's shown for pixels:
http://www.fho-emden.de/~hoffm ann/inside.jpg
It should be possible to apply the strategy to vectors.
Any other strategy would depend on the image content.
Best regards --Gernot Hoffmann
Для задачи нахождения внешнего контура — вполне подходит. Но у меня задача сложнее — мне нужна именно полная эмуляция правила закраски non-zero в векторном виде.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, McSeem2, Вы писали:
MS>Для задачи нахождения внешнего контура — вполне подходит. Но у меня задача сложнее — мне нужна именно полная эмуляция правила закраски non-zero в векторном виде.
Конечно не подходит. Эта цитата – слишком общее утверждение. Как если бы автор советовал взять машину если нам надо на речку за городом. Эту машину мы еще строим! По-моему, для невыпуклой оболочки перспективны два подхода: графический (сканировать изображение) или сжимать convex hull. В моем случае число точек измеряется 1.0е+6, перебирать каждый лучик из контрольной точки очень дорого!
Здравствуйте, gok, Вы писали:
gok>Конечно не подходит. Эта цитата – слишком общее утверждение. Как если бы автор советовал взять машину если нам надо на речку за городом. Эту машину мы еще строим! По-моему, для невыпуклой оболочки перспективны два подхода: графический (сканировать изображение) или сжимать convex hull. В моем случае число точек измеряется 1.0е+6, перебирать каждый лучик из контрольной точки очень дорого!
Почему не подходит? Нам надо составить ненаправленный граф из имеющихся вершин плюс всех точек пересечения. При этом мы просто обязаны добавить в этот граф все точки пересечения — в наихудших случаях эта операция может быть O(N^2) и от этого никуда не деться. Но на практике — близко к O(N). Далее мы находим точку, гарантированно лежащую на границе и шагаем от этой точки по нашему графу в любом направлении (для определенности — против часовой стрелки). А в узлах с разветвлениями мы шагаем на ту вершину, которая у нас "правее всего" от предыдущего направления. Вот и всех делов...
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, gok, Вы писали:
MS>>Для задачи нахождения внешнего контура — вполне подходит. Но у меня задача сложнее — мне нужна именно полная эмуляция правила закраски non-zero в векторном виде. gok>Конечно не подходит. Эта цитата – слишком общее утверждение. Как если бы автор советовал взять машину если нам надо на речку за городом. Эту машину мы еще строим! По-моему, для невыпуклой оболочки перспективны два подхода: графический (сканировать изображение) или сжимать convex hull. В моем случае число точек измеряется 1.0е+6, перебирать каждый лучик из контрольной точки очень дорого!
Найти все пересечения тебе придётся. Никуда не денешься.
Полигон хранится как зацикленный двусвязный список вершин.
Ищешь все точки пересечения. При находении очередной, добавляешь новую вершину в список, причем дважды, таким образом: Были стороны A-B и C-D, а получились стороны A-O1, O1-C, B-O2 и O2-D (или A-O1, O1-D, B-O2 и O2-C, в зависимости от того, в какую сторону C-D пересекает A-B).
Обработав все пересечения, получишь фактически несколько списков.
Нахожишь внешнюю точку, например самую правую. Тот список, которому она принадлеждит, задает внешнюю оболочку, остальные — дырки.
Здравствуйте, McSeem2, Вы писали:
MS>Для задачи нахождения внешнего контура — вполне подходит. Но у меня задача сложнее — мне нужна именно полная эмуляция правила закраски non-zero в векторном виде.
Круто, как я раньше не догадался Хотя я конечно догадался, но меня терзали смутные сомнения. Метод — то что надо!
Your own personal Jesus
Someone to hear your prayers
Reach out and touch faith
Здравствуйте, Рома Мик, Вы писали:
РМ>Найти все пересечения тебе придётся. Никуда не денешься.
А вот и не все. В алгоритме с обходом по внешней границе нажно искать только пресечение текущего ребра со всеми остальными, а так как мы идем только по внешней границе, то пересекать внутренние ребра с внутренними же не предется.
Здравствуйте, ZakkeR, Вы писали:
ZR>А вот и не все. В алгоритме с обходом по внешней границе нажно искать только пресечение текущего ребра со всеми остальными, а так как мы идем только по внешней границе, то пересекать внутренние ребра с внутренними же не предется.
Теоретически это верно. Но на этапе нахождения пересечений у нас нет ни малейшего представления о том, что есть внутреннее, а что внешнее. Значит нам надо начинать обход без вычисленных пересечений и каждое ребро проверять на пересечения — это очень дорого. Дешевле сначала найти все пересеченеия, а потом строить контур. В алгоритме GPC by Alan Murta поиск пересечений в практических случаях близок к к сложности O(N log N). В наихудшем случае — конечно же O(N^2).
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
MS>this is a well known problem, as described in the
MS>PostScript Language Reference Manual.
MS>Different rules deliver different results e.g. for
MS>the star or the donut, as demonstrated.
MS>One solution is the strict definition of an 'outer
MS>contour', as defined by this algorithm:
MS>1. Find a starting point on the contour which is
MS> not inside e.g. by searching by a scanline from
MS> far left (edge of bounding box).
MS>2. Go once around in ccw direction and go always
MS> to the right at a bifurcation.
MS>This delivers a contour without holes, which can be
MS>treated by any of the standard methods.
MS>Here it's shown for pixels:
MS>http://www.fho-emden.de/~hoffm ann/inside.jpg
MS>It should be possible to apply the strategy to vectors.
MS>Any other strategy would depend on the image content.
MS>Best regards --Gernot Hoffmann
MS>[/code]
MS>Для задачи нахождения внешнего контура — вполне подходит. Но у меня задача сложнее — мне нужна именно полная эмуляция правила закраски non-zero в векторном виде.
Внешний контур нашел. спасибо.
а как найти дырки? хелп плз
Здравствуйте, Леонид, Вы писали:
Л>Внешний контур нашел. спасибо. Л>а как найти дырки? хелп плз
О! Давнишнюю тему подняли. В общем, мне все удалось. Не сказал бы, что все эти годы я был озабочен именно этой проблемой, я ее решал время от времени, по мере возникновения новых мыслей, начиная с задачи быстрой и надежной триангуляции. Такие задачи, как нахождение пересечений, триангуляция методом "подметающего луча" (sweeping scan-beam), Булевы операции над полигонами (Constructive Area Geometry), преобразование Non-Zero Fill в Even/Odd и некоторые другие, являются очень родственными.
То есть, после обработки получается набор простых полигонов (контуров) без самопересечений. При этом гарантируется, что закрашенная область всегда находится слева от ребер. Отсюда следует, что во-первых, любой контур имеет однозначно определенное направление обхода (нет самопересечений), во-вторых, что направление обхода определяет сущность контура — если CCW, то внешняя граница, если CW — то дыра.
Одновременно решается задача булевой алгебры над полигонами, причем, в отличие от классических вариантов с двумя полигонами на входе, мой метод работает с произвольным числом полигонов и последовательных операций, например: A unite B intersect C subtract D. Полигоны конечно же могут быть многосвязными и для каждого из них можно задавать правило закраски — NonZero или EvenOdd. Так же, довольно легко добавились еще два полезных правила заливки — PositiveWinding и NegativeWinding — исключительно полезно для быстрого выполнения Distance Transformation (для справки, winding number: http://en.wikipedia.org/wiki/Winding_number).
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re[4]: а дырки? ("слияние" близко находящихся полигонов)
Моя задача несколько другая чем ваша, но возможно вы подскажете куда копать хоть
У меня есть набор прямоугольников, их ребра паралельны осям координат. Изначально они не пересекают друг друга.
Нужно найти все прямоугольники находящиеся близко друг к другу (расстояние меньше minDistance) и "слить" в одну фигуру.
Простейший случай изображен на рис 1. В данном случае мне нужно всего то найти внешний контур:
1) нахожу все пересечения ребер составляя ненаправленный граф, к-й собственно состоит из всех точек нач.фигур и связи — это ребра (исходные и образованные в рез. пересечений)
2) нахожу крайний левый узел в графе и шагаю "направо" (сравнивая координаты узлов). таким образом когда дохожу до начальной точки — получаю внешний контур.
Все замечательно работало пока не появился случай на рис.2. В данном случае мне необходимо выдать в ответ еще и две дырки
Есть какие либо соображения как их найти используя уже построенный граф пересечений?
Возможно такая задача про "слияние" близко находящихся полигонов тоже существует и уже есть к-либо простые решения?
