Приблизительный список точек с кратким списком кривых Безье
У меня есть список (x, y) точки. Я знаю, как составить список кривых Безье, которые проходят через все эти точки и имеют непрерывную первую (и вторую, хотя и менее важную) производную. Однако список, который я заканчиваю, слишком длинный. Я бы предпочел приблизить точки, которые у меня есть, если это позволит мне сократить количество кривых, которые у меня есть. Я хотел бы быть в состоянии передать параметр либо, насколько близко я получаю приближение, или максимальное количество кривых, предпочтительно первый.
Причина, по которой я хочу, заключается в том, что конечный результат будет иметь графический пользовательский интерфейс, где пользователи могут редактировать кривые Безье, и не критично, что кривые проходят точно через каждую точку, пока они находятся близко. Чем больше кривых, тем сложнее редактировать.
РЕДАКТИРОВАТЬ: Еще немного информации о цели этого. Я пытаюсь сделать программное обеспечение для редактирования изображений. Когда кто-то загружает растровое изображение, я хочу иметь возможность отследить центральную линию. Potrace - это то, что я бы использовал, чтобы проследить контур фигуры, но он не будет работать для отслеживания штрихов. Мне удалось определить множество точек вдоль центральной линии, и я хочу превратить эти данные в список связанных кривых Безье. Причина, по которой я не хочу создавать сплайн Безье, состоит в том, что будет слишком много контрольных точек, чтобы их было легко редактировать. "Слишком много" - это не простой для определения термин, но я хотел бы иметь возможность передать параметр, чтобы ограничить количество кривых. Либо функция, которая минимизирует расстояние до кривых от точек на основе максимального количества кривых, либо функция, которая минимизирует количество кривых на основе максимального отклонения от точек.
1 ответ
Существует несколько подходов для достижения того, что вы хотите сделать:
1) Используйте алгоритм RDP, чтобы уменьшить количество точек, затем создайте список кривых Безье, проходящих через оставшиеся точки.
2) Используйте алгоритмы подбора кривой (например, алгоритм Шнайдера), чтобы получить несколько кривых Безье, которые связаны с непрерывностью G1 (касательной). Ознакомьтесь с реализацией алгоритма Шнайдера по этой ссылке.
3) Используйте метод наименьших квадратов с B-сплайном, чтобы получить одну кривую B-сплайна.
С точки зрения реализации, подход 1, вероятно, самый простой для вас, поскольку вы уже знаете, как создавать кривые Безье, интерполирующие список точек. Подход 3 будет гораздо сложнее реализовать, и вам, вероятно, придется преобразовать кривую B-сплайна в кривые Безье, чтобы использовать их на уровне пользовательского интерфейса. Пожалуйста, обратитесь к этой статье SO для подробного обсуждения.