Сжатие и аппроксимация контура

[MadMaksidrom 0]

Добрый день!

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

Существуют ли какие-нибудь методы или библиотеки для решения данных задач?

[mrgloom 242]

http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A0%D0%B0%D0%BC%D0%B5%D1%80%D0%B0-%D0%94%D1%83%D0%B3%D0%BB%D0%B0%D1%81%D0%B0-%D0%9F%D0%B5%D0%BA%D0%B5%D1%80%D0%B0

Алгоритм Рамера-Дугласа-Пекера

не?

[MadMaksidrom 0]

http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A0%D0%B0%D0%BC%D0%B5%D1%80%D0%B0-%D0%94%D1%83%D0%B3%D0%BB%D0%B0%D1%81%D0%B0-%D0%9F%D0%B5%D0%BA%D0%B5%D1%80%D0%B0

Алгоритм Рамера-Дугласа-Пекера

не?

Для аппроксимации линиями этот алгоритм можно использовать. Но мне нужна аппроксимация не только линиями, но и дугами окружностей.

[mrgloom 242]

требуется "сжать" контур (произвести сдвиг контура по всему периметру) на определенное расстояние.

вообще то я не понял о чем речь.лучше нарисуйте картинку.

но и дугами окружностей.

чо то тут уже попахивает сплайнами.

в оценцв, есть AproxPoly или как то так.

[MadMaksidrom 0]

вообще то я не понял о чем речь.лучше нарисуйте картинку.

чо то тут уже попахивает сплайнами.

в оценцв, есть AproxPoly или как то так.

Картинка ниже.

Сплайн не подходит, нужны линии и дуги.

Одной лишь аппроксимации полилинией, которую выполняет ApproxPoly недостаточно, т.к. получается достаточно большая погрешность.

[mrgloom 242]

теперь понял.

это эквивалентно изменению масштаба.

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

[Smorodov 579]

Вот тут вроде Ваша задача с алгоритмом решения: http://hal.inria.fr/docs/00/57/94/67/PDF/main.pdf

Можно еще здесь посмотреть:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.1863&rep=rep1&type=pdf

[MadMaksidrom 0]

Вот тут вроде Ваша задача с алгоритмом решения: http://hal.inria.fr/docs/00/57/94/67/PDF/main.pdf

Можно еще здесь посмотреть:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.1863&rep=rep1&type=pdf

Спасибо, поизучаю.

[MadMaksidrom 0]

теперь понял.

это эквивалентно изменению масштаба.

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

Вот как раз в этом и вопрос, что значит "просто сжимаете\расширяете".

[mrgloom 242]

ну была точка (10,10) сжали в 2 раза стала (5,5)

[MadMaksidrom 0]

ну была точка (10,10) сжали в 2 раза стала (5,5)

а если не в 2 раза, а на 3 единицы, то что у Вас получится? в какую сторону будете двигать?

[mrgloom 242]

надо определить нормаль для точки контура и сдвинутся по на 3 единицы во внутрь если уменьшение и наружу если увеличение.

[Nuzhny 243]

а если не в 2 раза, а на 3 единицы, то что у Вас получится? в какую сторону будете двигать?

Всё таки нужна более точная постановка задачи.

1. Сжатие - это подобие, а оно определяется коэффициентом. Грубо говоря, "во сколько раз".

2. Так как изображение у нас дискретное, то при уменьшении масштаба получится так, что 2 точки исходного изображения х1 и х2 будут соответствовать 1 точке результирующего у1. И это нормально, согласен? Но в этом случае расстояние [х1, у1] может быть не равно [х2, у1]. То есть постановка задачи в виде "сжать на d единиц" некорректна. Хотя идеальную окружность так сжать можно.

[MadMaksidrom 0]

Всё таки нужна более точная постановка задачи.

1. Сжатие - это подобие, а оно определяется коэффициентом. Грубо говоря, "во сколько раз".

2. Так как изображение у нас дискретное, то при уменьшении масштаба получится так, что 2 точки исходного изображения х1 и х2 будут соответствовать 1 точке результирующего у1. И это нормально, согласен? Но в этом случае расстояние [х1, у1] может быть не равно [х2, у1]. То есть постановка задачи в виде "сжать на d единиц" некорректна. Хотя идеальную окружность так сжать можно.

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

[MadMaksidrom 0]

надо определить нормаль для точки контура и сдвинутся по на 3 единицы во внутрь если уменьшение и наружу если увеличение.

Абсолютно верно, вот я как раз и спрашивал о существующих алгоритмах и библиотеках для автоматизации этого процесса.

[Smorodov 579]

Это ведь задача построения эквидистанты, как я понял?

http://pmpu.ru/vf4/dets/discrim/equidist

http://sets.ru/base/41nomer/malkov/1.pdf

http://forum.shelek.ru/index.php/topic,26282.0.html

Ну и этот монстр наверняка все это может: http://www.cgal.org/

[mrgloom 242]

надо определить нормаль для точки контура и сдвинутся по на 3 единицы во внутрь если уменьшение и наружу если увеличение.

Абсолютно верно, вот я как раз и спрашивал о существующих алгоритмах и библиотеках для автоматизации этого процесса.

ну брать небольшие группы точек и заменять их отрезком из середины отрезка строить перпендикуляр.

правда не знаю насколько это будет точно.

или например пройтись по всем точкам контура последовательностью точек длинной К, так что средняя точка последовательности будет являться точкой из которой следует провести перпендикуляр,берем концевые точки и соединяем с этой точкой получаем 2 отрезка, определяем угол между ними и проводим нормаль как бисектрису этого угла.

наверно еще кривую надо сгладить изначально.