Числа обмотки на дискретных поверхностях

На плоскости число обмотки — это количество раз, которое кривая оборачивается вокруг заданной точки. Числа обмотки являются базовым компонентом геометрических алгоритмов, таких как тесты принадлежности точки многоугольнику, а их обобщение на данные с шумом или топологическими ошибками оказалось полезным для задач обработки геометрии — от реконструкции поверхностей до булевых операций над сетками. Однако стандартные определения не могут быть непосредственно применены к поверхностям, поскольку не всякая кривая ограничивает область. Мы разрабатываем содержательное обобщение, исходя из хорошо известной связи между числами обмотки и гармоническими функциями. Обрабатывая производные таких функций, мы можем устойчиво отфильтровывать компоненты входных данных, не ограничивающие никакой области. В итоге наш алгоритм выдает (i) замкнутую, дополненную версию исходных кривых, (ii) целочисленные метки областей, которые содержательно ограничены этими кривыми, и (iii) дополнительные кривые, не ограничивающие никакой области. Основные вычислительные затраты связаны с решением стандартного уравнения Пуассона или, для поверхностей с нетривиальной топологией, разреженной задачи линейного программирования. Мы также вводим специальные базисные функции для представления сингулярностей, естественным образом возникающих в концевых точках разомкнутых кривых.