Как в векторных редакторах реализован алгоритм закраски полигона, из которого с помощью булевых операций "вырезан" другой полигон? Или, хотя бы, как это реализовать с помощью функций winapi?

Что конкретно Вас интересует: подходящие структуры данных для хранения таких вещей (тогда winapi как бы ни причем),
или процесс рендеринга при выводе на экран?

Я пока еще не могу ответить на этот вопрос, но положение вещей таково:
Разработаны структуры данных с помощью которых я могу комфортно редактировать и хранить полигоны сложной формы, состоящие из различных линий и кривых. Рендеринг пока осуществляется с помощью функций winapi. В данный момент встала задача реализации булевых операций. Дырка в бублике, например, это частный случай операции вычитания.

Об этом я пока ничего не знаю, поэтому можно разбить вопрос на несколько:
- можно ли нарисовать бублик с помощью winapi (каков общий принцип).
- уже исходя из этого думать, как адаптировать существующие структуры к новой задаче.

Наверно, так будет правильнее.

Тогда желательно ответить еще на ряд вопросов:

Как выглядит структура полигона?
Строго говоря, если границы могут быть криволинейными, то это уже
не полигон.

Что Вы понимаете под булевыми операциями?
Не знаете как определить рузультирующий цвет или
результирующую область?

Что касается области, то обычно структуры хранения плоских полигонов содержат среди прочего список сторон, записанных в виде функций вида A*x + B*y + C (хранятся, естественно, только коэффициенты).
Для точек прямой f(x,y) = 0, для области с одной стороны от прямой
f(x,y)>0, с другой стороны --- f(x,y)>0.

Для подобного представления давно уже развита подходящая математика (линейная алгебра), позволяющая эффективно осуществлять переносы, повороты, растяжения, работу с многомерными объектами, отсечение невидимых линий
и т.д. и т.п.

Вполне возможно, Ваши проблемы решатся путем использования подходящей библиотеки, которая все это умеет.

И еще, на сайтах, посвященных компьютерной графике, наверняка полно всевозможных вводных статей, книг, и даже реализаций. Обратитесь сначала туда.

Может быть, конечно, Вы разрабатываете что-то очень специализированное и уникальноое. Тогда расскажите подробнее.

Рассмотрим пример:

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

Структура полигона представляет собой массив вершин, сегментов их соединяющих и класса, отвечающего за закраску полигона. Выршины, сегменты и заливка - это все классы, естественно.

Это сообщение отредактировал(а) Flap - 10.4.2006, 16:35

Присоединённый файл ( Кол-во скачиваний: 8 )
 sample1.PNG 3,36 Kb

И все же сначала нужно уточнить постановку вопроса:

1. Умеете ли Вы выводить на экран, то, что хранится в структуре?
2. Допускает ли Ваша структура хранение результата вычитания одного полигона из другого?
3. Если да, то будет ли алгоритм, строящий этот результат вычитания, тем что Вы хотите? Или все же проблемы с выводом на экран?

ну раз уж упомянули WinAPI, то можно воспользоваться его средствами:
1. создаем промежуточный device context
2. рисуем на нем внешний полигон и заполняем его нужным цветом
3. рисуем на нем вычитаемый полигон и заполняем его ненужным цветом (этот цвет будет означать прозрачность)
4. переносим с него на основной device context с помощью TransparentBlt, указывая при этом выбранный прозрачный цвет

Или- раз уже вырезали прямоугольник- то и создадим новый полигон из этой фигурки с TransparenColor=White.
Затем поместим под него зелений треугольник и все. Рендеринг по-моему без разницы как делать.

Большое спасибо за ответы. Все решается с помощью комбинирования регионов. Как это дела сохранять - дело техники. Буду думать.

Вообще-то, у меня есть где-то алгоритм (на C), решающий задачу четностного заполнения многоугольника (самопересекающегося). Думаю, можно его обобщить на произвольное число пересекающихся многоугольников. Если нужно, могу прислать.

Можно поподробней. Что значит четностного многоугольника? А еще до кучи не помешал бы алгоритм пересечения невыпуклых многоугольников. Вообще была бы красота.
Большое спасибо.
 

для этого лучше создать новую тему...
глядишь, чего-нибудь и придумаем... 

Многоугольник "четностным" не бывает, таким может быть алгоритм заполнения (Even/Odd Rule). имеется в виду то, что если от "внешнего пространства" какую-то область отделяет нечетное число отрезков, то она заполняется; если четное -- остается нетронутой.
 

Можешь попробовать использовать библиотеку glu:
Разбиваешь каждый контур (если он задан кривыми) на линии и задаешь их
gluBeginContour .. gluEndContour
На выходе получишь набор треугольников. 

Если многоугольник - это именно многоугольник (т.е. никаких кривых), то алгоритм, вкратце такой:
1. Полигоны должны быть ориентированы определенным образом, например, чтобы "внутри" было слева. 
Т.е.  самопересекающиеся полигоны нужно сначала "нормализовать". 
2. Строим эвклидов граф, вычисляя все пересечения и отслеживая принадлежность каждого ребра. Причем фиксируем ориентацию ребер и различаем, где полигон (слева, вправа). 
3. Отфильтровываем "лишние" ребра (по принципу что слева, а что справа).
4. Обходим то, что осталось.
5. Для того, чтобы все корректно работало, нужно обязательно ограничить точность сравнения точек - т.е. округлять их до некоторой сетки.

Алгоритм годится для любых операций с полигонами - объединения, разности, ... Изменяется только принцип отсева ребер.