Создание новых многоугольников из разрезанного многоугольника (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 a poly
do this for every non-cut-point

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

Ответ 1

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

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

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

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

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

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

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

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

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

Voila - вы получаете 4 многоугольника, которые вам нужны.

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

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

Ответ 2

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

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

Ответ 3

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

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

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

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

2 начинаются с каждого среза cx и идут один раз по часовой стрелке и против часовой стрелки.

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

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

input =  {a, c1, c0 ,c1, b, c4, c, c5, d, c6, c7, c6, e, c3, f, c2}

Ответ 4

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

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

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

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