Разбиение многоугольника на части

Question

В моем приложении я работаю с OpenGL и большими массивами данных.

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

Я получаю эти многоугольники в виде связанной петли точек (вершин), где каждый Vi связан с точками Vi-1 и Vi + 1и ничего больше. Последняя точка также связана с первой, что в результате дает нам цикл.

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

Но мне нужно построить МНОГО тех многоугольников, миллионы из них. Чтобы минимизировать нагрузку, я решил разделить свой мир на «куски», квадраты, как в Minecraft. Затем я использую отбраковку и другие методы оптимизации, чтобы визуализировать или отбросить / упростить эти чанки и сетки в них.

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

В результате я хочу иметь один (или несколько) контуров, которые затем можно триангулировать.

вот изображение моей задачи:

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

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

Answer 1

В данный момент я не на работе, потому что сейчас выходные, поэтому я буду пробовать / тестировать вещи в понедельник.

Однако я пришел к выводу, что это оченьпростое решение.

1) проверить все точки контура.

2) Если точка i и точка i + 1 не принадлежат одному и тому же фрагменту (который я могу легко проверить):

3), то найдите пересечение между границей фрагмента и линиейсделанный этими двумя точками.

4) добавьте эту новую точку к контуру между исходными двумя точками.

5) Когда каждый край многоугольника был проверен таким образом - триангулируйте его.

6) поскольку у нас есть точки по краям чанков - тогда во время триангуляции треугольники будут точно вписываться в границы чанков

7) для каждого треугольника, решить, к какому чанку он принадлежит, и сгенерироватьсетка в этом фрагменте.

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

Answer 2

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

---

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

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

// We need to keep track of the points that we insert on the cutting lines
let LIX = List of X-Cut-Line Intersection Points
let LIY = List of Y-Cut-Line Intersection Points

foreach Edge AB in Poly where A is inside the quadrant, B outside
    // Insert points into the polygon that intersect the X-Cut-Line
    if AB Intersects X-Cut-Line
        let Ix = Intersection Point
        Insert Ix between AB so that A<->B becomes A<->Ix
        B can be removed from the polygon now
        Add Ix to LIX
    // Insert points into the polygon that intersect the Y-Cut-Line
    if AB.Intersects Y-Cut-Line
        let Iy = Intersection Point
        Insert Iy between AB so that A<->B becomes A<->Iy
        B can be removed from the polygon now
        Add Iy to LIY

// Then iterate pairs of points along each cutting line to join them
sort LIX by X Ascending
while (LIX.Length > 0)
    let P0 = LIX[0]
    let P1 = LIX[1]
    Link P0 and P1
    Remove P0 and P1 from LIX

sort LIY by Y Ascending
while (LIY.Length > 0)
    let P0 = LIY[0]
    let P1 = LIY[1]
    Link P0 and P1
    Remove P0 and P1 from LIY

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