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

[dedsky]

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

[Zebestov]

В каком виде даны вершины и стороны?

[Волгоградец]

Я что-то не понял - если известны их вершины и стороны, то зачем их искать о_0?

[fish_r]

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

[dedsky]

В каком виде даны вершины и стороны?
Вершины в виде объектов Point, стороны - Vector.

Я что-то не понял - если известны их вершины и стороны, то зачем их искать о_0?
непонял, какие данные должны быть на выходе?(и в какой среде? а то вы во флейме, почему-то пишете)
Искать надо не вершины и стороны, а именно многоугольники. Нужно для каждого найденного многоугольника создать новый спрайт и отдельно его описать для дальнейшего манипулирования. Язык - AS, хотя это не так важно.

[incvizitor]

Вершины в виде объектов Point, стороны - Vector.

Что еще за Vector?

[fish_r]

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

[dedsky]

Я тут кажись чего-то родил
https://lh5.googleusercontent.com/_wJNzP7hBia8/TYCXDp9qFII/AAAAAAAAAOY/W5OJRJTjGq4/capture_03162011.jpg
Перебираем все объекты Point.
Уточнение: для каждого объекта P0, P1 и т.д. создан массив со всеми прилегающими сторонами. Сторона описана двумя векторами. На схеме обозначены синими стрелками. (Про вектор наглядно показано здесь (http://help.adobe.com/ru_RU/as3/dev/WSA8BD9022-BAB1-46d3-9B26-0D9649743C8E.html))

Из P0 движемся в следующую соседнюю вершину (P1), здесь встречаем свой массив векторов. Для поворота направо определяем вектор из этого массива с наименьшим углом к P0 P1. По нему движемся дальше до встречи с начальной точкой. Всё, первый спрайт создан (0 в красном кружке).
Смотрим следующую точку.
Точки, у которых перебрали все вектора исключаем из перебора.

Примерно так. Думал наткнуться на готовый алгоритм.
Извините за косноязычие, не могу доходчиво объяснять задачу. :(

[incvizitor]

То есть у Вас есть несколько объектов Vector.<Point>? Если да, где они хранятся?

[dedsky]

То есть у Вас есть несколько объектов Vector.<Point>? Если да, где они хранятся?

в массиве для каждой точки.

[incvizitor]

Короче, киньте код, а то как то не понятно.

[Zebestov]

Какой код — алгоритм человек просит. Данных достаточно.

[expl]

Sandy 3d или Papervision 3d или еще какой-то движок алгоритмом объект линиями обводит (с ходу не получилось нагуглить - может у Вас получится)
Как бы делал я:
- проходимся по всем линиям и хешируем точки по 2-м вершинам:

startVertexIndex// индекс вершины, от которой ведем линиию в данный момент.
endVertexIndex// вершина, к которой ведём линию.
if (isLineHashed[endVertexIndex + "," + startVertexIndex])
{
isIgnoredLine[endVertexIndex + "," + startVertexIndex] = true;
isIgnoredLine[startVertexIndex + "," + endVertexIndex] = true
}
else
{
isLineHashed[startVertexIndex + "," + endVertexIndex] = true
}

(таким образом линии, пройденные туда-обратно попадут в isLineIngored)
- далее при рисовании лини проверяем isIgnoredLine по двум ее точкам;

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

СТОП. Похоже не правильно задачу понял по картинке. Данный алгоритм только вычистит внутренние линии, но не поможет найти многоугольники

[semenyakinVS]

Думал алгоритм. На коленке:

1. Ищем самую правую (левую) вершину. Берём её в качестве текущей. Идём к П. 2.
2. Выбираем для текущей вершины любое из рёбер (векторов-соседей). Принимая его за «нулевое», сортируем остальные рёбра относительно него в порядке возрастания угла. Выбираем в качестве стартового ребра «нулевое». Идём к П. 3.
3. Движемся по рёбрам, начиная со стартового, следующим образом:
3.1. Вызываем в вершинах, по которым идёт«движение» сортировку по углам, принимая в качестве «нулевого» ребра то, по которому мы пришли в данную вершину.
3.2. Идём по ребру, которое следующие относительно «нулевого» в порядке сортировки (в какую сторону – большую или меньшую по углу, сами выберете).
3.3. В конце концов гарантированном приходим таким образом к начальной точке. Получаем многоугольник. Идём к П. 4.
Примечание: Рёбра, по которым мы проходим надо как-то исключать из списка используемых рёбер, понятное дело, не удаляя из основной структуры данных.
4. Брём следующее ребро для вершины сортировки (в какую сторону – большую или меньшую по углу, сами выберете). Это та вершина, с которой мы начинали строить многоугольник. В ней уже всё сортировано, поэтому можно брать следующее. Если такие рёбра кончились – переходим на следующую вершину. Берём её для «нулевого» ребра.

Вот в общем. Остальное можно додумать вместе. Тут тонкое место – выбор следующей вершины. А что хорошо по-моему – выбор следующей вершины в одном и том же направлении по углу, так как таким образом гарантированно получаем многоугольник.