Алгоритм сжатия векторной графики с потерями #735226

Рисуем мышкой любую линию. Кривую или ровную. Линия состоит из точек. Точек слишком много чтобы их координаты запомнить. Можно эти точки заменить соединенными отрезками, ломаной прямой, тогда нужно будет только запомнить координаты узловых точек, которых гораздо меньше, но качество при этом потеряется. нужно придумать алгоритм, при котором качество "на глаз" будет теряться одинаково не зависимо от кривизны и сложности линий. То есть если тупо соединять прямыми каждую десятую точку, то на плавных почти ровных участках с большим радиусом кривизны качество будет теряться меньше чем на крутых загибах маленького радиуса. Как решить эту задачу на лету? Прямо во время рисования чтобы кривая заменялась на отрезки.

Рисуем мышкой любую линию. Кривую или ровную. Линия состоит из точек. Точек слишком много чтобы их координаты запомнить. Можно эти точки заменить соединенными отрезками, ломаной прямой, тогда нужно будет только запомнить координаты узловых точек, которых гораздо меньше, но качество при этом потеряется. нужно придумать алгоритм, при котором качество "на глаз" будет теряться одинаково не зависимо от кривизны и сложности линий. То есть если тупо соединять прямыми каждую десятую точку, то на плавных почти ровных участках с большим радиусом кривизны качество будет теряться меньше чем на крутых загибах маленького радиуса. Как решить эту задачу на лету? Прямо во время рисования чтобы кривая заменялась на отрезки.

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

Ставишь точку 0 в точке начала кривой, через некий шаг(S) нарисованной кривой ставишь точку 1 и так далее. Потом апроксимируешь чем хочешь.

Так работает выделение контура в фотошопе и гимпе. Исходники гимпа открыты, можешь там посмотреть.

слишком сложно разбираться в коде ради просто алгоритма

Я думаю что критерия добавления каждой следующей точки должно быть два: 1. Угол отклонения следующего отрезка относительно предыдущего превысил определенный максимум. Это для мелких резких поворотов. 2. Нужно ограничить не только угол, но и расстояние следующей точки от прямой предыдущего отрезка. Это для больших плавных линий.

Что ты велосипеды изобретаешь? Почитай про сплайны и возьми наиболее подходящий метод.

Не мешай человеку ) Он науку двигает )

Если я сейчас вспомню свой диплом... :) Можно по принципу тахеометрической съемки: есть исходная нулевая точка съемки. От нее откладываем точки (X, Y, угол (если нужно)). После нанесения всех точек - соединяем. Упрощенно :)

+ Насколько я помню, есть еще минимальный шаг для точек.

кто-нибудь кроме понял ?

Чо тут понимать, название темы идиотское. Сжимать векторную графику - ты сам-то понял?

Ты же не в 1С свои сплайны рисовать?

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

Как рисовать сплайны я знаю. Вопрос был по каким точкам их рисовать.

вообще я решал сабж как в 2д так и в 3д... это классический интерпритарор CNC при решении я намеренно отказался от кривых, все делал отрезками, это на порядок упростило задачу...

Объясни нафейхуа? В смысле векторная графика занимает минимум, в отличие от растровой. Зачем её еще и сжимать? Это к тому что тему, назвал неправильно, тебе нужен алгоритм аппроксимации произвольных кривых - такое легко решается сплайнами. Суть в чем у тебя есть шаблоны кривых (разных) и можно любую свою произвольную кривую разбить на нужные кусочки, найти эти кусочки на шаблонах и указать координаты оттуда.

станки с ЧПУ сплошные. Ты о чем?

не надо с растровой сравнивать, тогда не будет казаться что она мало места занимает

Помню, в универе одногруппник делал курсовую по кривым Безье (вроде 2-го порядка). Высокая точность и производительность решения. Попробуй их замутить.

ага, я именно их и использую.

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

да пофиг на сплайны. С прямыми отрезками бы сначала разобраться.

вообще то прямая это частный случай кривой )) вырожденный такой случай так что если разобраться с кривыми, то прямые тоже решены

А по теме кто-нибудь может помочь?

+ да ник конечно классный, вот только вопрос не соответствует )) ЗЫ если рисуем мышкой (или планшетом) то можно еще проще делать кодируем не линию а движения мышки (пера) а они чем могут быть описаны? радиус-вектор (угол и длина перемещения) и временем т.е. просто через интервал времени берем угол движения, и зная начальную точку, интервал и углы строим линию, дл контроля используем конечную точку завершения рисования (координаты как и начальной)

а по теме ну не вижу проблемы как и прочие кто отписался, методов можно применить множество какой брать это уже на вкус

Через интервал времени не подойдет. Если пользователь быстро будет дергать мышкой, можно упустить что-то заметное.

Хоть бы один метод предложили.

э? ты случаем или пользователь не учитель-монстр из ? чтобы на нескольких махах мышкой дрыгать )) под интервалом подразумевалась часть секунды...очень маленькая например 100 или даже 10 миллисекунд чем не устраивают и ? в курсе что есть проги для cnc-станков которые чертеж преобразуют в команды для станка?

1. метод правой руки (не путать с левой) :) 2. метод "усечения" 3. метод перебора 4. метод "строй и перестраивай" и т.д.

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

Наверняка уже все придумано. Просто загугли

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

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

растр не рассматривается

гыыы супер контраргумент только можно же вместо интервала, точнее проверку-обработку то делаем все равно по интервалу, но вот кусочки берем от их длины не? т.е. кусок меньше X то ждем пока будет >=

пользователь рисует линию - это и есть растр

и чему равен Х? пользователь рисует загогулину и линию: @ _____________________________________ Так не пойдет

это вектор

почитай твой случай это упрощенная частность триангуляции....

зачем? наверное ты не правильно вопрос понял

я правильно понял, ты ресушь и тебе нужен векторы, хитрость в том, что нельзя расматривать дискретность по времени, каждый раз нужно откатывать немного назад и строить кусок до конца, это и есть "строй и перестраивай" пример нарисовал --~~~-- (3 вектора) потом добавил --~~~---- программа откатила последний вектор и проанализировала хвост заново, получили сново 3 вектора, но последний более длинный

попонятнее можно? Вот пользователь рисует. появилась точка. потом вторая. потом третья. и так далее. в какой момент можно сказать что некоторые предыдущие точки делаем одной линией, и начиная с какой-то из точек начинаем следующую линию? И какую точку выбрать?

Вот так например рисует: . . . . . . ..............

[1c] . . . . . . .............. [/1c]

[code] . . . . . . .............. [/code]

[ахалаймахалай] . . . . . . .............. [/ахалаймахалай]

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

как сравнить какой результат лучше?

это тема отдельной БОЛЬШОЙ ветки.... для меня например было минимальные длины перпендикуляров опущеные из точек... опять-же в моих ссылках все это написано, особенно про ЧПУ...

это я в писал. плюс еще минимальный угол отклонения

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

>> берем три точки Какие именно? Все подряд перебором? Нужен алгоритм наиболее простой, без переборов множества вариантов. Что-то вроде: Берем очередную точку, проверяем условие, если сработало то начинаем новый отрезок и продолжаеи, иначе просто продолжаем. Нужно только придумать условие

начиная с первой и вперед если без переборов - то представь ситуацию, 180 точек, отклонение каждой - 1гр., в пределах погрешности. Вместо полукруга получим прямую. Конечно можно хранить накопленную погрешность.

Что решить, куда решить? Сколько платишь, такой и алгоритм :) ...сдается мне, что товарищ в хочет халяву...

+Давай свой Код, вот тогда можно и обсудить :)

отклонение первой точки 1гр, второй 2гр, третьей уже 3гр. и постоянно растет пока не достигнет максимальной погрешности

Погрешность 1гр, 180 точек, отклонение каждой - 0.5гр. Как без перебора? и возврата к предыдущим, только по двум точкам? Просто напиши номера точек, которые должны остаться. Усложним пример. Отклонения точек чередуются - +-1гр., отклонение в не допуска. между первой и второй, и предпоследней и последней - расстояние в 2 раза меньше остальных. - т.е. надо реализовать вырождение ломаной в прямую

ты имеешь в виду вот так чередуются? -_-_-_-_-_-_-_-_-_- если отклонение вне допуска, то в прямую нельзя преобразовать. будет ломаная.

нет, VVVVVVVVVVVVVVVVVVVVVVVVV

VVVVVVVVVVVVVVVVVVVVVV

он не хочет читать и искать, он хочет готовое решение, он-же король :)

ну да. по прежнему если отклонение вне допуска, то в прямую нельзя преобразовать. будет ломаная

первая и последняя - на оси ломаной. т.е. все точки в допуске

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

короче, нужна формула желательно состоящая из простых арифметических действий: Расстояние от точки до прямой заданной двумя точками.

есть у кого ?

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

эта ссылка у меня цветом как уже просмотренная. Там нет ответа на мой вопрос.

можно приближенную формулу, адаптированную для компа.

чем формула d = (AMy + C)/sqrt(AB) не подходит? наличием корня? или ты не знаешь как подставлять координаты?

d = (A My + C)/sqrt(A B)

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

Например sqrt(А^2 + B^2) можно упростить до А + В, такой точности вполне достаточно.

все просто... наличие тупого угла указывает, что точка "за" границами отрезка отрезок АБ, точка В, если один из углов АБВ или БАВ более 90 градусов - точка - за разумеется считать нужно в радианах, там нет пи

каких углов? Углы не известны

а вообще я когда этим занимался активно использова понятие "четверти"...

сам угол рассчитывать тоже не нужно, достаточно узнать синус угла, и сравнивать с синусом угла погрешности.

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

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

хорошая ссылка. спасибо

еще и в Красноярском крае. Вообще замечательно

вот готовая формула: ( (ax-ox)*(by-oy)-(bx-ox)*(ay-oy) ) / sqrt( (ax-bx)*(ax-bx) + (ay-by)*ay-by) )

Короче, другой алгоритм придумал: 1. Накапливаем сумму расстояний между точками, получаем пройденный путь. 2. Считаем расстояние между первой точкой и последней. 3. Сравниваем эти два результата. 4. Если они равны в пределах погрешности, значит пока линия можно считать что прямая. Погрешность может зависеть от длины отрезка, т.е. на коротких отрезках погрешность меньше, пропорциональна длине отрезка. 5. Если результаты сильно разные, завершаем старый отрезок и начинаем новый. Этот алгоритм лучше чем предыдущий тем что проще в понимании, а так же лишен недостатка когда пользователь рисует прямую линию и возвращается по той же прямой обратно. Что скажете? Какие недостатки могут быть?

плохой алгоритм.... но объяснять не буду, сам думай...

Фактически в векторной графике храняться координаты точки, R(вектор), Направление V вектор, и кривизна A. Модель очень подходит под физическое косочно-равноускоренное движение материальной точки. Или "лекало". Суть приближения состоит в том, чтобы превратить кривую в несколько переходящих друг в друга дуг окружностей. Для такого приближения, мы подставляем к исходной точке дугу окружности и увеличиваем радиус этой окружности пока 1. Отклонение от кривой, вычисленное методом наименьших квадратов на покрываемую длину кривой будет наименьшим, оставаясь при этом в рамках допустимого отклонения для этой степени сжатия. Таким образом алгоритм похож на действия человека, который подставляет к кривой лекало и двигает его, пытаясь получить максимальное приближение поверхности лекала к кривой на максимальный отрезок кривой, с некоторым, допустимым для данного человека, приближением

чето тут велик конструируют с квадратными колесами. правильнее будет собрать матрицу данных и сжать ее LZ

а я предлагаю нарисовать и сохранить в jpeg ... двуцветный сжатый jpg это никакой вектор не угонится за минимальностью ))

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

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

это сжатие без потерь. Не годится

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

сделал тест. Одна черная линия на белом фоне. 10 тысяч байт файл получился ! ! ! Вместо 18 байт векторной графики - 10 тысяч! Зачем давать глупые советы?

не нашел в нем ничего плохого. Что не так?