Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.82
Snork
Сообщений: n/a
#1

Алгоритм Полигона - C++

08.01.2008, 15:40. Просмотров 2135. Ответов 6
Метки нет (Все метки)

Здравствуйте, господа!

У меня вопрос немного оффтопик, т.к. реализуется этот алгоритм не только на C++, а из чего угодно.

Все дело в алгоритме.

У меня есть два вектора (по X и по Y) в виде функций FLOAT GetVectorX(INT nIndex) и FLOAT GetVectorY(INT nIndex). Они дают нам координаты точек-узлов. Получается плоское поле с узлами. Чаще всего сетка равномерная, т.е. можно задавать начальные координаты поля, размер поля в узлах и дельты по обеим осям, но хочется иметь более универсальный алгоритм, так что будем считать, что сетка может быть какой угодно - не в виде прямоугольника, а неизвестно что. Но координата следующего узла всегда больше координаты предыдущей.

Дан массив массивов структур FPOINT, где лежат вещественные координаты X и Y. Каждый такой массив определяет замкнутый полигон. (А массив массивов - это массив полигонов). Надо: из этого массива полигонов и этих векторов получить массив массивов FPOINT'ов, содержащих координаты не только точек, определяющих границы полигона, но и точек сетки, попадающих в полигон. Т.е. был контур - стала плоская фигура. Причем: узлы полигона всегда лежат на прямых, соединяющих две соседние точки по одной из осей. Теперь - в каком порядке эти точки должны в преобразованный массив-полигон входить. Порядок должен быть таков, чтобы каждая тройка точек всегда давала треугольник, а все треугольники, вместе взятые и давали нужный нам плоский полигон. Если при этом какие-то точки будут входить в массив дважды, трижды - все равно. Вот такая задачка. Я сам с нее фигею.

Очень хочется надеяться, что кто-то когда-то аналогичную задачу решал! А лучше всего - если кто-то видел примеры аналогичного назначения.

С нетерпением жду ответов, спасибо всем, кто откликнется!

Снорк.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.01.2008, 15:40     Алгоритм Полигона
Посмотрите здесь:

C++ Алгоритм
с++ алгоритм C++
C++ c++/алгоритм
C++ Алгоритм прима
алгоритм C++
C++ Алгоритм
Алгоритм C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
McVillain
1 / 1 / 0
Регистрация: 30.04.2007
Сообщений: 226
08.01.2008, 16:15     Алгоритм Полигона #2
Правильно ли я понял условия?

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

Да, ещё. Многоугольник выпуклый или нет? Возможны ли пересечения сторон?

Ещё. Есть ли требования к скорости, или главное хоть как-то получить результат?
Snork
Сообщений: n/a
09.01.2008, 13:11     Алгоритм Полигона #3
Доброе время суток!

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

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

>Да, ещё. Многоугольник выпуклый или нет? Возможны ли пересечения сторон?

Он может быть и выпуклый и concave'ный. Пересечения всякие возможны, вчера своими глазами видел;-) На одном наборе данных генерировалась петля (8-образный контур).

>Ещё. Есть ли требования к скорости, или главное хоть как-то получить результат

Плювать на скорость;-), мне бы натолкнуться на идейку алгоритма, что-то я с ним тупикую. А оптимизацию идеи я и сам проведу.

С уважением - Снорк.
McVillain
1 / 1 / 0
Регистрация: 30.04.2007
Сообщений: 226
09.01.2008, 13:58     Алгоритм Полигона #4
> Только таких многоугольников много,

предлагаю для простоты рассматривать их последовательно...

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

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

> Он может быть и выпуклый и concave'ный.

плохо

> вчера своими глазами видел [...] 8-образный контур

отвратительно
Snork
Сообщений: n/a
09.01.2008, 14:25     Алгоритм Полигона #5
Допустим, что сетка действительно неравномерна, примерно как здесь.
______________/--------\______
|
|

/
|

(Это ее верхняя и левая стороны, на этом рисунке они пунктирны, но на самом деле - нет). Вот о каких осях идет речь. Это, ужо не ось, конечно, но смысл понятен. Ладно, будем рассматривать более общий случай (скоро все равно придется его делать при смене интерполяционной модели). Вершины контуров могут лежать где угодно. Предполагаю следующую реакцию: 'Еще хуже!'.

Снорк.
McVillain
1 / 1 / 0
Регистрация: 30.04.2007
Сообщений: 226
10.01.2008, 16:47     Алгоритм Полигона #6
> Предполагаю следующую реакцию: 'Еще хуже!'.

А вот и неправда!

Никакой реакции. Произвольный - и пусть его произвольный.

===============

Как я вижу алгоритм...

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 Тормозить будет жутко.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.01.2008, 13:03     Алгоритм Полигона
Еще ссылки по теме:

C++ Алгоритм А*
C++ QR алгоритм
C++ Алгоритм
C++ алгоритм бм
алгоритм вычисления C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Snork
Сообщений: n/a
11.01.2008, 13:03     Алгоритм Полигона #7
Спасибо большое за совет!

Попробую сделать, посмотрю что из этого выйдет.

Еще раз спасибо, Снорк.
Yandex
Объявления
11.01.2008, 13:03     Алгоритм Полигона
Ответ Создать тему
Опции темы

Текущее время: 03:00. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru