как??

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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


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


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

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

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

---
Understanding is not required. Only obedience.