Генерация новых полигонов из вырезанного полигона (2D)

Question

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

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

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,

Answer 1

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

Теперь мы можем построить простой рекурсивный алгоритм для резки полигонов. Учитывая ваш большой входной массив, {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], Если они вам не нужны, вы можете устранить их на поздних стадиях. В любом случае, это вычислительная геометрия с огромным количеством граничных случаев. Я не могу включить их всех в один ответ...

Answer 2

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

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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

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

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

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

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