тесселяция выпуклого многоугольника.

← →
@!!ex © (2008-05-14 15:17) [0]

как??

суть задачи:
есть массив.
в нем 0 и 1, 0 - пустая точка, 1 - залитая.
1 образуют некоторую фигуру.
нужно преобразовать эту фигуру в набор треугольник.

← →
Ega23 © (2008-05-14 15:20) [1]

Многоугольник точно выпуклый?

← →
Palladin © (2008-05-14 15:21) [2]

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

← →
@!!ex © (2008-05-14 15:27) [3]

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

← →
Ega23 © (2008-05-14 15:31) [4]

> как я понимаю задача сводится к разбиению фигуры на несколько
> правильных многоугольников.

Да. Коллега по работе решал года 2 назад. Алгоритм в гугле нарыл.

← →
@!!ex © (2008-05-14 15:36) [5]

В принципе посетила одна идея. попробую реализовать ее. сюда выложу для критики.

← →
Palladin © (2008-05-14 15:47) [6]

а чего тут посещать :) сел, нарисовал, проанализировал, выбрал общий подход и сделал :) могу написать даже... :)

1. начиная с вершины впуклого многоугольника идем по вершинам слева направо (справа налево) по цепочке

2. анализируем положение следующей вершины относительно послеследующей

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

4. рассматриваем уже два построенных многоугольника :)

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

← →
@!!ex © (2008-05-14 19:30) [7]

Рассказали мне об интересно подходе.
Marching squares
Очень простой и эффеективный сопсоб как раз для моего случая.

Смысл в том, что берется изображение, изначально уже можно считать, что триангуляция произведена. т.к. каждый пиксель можно представить двумя треугольниками. НЕо это не эффективно.
Делаем проход и объединяем квадраты, которые образуют собой квадрат 2х2, проходим по всему массиву.
Повторяем до тех пор, пока проход не вернет 0. Тоесть ни одного нового квадрата не построено.
В результате мы получаем фигуру состоящия из нескольких больших квадратов, заполняющих основное пространство, нескольких чуть поменьше - в всяких затых и т.д. и совсем маленькие - для микродетализации.
Все. Просто. и эффективно

← →
@!!ex © (2008-05-14 19:30) [8]

Думаю, если еще в конце провести объединение не в квадрат, а в прямоугольник - вообще замечательно получится.

← →
Palladin © (2008-05-14 23:49) [9]

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

>1 образуют некоторую фигуру.

они никакую фигуру не образуют в таком случае, просто набор точек на плоскости, а как его интерпритировать - жестки правил нет. систему распознавания образов строить?

другое дело если бы это был последовательный список координат, описывающий тот самый впуклый многоугольник

← →
ketmar © (2008-05-14 23:59) [10]

>[9] Palladin © (2008-05-14 23:49:00)
угу. похоже на «полигонизатор» битмапов. плоская версия marching cubes.

---
Understanding is not required. Only obedience.

> другое дело если бы это был последовательный список координат,
> описывающий тот самый впуклый многоугольник

Это как раз довольно легко строится.

> угу. похоже на «полигонизатор» битмапов. плоская версия
> marching cubes.

мм. Ну я же в [7] как раз об этом и писал...

>[13] @!!ex © (2008-05-15 18:41:00)
я про метод задания оригинального полигона.

---
Understanding is not required. Only obedience.

тесселяция выпуклого многоугольника. Найти похожие ветки