Вопрос у меня весьма непростой (в моем понимании), очень надеюсь на помощь. При закраске многоугольников используются два основных правила — even-odd (AKA alternating) и non-zero (AKA winding).

Правило для even-odd:
Из интересующей нас точки пускаем луч в бесконечность в произвольном направлении и подсчитываем количество пересечений этого луча с ребрами. Если получилось нечетное число, значит в этой точке закрашено, если четное — либо дыра, либо точка вообще не принадлежит многоугольнику.

Правило для non-zero:
Из точки пускаем луч в бесконечность и подсчитываем пересечения ребер с этим лучем. Если ребро пересекает луч слева направо — инкрементируем, если справа налево — декрементируем. Если результат не равен нулю, значит в этой точке — закрашено, если ноль — значит дыра. Например, если взять две концентрические окружности, то наличие дыры в центре будет определяться направлениями обхода — если они одинаковы, то дыры не будет, если разные — то будет дыра. То есть, с non-zero fill тоже могут быть дыры, причем даже в односвязном многоугольнике.

Задача заключается в том, чтобы в многосвязном или односвязном многоугольнике удалить лишние ребра, сохраняя правило non-zero. Рисунок в качестве примеров:



Здесь случае 1 ничего не удаляем, в случае 2 удаляем весь внутренний треугольник, поскольку с точки зрения non-zero fill он никак не влияет на результат.
Случай 3 — самый сложный. Здесь возможны 3 решения, каждое из которых приемлемо.
1) Не делать ничего — вопрос в том, как определить, что можно не далать ничего. Это очень сложно, поэтому мы его отбрасываем.
2) Сделать многосвязный полигон, как на рисунке 3b. Получится 2 многоугольника — ABCDEF и CGHE
3) Сделать односвязный полигон с дублированием точек — ABCGHECDEF.
В любом случае, нельзя проходить по одному ребру два раза. Дублировать точки — можно.

В случае 4 результат эквивалентен объединению двух треугольников. Случай 3 — это исключающее ИЛИ.
Казалось бы, это чистая Constructive Area Geometry, и Alan Murta с его GPC здесь поможет. Но не все так просто.



Здесь у нас многосвязный полигон, состоящий из треугольника и самопересекающегося четырехугольника. В результате должно получиться то, что справа. В одном варианте — многосвязный полигон: ABCDEFGH, IJE, JKG. В другом варианте — односвязный (щас попробую, могу и ошибиться). Итак, ABCDEIJEFGJKGH — вроде бы правильно. В принципе, односвязный вариант лучше (там, где это возможно, в случае 1 на предыдущем рисунке это невозможно). Но это может сильно усложнить задачу, поэтому многосвязный вариант тоже хорош.

Ну или еще случай:



Здесь алгоритм будет фильтровать самопересечения и сделает из ABCDEF треугольник. Из этого случая видно, что традиционные булевы оперции над полигонами нам никак не помогут.

Я чувствую, что надо делать нечто похожее на алгоритм Алана (http://www.cs.man.ac.uk/aig/staff/alan/software), но не могу определить, насколько эта задача сложна и решаема ли вообще данным способом. Просто пока что глубоко не разбирался.

Приветствуются любые мысли, ссылки, и т.д. А если кто-то возьмется решить — есть даже некоторая деньга (небольшая, но есть).