Цитата(Flap @ 28.4.2006, 12:34  ) |
| А еще до кучи не помешал бы алгоритм пересечения невыпуклых многоугольников. |
для этого лучше создать новую тему...
глядишь, чего-нибудь и придумаем...
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Полигон с дыркой |
| Автор: Flap 10.4.2006, 08:06 |
| Как в векторных редакторах реализован алгоритм закраски полигона, из которого с помощью булевых операций "вырезан" другой полигон? Или, хотя бы, как это реализовать с помощью функций winapi? |
| Автор: nostromo 10.4.2006, 14:42 |
| Что конкретно Вас интересует: подходящие структуры данных для хранения таких вещей (тогда winapi как бы ни причем), или процесс рендеринга при выводе на экран? |
| Автор: Flap 10.4.2006, 15:49 |
| Я пока еще не могу ответить на этот вопрос, но положение вещей таково: Разработаны структуры данных с помощью которых я могу комфортно редактировать и хранить полигоны сложной формы, состоящие из различных линий и кривых. Рендеринг пока осуществляется с помощью функций winapi. В данный момент встала задача реализации булевых операций. Дырка в бублике, например, это частный случай операции вычитания. Об этом я пока ничего не знаю, поэтому можно разбить вопрос на несколько: - можно ли нарисовать бублик с помощью winapi (каков общий принцип). - уже исходя из этого думать, как адаптировать существующие структуры к новой задаче. Наверно, так будет правильнее. |
| Автор: nostromo 10.4.2006, 16:17 |
| Тогда желательно ответить еще на ряд вопросов: Как выглядит структура полигона? Строго говоря, если границы могут быть криволинейными, то это уже не полигон. Что Вы понимаете под булевыми операциями? Не знаете как определить рузультирующий цвет или результирующую область? Что касается области, то обычно структуры хранения плоских полигонов содержат среди прочего список сторон, записанных в виде функций вида A*x + B*y + C (хранятся, естественно, только коэффициенты). Для точек прямой f(x,y) = 0, для области с одной стороны от прямой f(x,y)>0, с другой стороны --- f(x,y)>0. Для подобного представления давно уже развита подходящая математика (линейная алгебра), позволяющая эффективно осуществлять переносы, повороты, растяжения, работу с многомерными объектами, отсечение невидимых линий и т.д. и т.п. Вполне возможно, Ваши проблемы решатся путем использования подходящей библиотеки, которая все это умеет. И еще, на сайтах, посвященных компьютерной графике, наверняка полно всевозможных вводных статей, книг, и даже реализаций. Обратитесь сначала туда. Может быть, конечно, Вы разрабатываете что-то очень специализированное и уникальноое. Тогда расскажите подробнее. |
| Автор: Flap 10.4.2006, 16:32 |
| Рассмотрим пример: Есть розовый полигон сложной формы (две линии и две кривые). Из него хочу вырезать белый пятиугольник так, чтобы просвечивал зеленый. Структура полигона представляет собой массив вершин, сегментов их соединяющих и класса, отвечающего за закраску полигона. Выршины, сегменты и заливка - это все классы, естественно. |
| Автор: nostromo 10.4.2006, 16:46 |
| И все же сначала нужно уточнить постановку вопроса: 1. Умеете ли Вы выводить на экран, то, что хранится в структуре? 2. Допускает ли Ваша структура хранение результата вычитания одного полигона из другого? 3. Если да, то будет ли алгоритм, строящий этот результат вычитания, тем что Вы хотите? Или все же проблемы с выводом на экран? |
| Автор: maxim1000 10.4.2006, 17:13 |
| ну раз уж упомянули WinAPI, то можно воспользоваться его средствами: 1. создаем промежуточный device context 2. рисуем на нем внешний полигон и заполняем его нужным цветом 3. рисуем на нем вычитаемый полигон и заполняем его ненужным цветом (этот цвет будет означать прозрачность) 4. переносим с него на основной device context с помощью TransparentBlt, указывая при этом выбранный прозрачный цвет |
| Автор: SoWa 10.4.2006, 18:19 |
| Или- раз уже вырезали прямоугольник- то и создадим новый полигон из этой фигурки с TransparenColor=White. Затем поместим под него зелений треугольник и все. Рендеринг по-моему без разницы как делать. |
| Автор: Flap 11.4.2006, 08:22 |
| Большое спасибо за ответы. Все решается с помощью комбинирования регионов. Как это дела сохранять - дело техники. Буду думать. |
| Автор: regis 14.4.2006, 13:09 |
| Вообще-то, у меня есть где-то алгоритм (на C), решающий задачу четностного заполнения многоугольника (самопересекающегося). Думаю, можно его обобщить на произвольное число пересекающихся многоугольников. Если нужно, могу прислать. |
| Автор: Flap 28.4.2006, 13:34 |
| Можно поподробней. Что значит четностного многоугольника? А еще до кучи не помешал бы алгоритм пересечения невыпуклых многоугольников. Вообще была бы красота. Большое спасибо. |
| Автор: maxim1000 28.4.2006, 22:39 | ||
для этого лучше создать новую тему... глядишь, чего-нибудь и придумаем... |
| Автор: regis 11.5.2006, 11:27 | ||
Многоугольник "четностным" не бывает, таким может быть алгоритм заполнения (Even/Odd Rule). имеется в виду то, что если от "внешнего пространства" какую-то область отделяет нечетное число отрезков, то она заполняется; если четное -- остается нетронутой. |
| Автор: RomanEEP 18.5.2006, 15:08 |
| Можешь попробовать использовать библиотеку glu: Разбиваешь каждый контур (если он задан кривыми) на линии и задаешь их gluBeginContour .. gluEndContour На выходе получишь набор треугольников. |
| Автор: Earnest 23.5.2006, 18:04 | ||
Если многоугольник - это именно многоугольник (т.е. никаких кривых), то алгоритм, вкратце такой: 1. Полигоны должны быть ориентированы определенным образом, например, чтобы "внутри" было слева. Т.е. самопересекающиеся полигоны нужно сначала "нормализовать". 2. Строим эвклидов граф, вычисляя все пересечения и отслеживая принадлежность каждого ребра. Причем фиксируем ориентацию ребер и различаем, где полигон (слева, вправа). 3. Отфильтровываем "лишние" ребра (по принципу что слева, а что справа). 4. Обходим то, что осталось. 5. Для того, чтобы все корректно работало, нужно обязательно ограничить точность сравнения точек - т.е. округлять их до некоторой сетки. Алгоритм годится для любых операций с полигонами - объединения, разности, ... Изменяется только принцип отсева ребер. |