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

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

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

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

08.01.2008, 15:40. Просмотров 2316. Ответов 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++
#include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; void lab () { int s1 = 0; int s2 =...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) - C++
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...

Помогите алгоритм для char переделать в алгоритм для float - C++
char* DecToBin(char x, char* str) { int i; for (i = sizeof(x)*8-1; i>=0; i--) { str = (x&1 == 1) ? '1' : '0'; x = x >>...

Волновой алгоритм (алгоритм Ли) - C++
Здравствуйте! У кого-нибудь есть реализованный волновой алгоритм (алгоритм Ли) ? Дело в том, что я игрушку захотел написать (что-то...

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

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

6
McVillain
1 / 1 / 0
Регистрация: 30.04.2007
Сообщений: 226
08.01.2008, 16:15 #2
Правильно ли я понял условия?

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

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

Ещё. Есть ли требования к скорости, или главное хоть как-то получить результат?
0
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-образный контур

отвратительно
0
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 Тормозить будет жутко.
0
Snork
Сообщений: n/a
11.01.2008, 13:03 #7
Спасибо большое за совет!

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

Еще раз спасибо, Снорк.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.01.2008, 13:03
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
7
Yandex
Объявления
11.01.2008, 13:03
Ответ Создать тему
Опции темы

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