Алгоритм Полигона

Здравствуйте, господа!У меня вопрос немного оффтопик, т.к. реализуется этот алгоритм не только на C++, а из чего угодно.Все дело в алгоритме.У меня есть два вектора (по X и по Y) в виде функций FLOAT GetVectorX(INT nIndex) и FLOAT GetVectorY(INT nIndex). Они дают нам координаты точек-узлов. Получается плоское поле с узлами. Чаще всего сетка равномерная, т.е. можно задавать начальные координаты поля, размер поля в узлах и дельты по обеим осям, но хочется иметь более универсальный алгоритм, так что будем считать, что сетка может быть какой угодно - не в виде прямоугольника, а неизвестно что. Но координата следующего узла всегда больше координаты предыдущей.Дан массив массивов структур FPOINT, где лежат вещественные координаты X и Y. Каждый такой массив определяет замкнутый полигон. (А массив массивов - это массив полигонов). Надо: из этого массива полигонов и этих векторов получить массив массивов FPOINT'ов, содержащих координаты не только точек, определяющих границы полигона, но и точек сетки, попадающих в полигон. Т.е. был контур - стала плоская фигура. Причем: узлы полигона всегда лежат на прямых, соединяющих две соседние точки по одной из осей. Теперь - в каком порядке эти точки должны в преобразованный массив-полигон входить. Порядок должен быть таков, чтобы каждая тройка точек всегда давала треугольник, а все треугольники, вместе взятые и давали нужный нам плоский полигон. Если при этом какие-то точки будут входить в массив дважды, трижды - все равно. Вот такая задачка. Я сам с нее фигею.Очень хочется надеяться, что кто-то когда-то аналогичную задачу решал! А лучше всего - если кто-то видел примеры аналогичного назначения.С нетерпением жду ответов, спасибо всем, кто откликнется!Снорк.
3 ответа

Правильно ли я понял условия?Есть произвольное множество множество точек плоскости (сетка) и произвольный многоугольник, заданный набором вершин. Требуется определить, какие из точек 'сетки' лежат внутри многоугольника, и составить из них и вершин многоугольника такой набор треугольников, который бы 'покрывал' многоугольник. Так?Да, ещё. Многоугольник выпуклый или нет? Возможны ли пересечения сторон?Ещё. Есть ли требования к скорости, или главное хоть как-то получить результат?


> Только таких многоугольников много, предлагаю для простоты рассматривать их последовательно... > и если это играет какую-нибудь рояль, то координаты их вершин > таковы, что вершины всегда лежат на отрезках, соединяющих 2 узла. > (Не диагональных, а по оси!)не совсем понятно, о каких осях речь. ('хочется иметь более универсальный алгоритм, так что будем считать, что сетка может быть какой угодно - не в виде прямоугольника, а неизвестно что' -- то есть в итоге просто набор точек, я так понял).> Он может быть и выпуклый и concave'ный.плохо> вчера своими глазами видел [...] 8-образный контуротвратительно


> Предполагаю следующую реакцию: 'Еще хуже!'. А вот и неправда! Никакой реакции. Произвольный - и пусть его произвольный.===============Как я вижу алгоритм...1. Устранить самопересечения контуров. То есть полный попарный перебор сторон с поиском пересечений. После этого можно рассматривать один произвольный (невыпуклый) многоугольник.2. Разбить невыпуклый многоугольник на треугольники. Наверное, есть какие-то более умные алгоритмы, но я их не знаю. Предлагаю следующее:Взять три подряд идущие вершины а(i), а(i+1), а(i+2) контура. Если отрезок а(i)-а(i+2) лежит внутри многоугольника (см. ниже), запомнить треугольник а(i)-а(i+1)-а(i+2) и перейти к контуру a(0)-a(1)-..-a(i)-a(i+2)-..-a(n), полученному из начального исключением вершины a(i+1). В противном случае перейти к следующей тройке контура. В итоге получаем совокупность треугольников, покрывающих без перекрытия исходный многоугольник.Отрезок лежит внутри произвольного многоугольника, если и только если он не пересекает ни одной стороны многоугольника и произвольная полупрямая, проведённая из произвольной внутренней точки отрезка, не проходящая ни через одну вершину многоугольника, пересекает нечётное количеством сторон многоугольника.3. Имеем множество треугольников (у некоторых из них есть общие стороны) и множество точек сетки. Для каждой точки и каждого треугольника: если точка лежит вне треугольника -- игнорируем; если точка совпадает с вершиной треугольника -- игнорируем; если точка лежит на стороне треугольника -- делим его на два новых; если точка лежит внутри треугольника -- делим его на три новых.точка X лежит внутри треугольника ABC, если и только если знаки третьих координат векторных произведений [AX, AB], [BX, BC], [CX, CA] совпадают.С не меньшим уважением.PS Тормозить будет жутко.