Какой алгоритм или идея, чтобы найти выпуклую оболочку из набора кривых?

Question

Давайте определим кривую как набор двухмерных точек, которые можно вычислить с произвольной точностью. Например, это кривая:

Дается набор из N пересекающихся кривых (N может быть сколь угодно большим), как показано на следующем рисунке:

Как найти периметр соединяемой области (в случае необходимости указывается ограничительная рамка), которая ограничена набором кривых; или, учитывая приведенный выше пример, красная кривая? Обратите внимание, что периметр может быть вогнутым и не имеет явной параметризации.

• Можно указать начальную точку красной кривой
• Меня интересуют эффективные идеи для построения общего алгоритма, однако ...
• Я пишу на C ++ и могу использовать любую библиотеку с открытым исходным кодом, чтобы помочь с этим
• Я не знаю, есть ли у этой проблемы имя или есть готовое решение, на случай, пожалуйста, дайте мне знать, и я отредактирую заголовок и теги.

Дополнительные примечания:

• Решение уникально, так как в интересующей области есть только одна связная область, свободная от любой кривой, но, конечно, я могу вычислить только конечное число кривых.
• Кривые изначально параметризованы (а затем применяются аффинные преобразования), поэтому я могу добавить столько точек, сколько захочу. Я могу вычислить расстояния, длины и идти вместе с ними. Пересечения также возможны. В принципе, допустима любая геометрическая операция, которая может быть построена из координат точки.
• Я обнаружил, что похожая проблема возникает при «резании» передач, например. https://scialert.net/fulltext/?doi=jas.2014.362.367, но все же я не вижу, как решить это прилично эффективным способом.

Answer 1

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

Тогда первое приближение огибающей - это ломаная линия через эти точки.

Еще одно приближение можно получить, рисуя общую касательную к последовательным кривым и пересекая эти касательные попарно. Во всяком случае, общая касательная проблема сложнее.

---

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

Answer 2

Когда у меня возникают такие проблемы (математика недостаточна или ужасно сложна), я разбиваю каждую кривую на сегменты.

Затем я ищу пересечения сегмент-сегмент.Например, сегмент на кривой Ci со всеми сегментами на кривой Cj.Даже вы можете заменить сегмент его ограничивающим прямоугольником и выполнить пересечение прямоугольного блока для быстрого сброса, фокусируясь на тех прямоугольниках, которые имеют пересечение.

Это дает грубое приближение пересечения кривой с кривой.

Помимо пересечений вы можете искать максимальные / минимальные координаты, приблизительно также с сегментами или прямоугольниками.

Получив подходящее приближение, вы можете уточнить его, уменьшив длину / размер сегментов и блоков и повторивпроверки пересечения (или макс / мин).

Answer 3

Вы можете иметь приблизительное решение, используя сетки. Сначала найдите ограничивающий прямоугольник для кривых. А потом скручиваем внутри ограничительной рамки. а затем поиск по ячейкам, чтобы найти указанную область. И, наконец, с помощью количества ячеек по периметру приблизите значение периметра (так как размер ячеек известен).