Подскажите в какую сторону копать для решения следующей задачки: есть множество точек на плоскости p[N]. Нужно получить подмножество p1[M] таким образом, чтобы при интерполяции набора p1 кривыми Безье (например, как в алгоритме на antigrain), максимальная ошибка (растояние от кривой Безье к ламаной из набора p) не превышала заданное число.

Здравствуйте, IAF, Вы писали:

IAF>Подскажите в какую сторону копать для решения следующей задачки: есть множество точек на плоскости p[N]. Нужно получить подмножество p1[M] таким

Есть метод упрощения ломаных Дугласа-Пекерп (Douglas-Peucker), но критерии в нем, конечно, другие.

Здравствуйте, MBo, Вы писали:

MBo>Здравствуйте, IAF, Вы писали:

IAF>>Подскажите в какую сторону копать для решения следующей задачки: есть множество точек на плоскости p[N]. Нужно получить подмножество p1[M] таким

MBo>Есть метод упрощения ломаных Дугласа-Пекерп (Douglas-Peucker), но критерии в нем, конечно, другие.

Отлично! Метод должен полностью удовлетворить нужные условия.

IAF>Отлично! Метод должен полностью удовлетворить нужные условия.

Конечно, хорошо, если это решит вашу задачу, но той постановке задачи, которую вы привели, это решение, к сожалению, не удовлетворяет.

Алгоритм Дагласа-Пикера выдает на входе ломаную, вершины которой являются подмножеством вершин исходной ломаной, и которая не отклоняется от исходной ломаной больше чем на заданное линейное расстояние.

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

То есть две погрешности складываются — погрешность упрощения ломаной и погрешность интерполяции.

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

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

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

Здравствуйте, Аноним, Вы писали:

IAF>>Отлично! Метод должен полностью удовлетворить нужные условия.

А>Конечно, хорошо, если это решит вашу задачу, но той постановке задачи, которую вы привели, это решение, к сожалению, не удовлетворяет.

А>Алгоритм Дагласа-Пикера выдает на входе ломаную, вершины которой являются подмножеством вершин исходной ломаной, и которая не отклоняется от исходной ломаной больше чем на заданное линейное расстояние.

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

А>То есть две погрешности складываются — погрешность упрощения ломаной и погрешность интерполяции.

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

А>Короче, Даглас-Пикер здесь вообще не поможет (на самом деле, Даглас-Пикер был первым алгоритмом, про который я вспомнил, когда столкнулся с данной задачей).

А>Сам интересуюсь решением данной задачи. Судя по всему, она относится к разряду нетривиальных.

Цель следующая: использую мишь (или перо) юзверь рисует произвольную кривую. Т.е. у меня получается последовательность точек через которую прошел курсор. Мне нужно интерполировать нарисованную "кракозяблу" кривыми Безье (естественно с определенной погрешностью). Использование Даглас-Пикер помогло в основном на прямолинейных и "слабо градиентных" участках. а вот на резких поворотах получается "не то".