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

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

Как решить эту задачу на лету? Прямо во время рисования чтобы кривая заменялась на отрезки.

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

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

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

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

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

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

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

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

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

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

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

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

https://msdn.microsoft.com/ru-ru/library/windows/desktop/554h284b(v=vs.85).aspx

http://stackoverflow.com/questions/7054272/how-to-draw-smooth-curve-through-n-points-using-javascript-html5-canvas

http://www.codeproject.com/Articles/31859/Draw-a-Smooth-Curve-through-a-Set-of-D-Points-wit

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

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

https://ru.wikipedia.org/wiki/%D7%E5%F0%E5%EF%E0%F8%FC%FF_%E3%F0%E0%F4%E8%EA%E0

вообще я решал сабж как в 2д так и в 3д...

это классический интерпритарор CNC

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

http://yandex.ru/yandsearch?lr=213&clid=41124&text=постпроцессор+CNC+алгоритм&suggest_reqid=678658736142129963572807754896158

(0) Объясни нафейхуа? В смысле векторная графика занимает минимум, в отличие от растровой.

Зачем её еще и сжимать?

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

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

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

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

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

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

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

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

и тут дело не в разных теоретических алгоритмах а конкретной реалитзации...

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

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

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

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

(26)+ да ник конечно классный, вот только вопрос не соответствует ))

ЗЫ
если рисуем мышкой (или планшетом) то можно еще проще делать

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

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

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

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

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

(30) э? ты случаем или пользователь не учитель-монстр из http://animeonline.su/anime-sub/tv-sub/14747-klass-ubijc-tv-ansatsu-kyoushitsu.html#!/episode/1/myvi/sub ? чтобы на нескольких махах мышкой дрыгать ))

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

(31) чем не устраивают (18) и (28) ?

в курсе что есть проги для cnc-станков которые чертеж преобразуют в команды для станка?

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

и т.д.

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

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

пример:

пользователь рисует прямую линию. Долго, медленно и старательно. вот она:
_____________________________________________

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

Но правильное решение в данном случае было бы запомнить только первую точку и последнюю.

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

(37) растр не рассматривается

(36) гыыы супер контраргумент

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

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

(39) и чему равен Х? пользователь рисует загогулину и линию:

@ _____________________________________



Так не пойдет

(40) это вектор

(36) почитай http://algolist.manual.ru/maths/geom/deluanay.php

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

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

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

пример

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

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

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

.
.
.
.
.
.
..............


.
.
.
.
.
.
..............


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

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

(46) ты почитай... там все написано....

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

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

(52) это тема отдельной БОЛЬШОЙ ветки.... для меня например было минимальные длины перпендикуляров опущеные из точек...

опять-же в моих ссылках все это написано, особенно про ЧПУ...

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

(0) Мой вариант:

Первый:
Как определить, что точку можно удалить?
Задаем максимальную погрешность

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

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

(55) >> берем три точки
Какие именно? Все подряд перебором?

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

(56) начиная с первой и вперед

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

Конечно можно хранить накопленную погрешность.

(0) Что решить, куда решить?
Сколько платишь, такой и алгоритм :)

...сдается мне, что товарищ в (0) хочет халяву...

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

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

Погрешность 1гр, 180 точек, отклонение каждой - 0.5гр.

Как без перебора? и возврата к предыдущим, только по двум точкам?

Просто напиши номера точек, которые должны остаться.

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

(61) ты имеешь в виду вот так чередуются?

-_-_-_-_-_-_-_-_-_-

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

нет, VVVVVVVVVVVVVVVVVVVVVVVVV

VVVVVVVVVVVVVVVVVVVVVV\

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

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

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

у тебя 2 разные задачи

1. векторизация
2. проблемма обработки больших массивов

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

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

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

есть у кого (69) ?

http://yandex.ru/yandsearch?lr=213&clid=41124&text=формула+расстояния+от+точки+до+прямой&suggest_reqid=609124950142501380794825231588462

прервая ссылка

http://ru.onlinemschool.com/math/library/analytic_geometry/p_line1/

зы
если Супер король не может такую элементарную вещь найти в инете, то это ппц....

закрыть-бы ветку, да жалко, вроде люди хотели помоч....

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

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

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

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

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

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

Я задал очень сложный вопрос, на который скорее всего нет простого ответа. Простые ответы типа http://ru.onlinemschool.com/math/library/analytic_geometry/p_line1/  не предлагайте, я их и сам находил.

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

все просто...


наличие тупого угла указывает, что точка "за" границами отрезка

отрезок АБ, точка В, если один из углов АБВ или БАВ более 90 градусов - точка - за

разумеется считать нужно в радианах, там нет пи

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

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

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

(79) так посчитай...

уверяю ты не сможешь обойтись пятью знаками...

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

другой путь - использовать готовые библиотеки

третьего не дано...

(82) кто знает. Вдруг уже кто-то вывел решение этой задачи.

Есть у алгоритма преимущество перед просто формулой - можно использовать условия, сравнения.

Можно нарисовать окружность по точкам используя только сложение и сравнение

http://krasprog.ru/persons.php?page=demidenko&blog=10

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

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

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

Короче, другой алгоритм придумал:

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

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

Что скажете? Какие недостатки могут быть?

плохой алгоритм....

но объяснять не буду, сам думай...

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

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

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

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

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

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

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

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

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

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

(98) сколько будет векторов по твоей методе (один знак - один пиксель)

1. -------_--------

2. ------__--------

Не совсем понял рисунок, но похоже что по три вектора

или один. Зависит от допустимой погрешности

там варианты есть: один, три, пять

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

выбери только два критерия, тогда задачу решить будет проще

(103)+1000

(102) Возможно. И что плохо в алгоритме?

(103) чем не устраивает быстрое качественное и компактное решение (88) ?

(105) неоднозначность решения, а она у тебя есть в алгоритме, будут возникать пограничные ситуации...
(106) оно не качественое...

(106) Проверь свой алгоритм на прямой из многих точек и змейки.

(107) В чем неоднозначность? Увеличиваем погрешность, уменьшается количество векторов. Разве не так?

Чем не качественное?

(108) Проверил, работает.

(110) алгоритм (88) так как он описан не может представить прямую из точек и змейку как один отрезок.

(109) так называемая проблемма "бутылочного горлышка" или "впадин"

проблемма "дребезга" (одичная отстоящая точка)

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

-------------------------------

в идеале нужно задачу решать так
1. Упрощение растра (уменьшение точек, выделение контуров и т.д.)
2. построение сети триангуляции Делона
3. по граням сети определять искомую ломаную
4. замена части сегментов кривыми второго порядка

но этот алгоритм очень трудоемкий, куда более реально это обдход по рпавилу левой/правой руки

(112) нафига ему растр то анализировать? как понял он рисует и на ходу хочет векторизовать

т.е. не просто точки, а они все последовательно выстроены по появлению

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

(113)+ ТС а откат в твоей рисовалке будет? Т.е. как будешь алгоритмизировать если сначала нарисовали а потом стерли часть? И дальше рисуем

и да http://cgm.computergraphics.ru/content/view/41

(111) Почему так думаешь? Наверное ты его не понял. Как ты понял? Давай разберемся.

(112) Слишком сложно, не годится. У меня гораздо проще получилось.

(114) Стереть можно только с конца, Ctrl+Z

(118) я знал! ))

это ты не сразу считай/преобразовывай

а сначала последовательно все точки(пары координат X,Y) в список (решается проблема тормозов и стирания посередине) и только по кнопке запускай алгоритм свой

(119) не. Усложнять так нет необходимости.

(116) как написано так и понял

пример

VVVVVV
______

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

+(121) Смотреть в моноширинном шрифте

(122) Конечно разная. В первом случае заметно длиннее.

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

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

У нас точки - это участки траектории движения ?
Использование кривых второго порядка не позволяет сжать изображение - это только способ получить гладкую кривую.

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

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

(0) Кстати а какова задача (конечная цель) такого алгоритма? Т.е. для чего и зачем решаем траблу?

Всю ветку не осилил, извините.

Методы аппроксимации давно и хорошо проработаны, в том числе и аппроксимации сплайнами. Берешь любой учебник по численным методам. Выбираешь, изучаешь, реализуешь. В чем собственно проблема?

(126) задача совсем другая.
(127) Нужно сократить объем данных записываемых в базу. Пользователь мышкой рисует простую картинку. Ее надо сохранить в колонку желательно не более 1024 байт.
(128) Проблема в создании Алгоритма сжатия векторной графики с потерями, в (0) написано.

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

(129) а размеры картинки в пикселях известны заранее? или в каких пределах? Цветность?

Т.е. может проще будет свой формат растровый изобрести? Например в 1024 байт влазит монохромная картинка 90х90 пикселей.

С вектором не решить проблему роста объема данных. Например когда пользователь очень много линий нарисовал допустим делал отрезки и наделал их 10 0000 штук...

черепашья графика без сжатия влазит 2 маркерные точки на 1 байт, примерно 2000 закрашеных точек, это хватит?

(130) в данном случае дает
(131) размер картинки больше чем 500х500
цветность безразлична.
(132) возможно. Но чем меньше тем лучше, чтобы еще при передаче данных множества картинок уменьшить задержки.

(133) картинка монохром 500х500 растр это 32 кибайта

для векторов на каждую точку надо 4 байта, точнее слегка меньше 9+9 бит = 2,25 байта = 3 байта на точку

на каждый вектор 6 байт, итого в 32 кибайта влезет чуть больше 10 000 векторов (отрезков)

смысла? поле один фиг 500х500? т.е. в случае растра нет никаких ограничений на сложность рисунка в отличие от вектора

(134) смысл в том что в векторе занимает гораздо меньше.
Что за глупые вопросы? задача же понятно сформулирована.

(135) векторизованая в отрезки КРИВАЯ занимает БОЛЬШЕ МЕСТА чем монохромный растр...

(136) ну это же явно ложь. Я писал выше сколько занимает одна и та же картинка в векторе и в растре.

(137) векторизованная кривая занимает места меньше растра только для простых и коротких кривых

(137) окружность с диаметром 6 точек... посчитай :)

(139) посчитал. Растр в сотни раз больше места занял. И что?

(140) плохо считал...6х6 точек растр это 12 бит = 2 байта

(141) сорри ошибся 6х6 = 36 бит = 5 байт

(141) Снова ты ошибся. Ты же сам в прошлый раз насчитал 32 кибайта: (134)

(143) не понял?

в (134) для 500х500 написал что нужно для растра 32 КИЛОбайта (сча общепринятое сокращение КИбайт)

в (141) неправильно сначала посчитал для растра 6х6, нужно 5 байт (просто байт без КИ или КИЛО)

ЗЫ сколько нужно для одного вектора байт? как векторами и сколько их потребуется чтобы нарисовать окружность диаметром 6х6 ?

(144) на такую окружность около 10 векторов каждый по 2 байта плюс 3 байта накладных расходов на формат. итого 23 байта вектор против 32Кб растра. Вектор побеждает.

(145) ммм...мне нравится ваш способ чтения...но

на растр 6х6 надо 5 байт, вообще то, против 23 байт вектор так?

а если перейти к растру 500х500 и нарисованным окружностям от точки в центре с увеличивающимся радиусом +1 пиксель... нет желания посчитать сколько векторов потребуется? растр займет 32 кибайта

ЗЫ учесть что 512 (координаты от 0 до 499) = 2^9, т.е. на один вектор (по две пары чисел для начала и для конца или начала вектора, угла и длины) нужно (9+9)+(9+9) = 36 бит = 4,5 байта

Ну и самое главное то забыли )) Растр замечательно сжимается (несжатый BMP 5мб ~ сжатому PNG 500кб)

(147)+ а проверить как сжимается вектор? )) где будут почти случайные пары чисел

(146) не понятно как у тебя поле 500х500 вдруг сжалось до 6х6, а окружность диаметром 6 превратилась в какую-то бесполезную фигуру.
Спорить нет смысла, я уже проверил опытным путем (97) что вектор занимает во много раз меньше чем jpeg который ты советовал в (92). А теперь вдруг про PNG заговорил.