|
Алгоритм сжатия векторной графики с потерями | ☑ | ||
---|---|---|---|---|
0
Супер король
26.02.15
✎
08:28
|
Рисуем мышкой любую линию. Кривую или ровную.
Линия состоит из точек. Точек слишком много чтобы их координаты запомнить. Можно эти точки заменить соединенными отрезками, ломаной прямой, тогда нужно будет только запомнить координаты узловых точек, которых гораздо меньше, но качество при этом потеряется. нужно придумать алгоритм, при котором качество "на глаз" будет теряться одинаково не зависимо от кривизны и сложности линий. То есть если тупо соединять прямыми каждую десятую точку, то на плавных почти ровных участках с большим радиусом кривизны качество будет теряться меньше чем на крутых загибах маленького радиуса. Как решить эту задачу на лету? Прямо во время рисования чтобы кривая заменялась на отрезки. |
|||
1
Супер король
26.02.15
✎
08:30
|
Можно усложнить задачу используя вместо прямых отрезков кривые второго, третьего порядков. Сплайны. Безье.
|
|||
2
Лодырь
26.02.15
✎
08:38
|
Ставишь точку 0 в точке начала кривой, через некий шаг(S) нарисованной кривой ставишь точку 1 и так далее. Потом апроксимируешь чем хочешь.
|
|||
3
Asmody
26.02.15
✎
08:39
|
Так работает выделение контура в фотошопе и гимпе. Исходники гимпа открыты, можешь там посмотреть.
|
|||
4
Супер король
26.02.15
✎
08:43
|
(3) слишком сложно разбираться в коде ради просто алгоритма
|
|||
5
Супер король
26.02.15
✎
08:48
|
Я думаю что критерия добавления каждой следующей точки должно быть два:
1. Угол отклонения следующего отрезка относительно предыдущего превысил определенный максимум. Это для мелких резких поворотов. 2. Нужно ограничить не только угол, но и расстояние следующей точки от прямой предыдущего отрезка. Это для больших плавных линий. |
|||
6
Крошка Ру
26.02.15
✎
08:57
|
(5) Что ты велосипеды изобретаешь? Почитай про сплайны и возьми наиболее подходящий метод.
|
|||
7
Лодырь
26.02.15
✎
08:59
|
(6) Не мешай человеку ) Он науку двигает )
|
|||
8
Масянька
26.02.15
✎
09:07
|
(5) Если я сейчас вспомню свой диплом... :)
Можно по принципу тахеометрической съемки: есть исходная нулевая точка съемки. От нее откладываем точки (X, Y, угол (если нужно)). После нанесения всех точек - соединяем. Упрощенно :) |
|||
9
Масянька
26.02.15
✎
09:09
|
+(8) Насколько я помню, есть еще минимальный шаг для точек.
|
|||
10
Супер король
26.02.15
✎
09:20
|
кто-нибудь кроме Asmody понял (0)?
|
|||
11
iamnub
26.02.15
✎
09:32
|
(10)
Чо тут понимать, название темы идиотское. Сжимать векторную графику - ты сам-то понял? |
|||
12
iamnub
26.02.15
✎
09:36
|
||||
13
iamnub
26.02.15
✎
09:37
|
||||
14
Lama12
26.02.15
✎
09:38
|
(0) Сжимать векторную графику не получится. Ее суть в том, что полученное изображением можно масштабировать без потерь качества. То, как поставлена задача, говорит о том, что изображение векторным не будет.
Да и что мешает рассмотреть алгоритмы поиска функции интерполяции, возможно на описание такой функции уйдет меньше информации, хотя х.з. |
|||
15
Супер король
26.02.15
✎
09:39
|
(12) Как рисовать сплайны я знаю. Вопрос был по каким точкам их рисовать.
|
|||
16
vde69
26.02.15
✎
09:51
|
||||
17
vde69
26.02.15
✎
09:53
|
вообще я решал сабж как в 2д так и в 3д...
это классический интерпритарор CNC при решении я намеренно отказался от кривых, все делал отрезками, это на порядок упростило задачу... |
|||
18
vde69
26.02.15
✎
09:54
|
||||
19
Garykom
гуру
26.02.15
✎
09:59
|
(0) Объясни нафейхуа? В смысле векторная графика занимает минимум, в отличие от растровой.
Зачем её еще и сжимать? Это к тому что тему, назвал неправильно, тебе нужен алгоритм аппроксимации произвольных кривых - такое легко решается сплайнами. Суть в чем у тебя есть шаблоны кривых (разных) и можно любую свою произвольную кривую разбить на нужные кусочки, найти эти кусочки на шаблонах и указать координаты оттуда. |
|||
20
Супер король
26.02.15
✎
10:20
|
(18) станки с ЧПУ сплошные. Ты о чем?
|
|||
21
Супер король
26.02.15
✎
10:22
|
(19) не надо с растровой сравнивать, тогда не будет казаться что она мало места занимает
|
|||
22
Drac0
26.02.15
✎
10:25
|
(0) Помню, в универе одногруппник делал курсовую по кривым Безье (вроде 2-го порядка). Высокая точность и производительность решения. Попробуй их замутить.
|
|||
23
Супер король
26.02.15
✎
10:25
|
(22) ага, я именно их и использую.
|
|||
24
vde69
26.02.15
✎
10:38
|
(23) дело все в том, что разные системы сплайны делают по разному, одна и таже модель в каде и максе будут отличны визульно для эксперта.
простой пример - обводы автомобилей, опытный человек по внешнему виду машины может сказать в какой программе делалось... и тут дело не в разных теоретических алгоритмах а конкретной реалитзации... |
|||
25
Супер король
26.02.15
✎
10:40
|
(24) да пофиг на сплайны. С прямыми отрезками бы сначала разобраться.
|
|||
26
Garykom
гуру
26.02.15
✎
11:01
|
(25) вообще то прямая это частный случай кривой )) вырожденный такой случай
так что если разобраться с кривыми, то прямые тоже решены |
|||
27
Супер король
26.02.15
✎
11:06
|
А по теме кто-нибудь может помочь?
|
|||
28
Garykom
гуру
26.02.15
✎
11:07
|
(26)+ да ник конечно классный, вот только вопрос не соответствует ))
ЗЫ если рисуем мышкой (или планшетом) то можно еще проще делать кодируем не линию а движения мышки (пера) а они чем могут быть описаны? радиус-вектор (угол и длина перемещения) и временем т.е. просто через интервал времени берем угол движения, и зная начальную точку, интервал и углы строим линию, дл контроля используем конечную точку завершения рисования (координаты как и начальной) |
|||
29
Garykom
гуру
26.02.15
✎
11:09
|
(27) а по теме ну не вижу проблемы как и прочие кто отписался, методов можно применить множество какой брать это уже на вкус
|
|||
30
Супер король
26.02.15
✎
11:10
|
(28) Через интервал времени не подойдет. Если пользователь быстро будет дергать мышкой, можно упустить что-то заметное.
|
|||
31
Супер король
26.02.15
✎
11:10
|
(29) Хоть бы один метод предложили.
|
|||
32
Garykom
гуру
26.02.15
✎
11:15
|
(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-станков которые чертеж преобразуют в команды для станка? |
|||
33
vde69
26.02.15
✎
11:16
|
(31)
1. метод правой руки (не путать с левой) :) 2. метод "усечения" 3. метод перебора 4. метод "строй и перестраивай" и т.д. |
|||
34
Супер король
26.02.15
✎
11:20
|
(32) в (18) просто яндекс, ничего конкретного
в (28) я уже сказал чем не устраивает. интервалы не подойдут, так как не оптимальны. |
|||
35
Гёдза
26.02.15
✎
11:22
|
Наверняка уже все придумано. Просто загугли
|
|||
36
Супер король
26.02.15
✎
11:23
|
пример:
пользователь рисует прямую линию. Долго, медленно и старательно. вот она: _____________________________________________ на каждый пиксель уходит пять раз по 10 миллисекунд. Получается если делать интервалами времени, то объем данных будет в пять раз больше чем если бы использовали просто пиксели. Но правильное решение в данном случае было бы запомнить только первую точку и последнюю. |
|||
37
Гёдза
26.02.15
✎
11:25
|
есть алгоритмы преобразования растра в вектор.
Именно твой случай |
|||
38
Супер король
26.02.15
✎
11:26
|
(37) растр не рассматривается
|
|||
39
Garykom
гуру
26.02.15
✎
11:27
|
(36) гыыы супер контраргумент
только можно же вместо интервала, точнее проверку-обработку то делаем все равно по интервалу, но вот кусочки берем от их длины не? т.е. кусок меньше X то ждем пока будет >= |
|||
40
Гёдза
26.02.15
✎
11:27
|
(38) пользователь рисует линию - это и есть растр
|
|||
41
Супер король
26.02.15
✎
11:30
|
(39) и чему равен Х? пользователь рисует загогулину и линию:
@ _____________________________________ Так не пойдет |
|||
42
Супер король
26.02.15
✎
11:30
|
(40) это вектор
|
|||
43
vde69
26.02.15
✎
11:31
|
(36) почитай http://algolist.manual.ru/maths/geom/deluanay.php
твой случай это упрощенная частность триангуляции.... |
|||
44
Супер король
26.02.15
✎
11:32
|
(43) зачем? наверное ты не правильно вопрос понял
|
|||
45
vde69
26.02.15
✎
11:42
|
(44) я правильно понял, ты ресушь и тебе нужен векторы, хитрость в том, что нельзя расматривать дискретность по времени, каждый раз нужно откатывать немного назад и строить кусок до конца, это и есть "строй и перестраивай"
пример нарисовал --~~~-- (3 вектора) потом добавил --~~~---- программа откатила последний вектор и проанализировала хвост заново, получили сново 3 вектора, но последний более длинный |
|||
46
Супер король
26.02.15
✎
11:57
|
(45) попонятнее можно?
Вот пользователь рисует. появилась точка. потом вторая. потом третья. и так далее. в какой момент можно сказать что некоторые предыдущие точки делаем одной линией, и начиная с какой-то из точек начинаем следующую линию? И какую точку выбрать? |
|||
47
Супер король
26.02.15
✎
11:59
|
Вот так например рисует:
. . . . . . .............. |
|||
48
Супер король
26.02.15
✎
12:03
|
|
|||
49
Супер король
26.02.15
✎
12:03
|
[code]
. . . . . . .............. [/code] |
|||
50
Супер король
26.02.15
✎
12:04
|
[ахалаймахалай]
. . . . . . .............. [/ахалаймахалай] |
|||
51
vde69
26.02.15
✎
12:06
|
(46) ты почитай... там все написано....
ты разрушаешь последние элемент и строиш новый, потом разрушаешь предпоследний и строишь новый, сравниваешь два результата, выбираешь лучший, если луший получился разрушением двух сегментов - продолжаешь разрушать и строить с третего и так далее... |
|||
52
Супер король
26.02.15
✎
12:17
|
(51) как сравнить какой результат лучше?
|
|||
53
vde69
26.02.15
✎
12:23
|
(52) это тема отдельной БОЛЬШОЙ ветки.... для меня например было минимальные длины перпендикуляров опущеные из точек...
опять-же в моих ссылках все это написано, особенно про ЧПУ... |
|||
54
Супер король
26.02.15
✎
12:28
|
(53) это я в (5) писал. плюс еще минимальный угол отклонения
|
|||
55
Rebelx
26.02.15
✎
12:28
|
(0) Мой вариант:
Первый: Как определить, что точку можно удалить? Задаем максимальную погрешность берем три точки, строим прямую между первой и последней. Если максимальное отклоненение отрезка от точки меньше погрешности - среднюю точку можно удалить. Добавляем следующую точку для анализа и т.д. Дополнение: Можно попробовать сместить крайние точки в пределах погрешности, и тогда может быть средняя окажется лишней - см.выше. |
|||
56
Супер король
26.02.15
✎
12:41
|
(55) >> берем три точки
Какие именно? Все подряд перебором? Нужен алгоритм наиболее простой, без переборов множества вариантов. Что-то вроде: Берем очередную точку, проверяем условие, если сработало то начинаем новый отрезок и продолжаеи, иначе просто продолжаем. Нужно только придумать условие |
|||
57
Rebelx
26.02.15
✎
12:51
|
(56) начиная с первой и вперед
если без переборов - то представь ситуацию, 180 точек, отклонение каждой - 1гр., в пределах погрешности. Вместо полукруга получим прямую. Конечно можно хранить накопленную погрешность. |
|||
58
DrZombi
гуру
26.02.15
✎
12:54
|
(0) Что решить, куда решить?
Сколько платишь, такой и алгоритм :) ...сдается мне, что товарищ в (0) хочет халяву... |
|||
59
DrZombi
гуру
26.02.15
✎
12:54
|
+(0)Давай свой Код, вот тогда можно и обсудить :)
|
|||
60
Супер король
26.02.15
✎
13:17
|
(57) отклонение первой точки 1гр, второй 2гр, третьей уже 3гр. и постоянно растет пока не достигнет максимальной погрешности
|
|||
61
Rebelx
26.02.15
✎
13:24
|
Погрешность 1гр, 180 точек, отклонение каждой - 0.5гр.
Как без перебора? и возврата к предыдущим, только по двум точкам? Просто напиши номера точек, которые должны остаться. Усложним пример. Отклонения точек чередуются - +-1гр., отклонение в не допуска. между первой и второй, и предпоследней и последней - расстояние в 2 раза меньше остальных. - т.е. надо реализовать вырождение ломаной в прямую |
|||
62
Супер король
26.02.15
✎
13:30
|
(61) ты имеешь в виду вот так чередуются?
-_-_-_-_-_-_-_-_-_- если отклонение вне допуска, то в прямую нельзя преобразовать. будет ломаная. |
|||
63
Rebelx
26.02.15
✎
13:31
|
нет, VVVVVVVVVVVVVVVVVVVVVVVVV
|
|||
64
Rebelx
26.02.15
✎
13:31
|
VVVVVVVVVVVVVVVVVVVVVV\
|
|||
65
vde69
26.02.15
✎
13:32
|
(61) он не хочет читать и искать, он хочет готовое решение, он-же король :)
|
|||
66
Супер король
26.02.15
✎
14:00
|
(63) ну да. по прежнему если отклонение вне допуска, то в прямую нельзя преобразовать. будет ломаная
|
|||
67
Rebelx
26.02.15
✎
15:17
|
(66) первая и последняя - на оси ломаной. т.е. все точки в допуске
|
|||
68
vde69
26.02.15
✎
15:21
|
у тебя 2 разные задачи
1. векторизация 2. проблемма обработки больших массивов по этому твоя задача решается только применением двух алгоритмов одновременно... а ты обсуждаешь только один алгоритм.... |
|||
69
Супер король
27.02.15
✎
07:20
|
короче, нужна формула желательно состоящая из простых арифметических действий:
Расстояние от точки до прямой заданной двумя точками. |
|||
70
Супер король
27.02.15
✎
08:36
|
есть у кого (69) ?
|
|||
71
vde69
модератор
27.02.15
✎
08:47
|
http://yandex.ru/yandsearch?lr=213&clid=41124&text=формула+расстояния+от+точки+до+прямой&suggest_reqid=609124950142501380794825231588462
прервая ссылка http://ru.onlinemschool.com/math/library/analytic_geometry/p_line1/ зы если Супер король не может такую элементарную вещь найти в инете, то это ппц.... закрыть-бы ветку, да жалко, вроде люди хотели помоч.... |
|||
72
Супер король
27.02.15
✎
09:08
|
(71) эта ссылка у меня цветом как уже просмотренная. Там нет ответа на мой вопрос.
|
|||
73
Супер король
27.02.15
✎
09:11
|
можно приближенную формулу, адаптированную для компа.
|
|||
74
vde69
27.02.15
✎
09:12
|
чем формула d = (AMx + BMy + C)/sqrt(AA + BB) не подходит? наличием корня? или ты не знаешь как подставлять координаты?
|
|||
75
vde69
27.02.15
✎
09:13
|
d = (A Mx + B My + C)/sqrt(A A + B B)
|
|||
76
Супер король
27.02.15
✎
09:17
|
(74) от корня могу избавиться возведя все это в квадрат. Для сравнения квадрат тоже подойдет.
Но эта формула для прямой заданной уравнением, а не двумя точками. При выводе уравнения прямой добавятся куча других действий, что еще больше ее усложнит. А мне нужна очень простая формула, пусть даже с какой-то погрешностью но быстро рассчитываемая. Мне даже не нужно получить расстояние, а нужно узнать оно больше или меньше заданного числа. Я задал очень сложный вопрос, на который скорее всего нет простого ответа. Простые ответы типа http://ru.onlinemschool.com/math/library/analytic_geometry/p_line1/ не предлагайте, я их и сам находил. |
|||
77
Супер король
27.02.15
✎
09:22
|
Например sqrt(А^2 + B^2) можно упростить до А + В, такой точности вполне достаточно.
|
|||
78
vde69
27.02.15
✎
09:23
|
все просто...
наличие тупого угла указывает, что точка "за" границами отрезка отрезок АБ, точка В, если один из углов АБВ или БАВ более 90 градусов - точка - за разумеется считать нужно в радианах, там нет пи |
|||
79
Супер король
27.02.15
✎
09:25
|
(78) каких углов? Углы не известны
|
|||
80
vde69
27.02.15
✎
09:27
|
а вообще я когда этим занимался активно использова понятие "четверти"...
|
|||
81
Супер король
27.02.15
✎
09:28
|
сам угол рассчитывать тоже не нужно, достаточно узнать синус угла, и сравнивать с синусом угла погрешности.
|
|||
82
vde69
27.02.15
✎
09:29
|
(79) так посчитай...
уверяю ты не сможешь обойтись пятью знаками... берешь бумагу, ручку, на ней ставишь кучу точек и выводишь уравнения, потом их упращаеш... другой путь - использовать готовые библиотеки третьего не дано... |
|||
83
Супер король
27.02.15
✎
09:33
|
(82) кто знает. Вдруг уже кто-то вывел решение этой задачи.
Есть у алгоритма преимущество перед просто формулой - можно использовать условия, сравнения. Можно нарисовать окружность по точкам используя только сложение и сравнение |
|||
84
vde69
27.02.15
✎
09:34
|
||||
85
Супер король
27.02.15
✎
10:53
|
(84) хорошая ссылка. спасибо
|
|||
86
Супер король
27.02.15
✎
10:53
|
еще и в Красноярском крае. Вообще замечательно
|
|||
87
Супер король
27.02.15
✎
12:53
|
вот готовая формула:
( (ax-ox)*(by-oy)-(bx-ox)*(ay-oy) ) / sqrt( (ax-bx)*(ax-bx) + (ay-by)*ay-by) ) |
|||
88
Супер король
01.03.15
✎
16:18
|
Короче, другой алгоритм придумал:
1. Накапливаем сумму расстояний между точками, получаем пройденный путь. 2. Считаем расстояние между первой точкой и последней. 3. Сравниваем эти два результата. 4. Если они равны в пределах погрешности, значит пока линия можно считать что прямая. Погрешность может зависеть от длины отрезка, т.е. на коротких отрезках погрешность меньше, пропорциональна длине отрезка. 5. Если результаты сильно разные, завершаем старый отрезок и начинаем новый. Этот алгоритм лучше чем предыдущий тем что проще в понимании, а так же лишен недостатка когда пользователь рисует прямую линию и возвращается по той же прямой обратно. Что скажете? Какие недостатки могут быть? |
|||
89
vde69
01.03.15
✎
19:42
|
плохой алгоритм....
но объяснять не буду, сам думай... |
|||
90
sda553
01.03.15
✎
22:00
|
(0) Фактически в векторной графике храняться координаты точки, R(вектор), Направление V вектор, и кривизна A.
Модель очень подходит под физическое косочно-равноускоренное движение материальной точки. Или "лекало". Суть приближения состоит в том, чтобы превратить кривую в несколько переходящих друг в друга дуг окружностей. Для такого приближения, мы подставляем к исходной точке дугу окружности и увеличиваем радиус этой окружности пока 1. Отклонение от кривой, вычисленное методом наименьших квадратов на покрываемую длину кривой будет наименьшим, оставаясь при этом в рамках допустимого отклонения для этой степени сжатия. Таким образом алгоритм похож на действия человека, который подставляет к кривой лекало и двигает его, пытаясь получить максимальное приближение поверхности лекала к кривой на максимальный отрезок кривой, с некоторым, допустимым для данного человека, приближением |
|||
91
zulu_mix
01.03.15
✎
22:02
|
чето тут велик конструируют с квадратными колесами. правильнее будет собрать матрицу данных и сжать ее LZ
|
|||
92
Garykom
гуру
01.03.15
✎
22:33
|
(91) а я предлагаю нарисовать и сохранить в jpeg ... двуцветный сжатый jpg это никакой вектор не угонится за минимальностью ))
|
|||
93
zulu_mix
01.03.15
✎
22:35
|
(92) как вариант. кстати, в постановке задачи было только сжатие ведь? нигде не сказано что он должен правильно разжиматься?
|
|||
94
Супер король
02.03.15
✎
05:30
|
(90) метод наименьших квадратов плохо подходит, так как нужен быстрый метод, без пересчета всех точек при добавлении одной точки.
|
|||
95
Супер король
02.03.15
✎
05:33
|
(91) это сжатие без потерь. Не годится
|
|||
96
SeraFim
02.03.15
✎
05:36
|
(93)ахаха)
вспомнил - была какая-то олимпиада. Нужно было написать алгоритм сжатия данных. Причем написать как архиватор, так и разархиватор. В итоге победила команда, которая написала копирование данных) Ни одна из других команд не смогла разархивировать свой алгоритм))) |
|||
97
Супер король
02.03.15
✎
05:36
|
(92) сделал тест. Одна черная линия на белом фоне. 10 тысяч байт файл получился ! ! !
Вместо 18 байт векторной графики - 10 тысяч! Зачем давать глупые советы? |
|||
98
Супер король
02.03.15
✎
06:16
|
(89) не нашел в нем ничего плохого. Что не так?
|
|||
99
vde69
02.03.15
✎
09:59
|
(98) сколько будет векторов по твоей методе (один знак - один пиксель)
1. -------_-------- 2. ------__-------- |
|||
100
Супер король
02.03.15
✎
10:05
|
Не совсем понял рисунок, но похоже что по три вектора
|
|||
101
Супер король
02.03.15
✎
10:05
|
или один. Зависит от допустимой погрешности
|
|||
102
vde69
02.03.15
✎
10:10
|
там варианты есть: один, три, пять
|
|||
103
Rebelx
02.03.15
✎
10:12
|
ты пытаешься решить не совместимые задачи - просто, быстро, качественно и компактно.
выбери только два критерия, тогда задачу решить будет проще |
|||
104
vde69
02.03.15
✎
10:13
|
(103)+1000
|
|||
105
Супер король
02.03.15
✎
10:20
|
(102) Возможно. И что плохо в алгоритме?
|
|||
106
Супер король
02.03.15
✎
10:21
|
(103) чем не устраивает быстрое качественное и компактное решение (88) ?
|
|||
107
vde69
02.03.15
✎
10:35
|
(105) неоднозначность решения, а она у тебя есть в алгоритме, будут возникать пограничные ситуации...
(106) оно не качественое... |
|||
108
Rebelx
02.03.15
✎
11:15
|
(106) Проверь свой алгоритм на прямой из многих точек и змейки.
|
|||
109
Супер король
02.03.15
✎
11:16
|
(107) В чем неоднозначность? Увеличиваем погрешность, уменьшается количество векторов. Разве не так?
Чем не качественное? |
|||
110
Супер король
02.03.15
✎
11:16
|
(108) Проверил, работает.
|
|||
111
Rebelx
02.03.15
✎
11:19
|
(110) алгоритм (88) так как он описан не может представить прямую из точек и змейку как один отрезок.
|
|||
112
vde69
02.03.15
✎
11:28
|
(109) так называемая проблемма "бутылочного горлышка" или "впадин"
проблемма "дребезга" (одичная отстоящая точка) проблемма "пропуска" это когда из-за пропуска нескольких точек возникает неоднозначность.... ------------------------------- в идеале нужно задачу решать так 1. Упрощение растра (уменьшение точек, выделение контуров и т.д.) 2. построение сети триангуляции Делона 3. по граням сети определять искомую ломаную 4. замена части сегментов кривыми второго порядка но этот алгоритм очень трудоемкий, куда более реально это обдход по рпавилу левой/правой руки |
|||
113
Garykom
гуру
02.03.15
✎
12:44
|
(112) нафига ему растр то анализировать? как понял он рисует и на ходу хочет векторизовать
т.е. не просто точки, а они все последовательно выстроены по появлению в этом случае все проще и его алгоритм вполне имеет жизнеспособность (с некоторыми доработками) |
|||
114
Garykom
гуру
02.03.15
✎
12:45
|
(113)+ ТС а откат в твоей рисовалке будет? Т.е. как будешь алгоритмизировать если сначала нарисовали а потом стерли часть? И дальше рисуем
|
|||
115
Garykom
гуру
02.03.15
✎
12:57
|
||||
116
Супер король
02.03.15
✎
13:16
|
(111) Почему так думаешь? Наверное ты его не понял. Как ты понял? Давай разберемся.
|
|||
117
Супер король
02.03.15
✎
13:17
|
(112) Слишком сложно, не годится. У меня гораздо проще получилось.
|
|||
118
Супер король
02.03.15
✎
13:18
|
(114) Стереть можно только с конца, Ctrl+Z
|
|||
119
Garykom
гуру
02.03.15
✎
13:23
|
(118) я знал! ))
это ты не сразу считай/преобразовывай а сначала последовательно все точки(пары координат X,Y) в список (решается проблема тормозов и стирания посередине) и только по кнопке запускай алгоритм свой |
|||
120
Супер король
02.03.15
✎
18:18
|
(119) не. Усложнять так нет необходимости.
|
|||
121
Rebelx
02.03.15
✎
18:26
|
(116) как написано так и понял
пример VVVVVV ______ на глаз видно, что сумма длин отрезков существенно разная |
|||
122
Rebelx
02.03.15
✎
18:26
|
+(121) Смотреть в моноширинном шрифте
|
|||
123
Супер король
02.03.15
✎
18:59
|
(122) Конечно разная. В первом случае заметно длиннее.
|
|||
124
Супер король
02.03.15
✎
19:05
|
Понял что ты имел в виду. Короче, если погрешность позволяет, то змейка преобразуется в прямую линию. Если погрешность более строгая, то змейка останется змейкой.
|
|||
125
Супер король
02.03.15
✎
19:08
|
Погрешность при которой такая змейка как ты нарисовал станет прямой - очень огромная, на практике использоваться не будет. Будет задана погрешность в пределах 5%-10% я предполагаю, вполне достаточно чтобы сжать данные в 10-20 раз без заметного ухудшения внешнего вида.
|
|||
126
Torquader
02.03.15
✎
21:05
|
У нас точки - это участки траектории движения ?
Использование кривых второго порядка не позволяет сжать изображение - это только способ получить гладкую кривую. Как вариант, можно рассмотреть векторизацию результата нанесения краски на стену, когда каждая капля краски - это точка, но они имеют определённое распределение - а в итоге мы получаем достаточно ровную толстую линию. Поэтому, не стоит забывать, что у линии есть не только направление и кривизна, но и толщина - тогда ваша змейка превратиться в линию, если её шаги сравнимы с толщиной линии, если же больше, то ничего страшного. |
|||
127
Garykom
гуру
02.03.15
✎
22:24
|
(0) Кстати а какова задача (конечная цель) такого алгоритма? Т.е. для чего и зачем решаем траблу?
|
|||
128
mistеr
03.03.15
✎
05:27
|
Всю ветку не осилил, извините.
Методы аппроксимации давно и хорошо проработаны, в том числе и аппроксимации сплайнами. Берешь любой учебник по численным методам. Выбираешь, изучаешь, реализуешь. В чем собственно проблема? |
|||
129
Супер король
03.03.15
✎
06:21
|
(126) задача совсем другая.
(127) Нужно сократить объем данных записываемых в базу. Пользователь мышкой рисует простую картинку. Ее надо сохранить в колонку желательно не более 1024 байт. (128) Проблема в создании Алгоритма сжатия векторной графики с потерями, в (0) написано. |
|||
130
sda553
03.03.15
✎
07:13
|
(129) Векторная графика в общем случае не дает выигрыша в размере данных. Зачастую, даже наоборот. У нее другое предназначение.
|
|||
131
Garykom
гуру
03.03.15
✎
10:46
|
(129) а размеры картинки в пикселях известны заранее? или в каких пределах? Цветность?
Т.е. может проще будет свой формат растровый изобрести? Например в 1024 байт влазит монохромная картинка 90х90 пикселей. С вектором не решить проблему роста объема данных. Например когда пользователь очень много линий нарисовал допустим делал отрезки и наделал их 10 0000 штук... |
|||
132
vde69
03.03.15
✎
11:46
|
черепашья графика без сжатия влазит 2 маркерные точки на 1 байт, примерно 2000 закрашеных точек, это хватит?
|
|||
133
Супер король
04.03.15
✎
11:26
|
(130) в данном случае дает
(131) размер картинки больше чем 500х500 цветность безразлична. (132) возможно. Но чем меньше тем лучше, чтобы еще при передаче данных множества картинок уменьшить задержки. |
|||
134
Garykom
гуру
04.03.15
✎
17:01
|
(133) картинка монохром 500х500 растр это 32 кибайта
для векторов на каждую точку надо 4 байта, точнее слегка меньше 9+9 бит = 2,25 байта = 3 байта на точку на каждый вектор 6 байт, итого в 32 кибайта влезет чуть больше 10 000 векторов (отрезков) смысла? поле один фиг 500х500? т.е. в случае растра нет никаких ограничений на сложность рисунка в отличие от вектора |
|||
135
Супер король
05.03.15
✎
13:54
|
(134) смысл в том что в векторе занимает гораздо меньше.
Что за глупые вопросы? задача же понятно сформулирована. |
|||
136
vde69
05.03.15
✎
14:27
|
(135) векторизованая в отрезки КРИВАЯ занимает БОЛЬШЕ МЕСТА чем монохромный растр...
|
|||
137
Супер король
05.03.15
✎
17:15
|
(136) ну это же явно ложь. Я писал выше сколько занимает одна и та же картинка в векторе и в растре.
|
|||
138
Garykom
гуру
05.03.15
✎
19:43
|
(137) векторизованная кривая занимает места меньше растра только для простых и коротких кривых
|
|||
139
vde69
05.03.15
✎
20:04
|
(137) окружность с диаметром 6 точек... посчитай :)
|
|||
140
Супер король
06.03.15
✎
11:36
|
(139) посчитал. Растр в сотни раз больше места занял. И что?
|
|||
141
Garykom
гуру
06.03.15
✎
12:13
|
(140) плохо считал...6х6 точек растр это 12 бит = 2 байта
|
|||
142
Garykom
гуру
06.03.15
✎
12:14
|
(141) сорри ошибся 6х6 = 36 бит = 5 байт
|
|||
143
Супер король
14.03.15
✎
19:39
|
(141) Снова ты ошибся. Ты же сам в прошлый раз насчитал 32 кибайта: (134)
|
|||
144
Garykom
гуру
14.03.15
✎
19:44
|
(143) не понял?
в (134) для 500х500 написал что нужно для растра 32 КИЛОбайта (сча общепринятое сокращение КИбайт) в (141) неправильно сначала посчитал для растра 6х6, нужно 5 байт (просто байт без КИ или КИЛО) ЗЫ сколько нужно для одного вектора байт? как векторами и сколько их потребуется чтобы нарисовать окружность диаметром 6х6 ? |
|||
145
Супер король
14.03.15
✎
19:49
|
(144) на такую окружность около 10 векторов каждый по 2 байта плюс 3 байта накладных расходов на формат. итого 23 байта вектор против 32Кб растра. Вектор побеждает.
|
|||
146
Garykom
гуру
14.03.15
✎
20:10
|
(145) ммм...мне нравится ваш способ чтения...но
на растр 6х6 надо 5 байт, вообще то, против 23 байт вектор так? а если перейти к растру 500х500 и нарисованным окружностям от точки в центре с увеличивающимся радиусом +1 пиксель... нет желания посчитать сколько векторов потребуется? растр займет 32 кибайта ЗЫ учесть что 512 (координаты от 0 до 499) = 2^9, т.е. на один вектор (по две пары чисел для начала и для конца или начала вектора, угла и длины) нужно (9+9)+(9+9) = 36 бит = 4,5 байта |
|||
147
Garykom
гуру
14.03.15
✎
20:13
|
Ну и самое главное то забыли )) Растр замечательно сжимается (несжатый BMP 5мб ~ сжатому PNG 500кб)
|
|||
148
Garykom
гуру
14.03.15
✎
20:14
|
(147)+ а проверить как сжимается вектор? )) где будут почти случайные пары чисел
|
|||
149
Супер король
14.03.15
✎
20:58
|
(146) не понятно как у тебя поле 500х500 вдруг сжалось до 6х6, а окружность диаметром 6 превратилась в какую-то бесполезную фигуру.
Спорить нет смысла, я уже проверил опытным путем (97) что вектор занимает во много раз меньше чем jpeg который ты советовал в (92). А теперь вдруг про PNG заговорил. |
Форум | Правила | Описание | Объявления | Секции | Поиск | Книга знаний | Вики-миста |