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

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

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

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

08.01.2008, 15:40. Просмотров 2261. Ответов 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     Алгоритм Полигона
Посмотрите здесь:

Алгоритм трансформации полигона в массив треугольников (2d) - JavaFX
Доброго времени суток, делая проект, столкнулся с проблемкой. Появилась нужда создавать полигон, залитый определенного цвета. По идеи для...

Алгоритм трансформации полигона в массив треугольников (2d) - Графика и игры
Доброго времени суток, делая проект, столкнулся с проблемкой. Появилась нужда создавать полигон, залитый определенным цветом. По идеи для...

Изгиб Полигона - MathCAD
Доброго времени суток, нужен изгиб полигона Я пробовал добавить к матрице координат вторую и ей прибавлять значения, начиная от низа...

Прорисовка полигона - C#
Здравствуйте! Я хочу нарисовать полигон некоторой толщины, а потом залить его. ConturWidth = 25; ...

Вращение полигона - OpenGL
glLoadIdentity(); //glTranslatef(0.0,0.0,0.0); Что нужно сделать тут //glRotatef(rotateQuad,0.0,0.0,10.0); Вот тут...

GD. Сглаживание полигона - PHP
Здравствуйте. Есть ли в PHP алгоритмы для сглаживания полигона? К примеру, написал скрипт, который рисует график: <?php ...

Создание полигона - C#
Хочу создать полигон: myPolygon = new Polygon(); Пишет:Не удалось найти имя типа или пространства имен "Polygon" (пропущена директива...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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     Алгоритм Полигона
Еще ссылки по теме:

Заливка полигона - Lisp
Нужно сделать заливку полигона Пожалуйста, помогите сделать заливку полигона.

Расчёт полигона - Алгоритмы
Добрый день, форумчане! У меня есть точки полигона. Задача, нужно рассчитать точки второго полигона, каждая точка которого будут...

рисование многоугольника(полигона) - C#
Доброго времени суток!!!! Мне необходимо организовать рисование многоугольника(полигона) и делать всё это мышкой,дак вот есть метод...

Отображение полигона по координатам - Delphi
Подскажите как отобразить полигон по координатам на форме? Скажем имеются полигон со следующими координатами: x = 432669.90 y =...

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


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

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

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

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

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