Алгоритм определения твердых тел/отверстий в сложной форме Безье

Я использую библиотеку nanovg для визуализации сложной формы Безье, но nanosvg не сообщает мне направление намотки, то есть прочность/отверстие каждого подконтура в составной форме.

Что такое математический алгоритм, который скажет мне, какой подконтур является сплошным, а какой — дырой, учитывая точки Безье подконтуров, предполагая, что все пути не пересекаются?

Я мог бы вычислить площадь каждого подконтура, отсортировать по площади и альтернативу между сплошным телом и отверстием, но это работает только в том случае, если пути образуют цепочку подмножеств, поэтому нарисовать эту составную форму было бы невозможно.

составная фигура


svg graphics bezier
person Vortico    schedule 19.09.2017    source источник
comment
техническое примечание: многоугольников Безье не существует. Многоугольники — это пути, состоящие из прямых участков, тогда как безье — это кривые. Это может быть придиркой, но вы спрашиваете о технической теме, поэтому правильное определение терминов имеет большое значение. Что касается алгоритма? ответ зависит от вашей библиотеки. Некоторые библиотеки рассматривают направление по часовой стрелке/против часовой стрелки как заполнение/вырез, некоторые придерживаются противоположного направления, что означает противоположное правило заполнения. Однако не существует алгоритма, который мог бы сказать вам, что ДОЛЖНО быть заполнено/вырезано исключительно на основе путей, потому что это не свойство путей.   -  person Mike 'Pomax' Kamermans    schedule 20.09.2017
comment
@Mike'Pomax'Kamermans Хороший улов, спасибо. Также добавлено предположение, что все пути не пересекаются, поэтому я считаю, что теперь это должно быть четко определено. nanovg обрабатывает CCW как заполнение, а CW как вырез.   -  person Vortico    schedule 20.09.2017
comment
Можете ли вы указать правило заполнения svg? Если это так, установите его на четный/нечетный, и это должно помочь без каких-либо усилий с вашей стороны. Если нет, все равно установите его сразу после того, как nanosvg сгенерирует ваш файл, используя дополнительную утилиту (или даже замену строки).   -  person Mike 'Pomax' Kamermans    schedule 20.09.2017
comment
почему бы не добавить SVG в качестве кода, чтобы мы могли видеть, что вы действительно получили (к сожалению, SO/SE не поддерживает изображения SVG и PCX).   -  person Spektre    schedule 20.09.2017

Ответы (1)


arrow_upward
2
arrow_downward

Алгоритм описан в определении fill-rule SVG. Начните с точки и проведите один произвольный луч в бесконечность (ну, линию, которая заканчивается за пределами области, которую нужно учитывать) и подсчитайте пересечения путей одним из двух методов ненулевой и четнонечетный описано.

Определение количества пересечений. Не пытайтесь сделать это для подпутей за один раз, а рассмотрите каждый сегмент пути отдельно. У большинства будет нулевой счет, и это нормально. Эта библиотека имеет, например, функция для вычисления точек пересечения куба Безье и прямой. Посмотрите исходный код, он хорошо документирован. (Хотя не очень ясно, какую позицию занимает автор в отношении авторского права.)

Определение направления пути. Вам нужно только определить, где находятся начальная и конечная точки сегмента слева или справа от луча.

  • Если оба находятся на одной стороне, считайте один слева направо и один справа налево. (ненулевое правило: 0, четно-нечетное правило: +2)
  • Если начальная точка левая, а конечная точка правая, подсчитайте либо один слева направо (+1), либо, для кубического Безье с тремя пересечениями, подсчитайте два слева направо и один справа налево. . (ненулевое правило: +1, четно-нечетное правило: +3)
  • Если начальная точка правая, а конечная точка левая, для одного пересечения (ненулевое правило: -1, четно-нечетное правило: +1) или для трех пересечений (ненулевое правило: -1, четно-нечетное правило: +3)
  • Если луч пересекает подконтур только в точке сегмента, вы должны избегать подсчета пересечения дважды. Лучший способ избежать ошибок — обрабатывать два сегмента так, как если бы они были одним целым, вычитать единицу из добавленного количества пересечений и определять сторону только для общих начальных и конечных точек.

В конце концов, для отличного от нуля точка находится внутри, если итоговая сумма подсчета не равна нулю. Для evenodd оно находится внутри, если окончательный итог подсчета нечетный.

person ccprog    schedule 19.09.2017
comment
Спасибо! Это более элегантно, чем я думал, когда кубический решатель убран. - person Vortico; 28.09.2017