Ну да ладно - я пытался решить эту проблему сам. Я потратил два месяца на решение, которое пыталось решить проблему нулевого оверлея. Как вы уже выяснили, вы не можете справиться со всеми вырожденными случаями и одновременно иметь нулевой перерасход.
Однако вы можете использовать гибридный подход:
Напишите себе процедуру, которая проверяет, могут ли соединения быть построены из простой геометрии без проблем. Для этого необходимо проверить угол соединения, ширину линии и длину соединенных отрезков (отрезки, которые короче своей ширины, являются PITA). С некоторой эвристикой вы сможете разобрать все тривиальные случаи.
Я не знаю, как выглядят ваши средние данные строки, но в моем случае более 90% широких линий не имели вырожденных случаев.
Для всех остальных строк:
Скорее всего, вы уже выяснили, что, если вы допускаете перерисовку, генерировать геометрию намного проще. Сделайте это, и пусть алгоритм многоугольника CSG и алгоритм тесселяции сделают тяжелую работу.
Я оценил большинство доступных пакетов тесселяции и в итоге получил тесселятор GLU. Это было быстро, надежно, никогда не ломалось (в отличие от большинства других алгоритмов). Это было бесплатно, и лицензия позволила мне включить его в коммерческую программу. Качество и скорость тесселяции в порядке. Вы не получите качество триангуляции Делоне, но поскольку для рендеринга вам просто нужны треугольники, это не проблема.
Так как я не любил API тесселятора, я поднял код тесселяции из бесплатной эталонной реализации SGI OpenGL, переписал весь интерфейс и добавил пулы памяти, чтобы уменьшить количество выделений. Это заняло два дня, но оно того стоило (например, повышение производительности в пять раз). Решение закончилось коммерческой реализацией OpenVG: -)
Если вы выполняете рендеринг с помощью OpenGL на ПК, вы можете переместить задание тесселяции / CSG из ЦП в графический процессор и использовать приемы stencil-buffer или z-buffer для удаления перерисовки. Это намного проще и может быть даже быстрее, чем тесселяция процессора.