Создание новых полигонов из разрезанного полигона (2D)

Я застрял с этой маленькой проблемой, и мой алгоритм ее решения подходит не для всех случаев. Кто-нибудь знает, как это решить?

Вот пример многоугольника:

http://img148.imageshack.us/img148/8804/poly.png

Официальное описание

У нас есть список точек в порядке CW, определяющих многоугольник. Мы также можем запросить, является ли точка точкой отсечения с is_cut(p), где p - заданная точка. Теперь мы хотим вычислить новые полигоны, вызванные этим «разрезом».

Алгоритм должен делать следующее:

Ввод: {a, c1, b, c4, c, c5, d, c6, e, c3, f, c2}

Выход: {a, c1, c2}, {b, c4, c3, f, c2, c1}, {d, c6, c5}, {e, c3, c4, c, c5, c6}

Вот мой текущий алгоритм:

follow your points, CW
if the point is a cut point
-> go back trough the list looking for cut points
--- if next cut point is connected to the current cut point 
    and not part of the current poly, follow it
--- else keep searching
else
-> continue until you hit your starting point.
that's a poly
do this for every non-cut-point

Этот алгоритм не работает, если вы начнете с c или f.


algorithm computational-geometry polygon intersection
person sulf    schedule 21.11.2009    source источник
comment
Когда я увидел вашу фотографию, я наконец понял результат. Однако я не думаю, что, учитывая этот ввод, компьютер может каким-то волшебным образом угадать, что все координаты C принадлежат друг другу. Поэтому я бы подумал, что помимо координат многоугольника вам также понадобится отдельный входной массив, определяющий, какой из этих индексов является индексом, по которому нужно вырезать. Более логичным было бы: один многоугольник и 1 вектор, определяющий линию разреза.   -  person Toad    schedule 21.11.2009
comment
Правильно, я вычислял точки c_n раньше, поэтому я могу предоставить функцию is_cut (p), которая будет формировать такой список {c1, ..., cn}, где n mod 2 == 0. Мне очень жаль, что изображение, но stackoverflow не позволяет мне публиковать изображения :(.   -  person sulf    schedule 21.11.2009
comment
Я добавил также алгоритм псевдокода, который использовал, чтобы знать.   -  person sulf    schedule 21.11.2009
comment
хм ... эта фотография напоминает мне то, что я каждый день вижу в метро. (рис.) alloyfirms.ru/bank/5295_moscow.gif   -  person P Shved    schedule 21.11.2009
comment
@pavel: Это моя карта метро ecampmany.com/NY/Subwaymap.gif   -  person sulf    schedule 21.11.2009

Ответы (4)


arrow_upward
5
arrow_downward

Сначала вы должны вычислить, какие сегменты линии разреза принадлежат внутренним частям вашего исходного многоугольника. Это классическая проблема, и ее решение простое. Учитывая, что ваши точки c1, c2, c3 ... c6 расположены вдоль линии именно в этом порядке, сегменты c1-c2, c3-c4 и т. Д. Всегда будут принадлежать внутренним элементам многоугольника (*).

Теперь мы можем построить простой рекурсивный алгоритм вырезания многоугольников. Учитывая ваш большой входной массив, {a, c1, b, c4, c, c5, d, c6, e, c3, f, c2}, начните с любой точки многоугольника, например, b; добавить его в массив result. Пройдите по входному массиву вперед. Если вы столкнетесь

  • обычный узел многоугольника, поместите его в массив result.
  • ck узел, где k нечетно, найдите c(k+1) и продолжайте движение с его позиции.
  • ck узел, где k четное, найдите c(k-1), перейдите на его позицию и продолжайте движение вперед.

В последних двух случаях добавьте эти узлы в том порядке, в котором они встречались, в массив result. Добавьте узел ck в набор cut и добавьте еще один узел (c(k+1) или c(k-1), в зависимости от того, что у вас есть) в глобальный набор done.

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

Рано или поздно вы встретите начальный узел, от которого переходили. Теперь в массиве result у вас есть вырезанный многоугольник. Помни это. Повторите процедуру рекурсивно, начиная с позиции каждого узла, который принадлежит набору cut и не принадлежит глобальному набору done.

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

В нашем примере начните с b:

  1. done={}, начиная с b. После первого прохода вы получите result=[b,c4,c3,f,c2,c1], cut={c4,c2}, done={c3,c1}; Рекурсия на узлы c4 и c2.
  2. done={c3;c1}, начиная с c4 (рекурсия с 1). После этого прохода вы получите result=[c4,c,c5,c6,e,c3,c4], cut={c5,c3}, done+={c6,c4}; Обратитесь к c5.
  3. done={c3;c1;c4;c6}, начиная с c2 (рекурсия с 1). После этого прохода вы получите result=[c2,a,c1], cut={c1}, done+={c2}; Не возвращайтесь к c1, так как он установлен done;
  4. done={c3;c1;c4;c6;c2}, начиная с c5 (рекурсия с 2). После этого прохода вы получите result=[c5,d,c6], cut={c5}, done+={c6}; Не возвращайтесь к c5, так как он установлен done;

Вуаля - у вас есть 4 нужных полигона.

(*) Обратите внимание, что для этого требуется более «математическое» представление линии. Например, если одна из вершин многоугольника находится на линии, вершина должна быть удвоена, т. Е. Если c точка была немного ближе к правой стороне и на красной линии, на линии было бы [c1, c2, c3, c, c, c6] точек, а многоугольник массив будет [a, c1, b, c, c, c, d, c6, e, c3, f, c2].

Иногда (не в этом примере) это может привести к вырезанию «пустых» полигонов, например [a, a, a]. Если они вам не нужны, вы можете устранить их на поздних этапах. Во всяком случае, это вычислительная геометрия с огромным количеством граничных случаев. Я не могу включить их все в один ответ ...

person P Shved    schedule 21.11.2009
comment
Цитата: ... сегменты c1-c2, c3-c4 и т.д. всегда будут принадлежать внутренним элементам многоугольника ..., не всегда будут выполняться. Например, удалите точки разреза c4 и c5 и пусть вместо этого c будет точкой разреза. - person Bart Kiers; 22.11.2009
comment
@ Барт К., в этом нет никакой ошибки. Добавлено объяснение. - person P Shved; 22.11.2009
comment
Извините, я не имел в виду, что вы ошибались. Просто вы заставляете это звучать очень легко, хотя есть (как вы сами отметили) довольно много сложных угловых случаев, которые нужно учитывать. - person Bart Kiers; 22.11.2009
comment
Потрясающий ответ! Здорово, что ты переступил через это после того, как объяснил, что делать. - person Adam Harte; 06.08.2010

arrow_upward
3
arrow_downward

Вы можете применить отсечение Weiler Atherton (фактически то, что предлагает Павел), но есть огромный нюанс.

Из-за ошибок с плавающей запятой чрезвычайно сложно заставить алгоритм отсечения W / A хорошо работать - в таких случаях, как линия отсечения, проходящая через вершину или точно вдоль края многоугольника, алгоритм может запутаться в том, какой «путь» "по периметру многоугольника, за которым он должен следовать, и затем выдает неверные результаты.

person Jason Williams    schedule 21.11.2009
comment
То, что я предлагаю, можно легко расширить для обработки таких случаев, но моему алгоритму не нужно ничего знать об арифметике с плавающей запятой, он просто просматривает данные массивы (что также не требует особой точности). - person P Shved; 22.11.2009
comment
Что правильно: это вычислительная геометрия с огромным количеством граничных случаев или [ее] можно легко расширить для обработки таких случаев? Любой, кто пытался реализовать эти методы, может сказать вам, что для реализации описанного выше алгоритма требуется всего несколько минут и гораздо больше времени, чтобы фактически начать работать в обобщенном и полезном смысле. Если вы примете одно неверное решение (это легко сделать, поскольку все знают, что компьютеры не умеют выполнять математические вычисления) при обходе иерархии узлов, вы сгенерируете неверные выходные данные. - person Jason Williams; 22.11.2009

arrow_upward
0
arrow_downward

1 сторона поиска для каждой точки

выберите один мост, который не находится в разрезе (например, a), и установите, что он находится с левой стороны (на самом деле он не соответствует)

когда вы переходите по точкам на разрезе, вы достигаете изменения стороны точки. Так вы найдете левую / правую точки.

Проблема в том, что вы также должны учитывать, что порядок точек должен быть предопределенным. (например, по часовой стрелке)

2 начните с каждой середины схватки и пройдите один раз по часовой стрелке и против часовой стрелки.

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

Если вы «переполняете» c, это означает, что вы достигли внешнего полинома. Вы можете решить эту проблему, если определите c0 и cmax, которые лежат на polgon, и у вас есть чем

input =  {a, c1, c0 ,c1, b, c4, c, c5, d, c6, c7, c6, e, c3, f, c2}
person Luka Rahne    schedule 21.11.2009

arrow_upward
0
arrow_downward

Самым простым в реализации является Sutherland-Hodgman. Единственная проблема заключается в том, что он оставляет небольшие полосы с нулевой площадью, соединяющие многоугольники на одной стороне линии. В вашем примере это даст вам что-то вроде:

{a c2 c3 e c6 c5 c c4 c1} и {b c1 c2 f c3 c6 d c5 c4}

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

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

person MPG    schedule 02.12.2009