Pixel precision problem

Имам следната задача: дадена е отсечка в равнина. Единият й край винаги е в (0, 0), а другият е двойка параметри (a, b), като a>=b, освен това a и b са цели числа.
Задачата е (a, b) да се сменят с "коригираните" координати (a', b'), които удовлетворяват условията:
1. a' и b' са цели числа
2. a'/b' е цяло число
3. разстоянието от (a, b) до (a', b') е минимално измежду възможните по 1. и 2.

Разбира се ако a/b е цяло число нищо не се коригира.

Намерих програмно решение на задачата, но математическото ми убягва.
Благодаря.

a'/b' е цяло число

а' - е Х - координата
b' - е Y - координата

Не че мога да предложа кой знае какво като решение, но да уточня за себе си условието: покрай другото търсиш точки, за които котангенсът на ъгъла на радиус-вектора им спрямо ос Х е цяло число, нали? Или казано другояче, тангенсът на ъгъла на радиус вектора с ос Y e цяло число.

Значи имаме:
a'/b'=k (цяло число)
или
a'/b' = cos(alpha)/sin(alpha), където alpha е въпросният ъгъл между радиус-вектора и ос X

ако c=cos(alpha), то c/sqrt(1-c^2)=k
следва, че c=cos(alpha)=k/sqrt(1+k^2)
alpha=arccos(k/sqrt(1+k^2))

Трябва да използваме за стойност на k най-близките цели числа до реалното частно a/b

Задачата изглежда се свежда до това, да се намери най-близката точка с цели координати от най-близката права, сключваща ъгъл alpha с оста X.

Просто разсъждавам, ама и аз първо бих пробвала с програмно решение, за да схвана динамиката на нещата :-)

Сега, като се замисля, ъгълът алфа може да се изрази по-лесно така:
alpha = arctan(1/k)

Да, точно.

Решението не е единствено при даденото условие.
Примерно за дадена двойка (4,3)
отговорите (3,3); (4,2); (4,4) са
еднакво приемливи (на разстояние 1)

Като идея за решаване на задачата бих предприел следното:
Нека a/b дава частно k с някакъв остатък, деленето
без остатък означава че условието съвпада с решението.
Би трябвало да се проверят двойките:
(k*b , b); ((k+1)*b,b); (k*(b+1),b+1) ; ((k+1)*(b-1), b-1))
Ще се изненадам ако решението се окаже извън тези заподозрени.

Съкращавайте фразите до размера на мисъл. М.Вайсберг

Естествено че ще се окаже. Да вземем например т.(300,17)
к=300/17=17.64..., значи според теб трябва да се проверявар к=16, к=17
b'=17, 18, 16. Но очевидно най-близката точка е (300,15). Тук к=20. Много по-добра е и (300,20) Тук к=15. Могат да се намерят колкото си искаш примери, където и
|b'-b|>1 и |a'-a|>1. И не съм съгласен, че ъгловият коефициент е толкова важен. В общият случай се търси минимум на функцията
f(k,x)=(kx-a)^2+(x-b)^2, при условие на целочисленост на аргументите, което съвсем не е тривиална задача, ако въобще е решима.
По-нормален вариант е след намирането на една от тези точки, за които пишеш, да се "начертае" окръжност с център (a,b) и радиус разстоянието между двете точки и да се провери не попадат ли "подходящи" точки вътре в окръжността.

Понеже имам много работа напоследък, поизоставих тази задача.

Това, което си написал на привет е абсолютно вярно. Всъщност неговия подход беше първото, което ми дойде на ум и пробвах, но то не е решение. Грешката се вижда много добре, ако се подберат двойка a и b, които са големи и приблизително равни. Тогава решението е a'=b', като почти винаги a' и b' нямат изразяване с a, b, a-1, a+1, b-1, b+1.

Другото, което ми дойде на ум, но не съм го изследвал, е да се разложи a/b на безконечна дроб и да се изследват всички междинни "производни" дроби дали не удовлетворяват условието. Трудно ще се докаже единственост обаче, дори да се намери решение там.

А това, което е написала Атилеа, е съвсем смислена идея и ще я изследвам довечера. От условието за кратност на a' и b' може да се направи извода, че те лежат на правата y=k*x, където k е цяло. Могат да се насмятат рзстоянията от (a,b) до тези прави, а също така и разстоянията от (a,b) до целочислените координати на y=k*x. Задача, която на пръв поглед не ми изглежда сложна, но трябва да я проверя.

При фиксирано "к" функцията (kx-a)^2+(x-b)^2 има минимум при
x=(ka+b)/(k^2+1). И тъй като параболата е симетрична относително тази точка, то по-близкото цяло число до x е минимума (но при фиксирано к). Номера е да се сведе до минимум проверките на к. И тъй като оптималното к винаги е "около" a/b, може да се изчисли първо за тези к. И като имаме вече един "временен" минимум може да се построи окръжност с радиус този минимум и двете допирателни към тази окръжност (ъгловите коефициенти) ще ни дадат ограничението (ако има по-добра точка, то тя трябва да е вътре в окръжността).
Сигурно има и по-лесен начин, но това ми идва на акъла засега.

"И тъй като оптималното к винаги е "около" a/b, може да се изчисли първо за тези к."

тва не знам дали е съвсем точно... например при (a,b)=(10^n,6), (a',b')=(10^n,5). оптималното k=a'/b' може да е произволно далече от a/b

Разбира се. Но проверката все трябва да започне отнякъде. По-точно е да се каже "не лош резултат", макар и това да не е сигурно. Макар в твоя случай оптималното да е (10^n,5) ще намери не-лошото (10^n+2,6) и в този случай е много по добре проверката да се извършва по x. Радиус r=2, x от b-r до b+r.
А чрез допирателните ще даде твърде голям диапазон за проверка. От друга страна, ако окръжността е далеч от началото и с голям радиус, по добре е по к.

Ами да. При (1000,6) диапазон по к
к1=124.9985625
к2=250.00275
къде-къде по-добре по х. Но в повечето случаи по к е значително по-добре.
Напр (1876,333)
r=20.1 (по x проверка на 42 точки)
k1=5.302859893
k2=6.006900558
по к проверка само на 1 точка

Всъщност, добре е да се приложи следния алгоритъм:
След намиране на първата точка (или минимума отпървите няколко),
се изследват всички съседни целочислени коефициенти k, докато
разстоянието от (a,b) до правата x=y*k стане по-голямо от моментния
минимум, който пък се променя динамично.

Съкращавайте фразите до размера на мисъл. М.Вайсберг

Т.е проверка по к. Но има случаи, когато другата е по-добра. Мисля, че трябва след намиране на първият минимум и разстоянието му от точката да се оценят двата диапазона за проверка и да се избере този с по-малко целочислени точки. Проверка по к:
X=Round((ak+b)/(k^2+1)) в диапазон (k1;k2), където
k1= (T-t)/(1+T*t)
k2=(T+t)/(1-T*t)
T=a/b
t=r/l
r - радиус на окръжността, r=sqrt((a'-a)^2+(b'-b)^2)
l=sqrt(a^2+b^2)
Проверка по x:
K=Round(a/x) В диапазон
x1=b-r
x2=b+r

В който диапазон има по-малко целочислени точки, по него извършваме проверката.
При поява на нов минимум може всичко това да се преизчисли наново, ама чак пък толкова...

Но наистина трябва да се проверява от средата към краищата на диапаона, защото дори и при голям диапазон минимума е някъде там. И тогава преизчисляването има смисъл.

Тази задача ме отчая. Множествеността на решенията пречи на изследването чрез функционални уравнения и полиноми. Ако се начертае графика на възможните отговори се вижда много добре колко сложен е проблема.
Да вметна само 2 неща, които открих, докато ровех.
1) a/b не е ориентир за това, колко ще е k, дори при малки стойности. Пример (18, 4), 18/4 = 4.5, но най-доброто приближение е 18/3, което не е нито floor нито ceiling на 4.5.
2) Решенията могат да бъдат най-много 4. Пример: всяка двойка (3+4*k, 2) има четири решения. Обаче когато опитах да намеря рашение в полином от 4та степен се провалих.

Ето и как изглежда модифицираното програмно решение, което взе предвид дискусията по темата
1. Съставя се редица от най-малки радиуси на окръжности с център (a, b), при които имаме целочислени координати. Задачата е елементарна, въпреки привидната си трудност:
I. 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, ...
2. Към всяко число от редицата се добавят в масив и възможните целочислени координати:
II. (1, 0), (1, 1), (2, 0), (2, 1), (2, 2), (3, 0), (3, 1), (3, 2), (4, 0), (3, 3), ...
3. Оценка за това колко дълга да е редицата се прави като се вземе "най-лошия" сценарий на отдалеченост на точки (точката да е близо до правата y=1.5*x). Оценката е I(i) ~ a * 0.25. Тази оценка се задава в алгоритъма.
4. Започва проверка дали са решения стойностите (a + i, b+ j), (a + i, b - j), (a - i, b + j), (a - i, b - j), където i и j са двойка от II.
5. Първата двойка (i, j), която удовлетворява условието е решение на задачата. За да се установи единственост решението, след намирането му се проверяват и всички двойки от II, които са със същата дължина на радиуса, като него.

Имам следната задача: дадена е отсечка в равнина. Единият й край винаги е в (0, 0), а другият е двойка параметри (a, b), като a>=b, освен това a и b са цели числа.
Задачата е (a, b) да се сменят с "коригираните" координати (a', b'), които удовлетворяват условията:
1. a' и b' са цели числа
2. a'/b' е цяло число
3. разстоянието от (a, b) до (a', b') е минимално измежду възможните по 1. и 2.


Мен ме зачудва точка 2:
a'/b' е цяло число

Сигурен ли си? Не мога да си представя задача, при която това да има смисъл. Ти си знаеш де, но не може ли без тази точка?

Опитай да се върнеш стъпка назад, преди тази формулировка на задачата, и пак преразгледай ситуацията...

Смисълът е следния:
Имам 3D обекти, които трябва да се изчертаят в аксонометрична проекция (разстоянията не се смаляват с отдалечаване от точката на гледане). Тъй като ще се използват само два цвята, е нужно сметнатите точки да се коригират, за да се получат гладки прави линии. Това става като ъглите на всяка права се направят да са с котангенси цели числа.

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



При програмите за графична обработка като Photoshop, изправеността на линията се постига като се добавят нюанси на черното, което в случая не ми е достъпна възможност.

Aз не се сещам във Фотошоп да има опция за чертане на права линия (освен на хоризонтална и вертикална). Обаче ако ти знаеш такава опция, пусни си във Фотошоп режим Index (или отвори GIF файл, който е в режим Index), и я пробвай.

Този косур според мен не е кой знае какъв косур. Впрочем аз си бях написала преди 20тина години такава функция (за чертане на права линия с различни дебелини, но само с един цвят, в масив от точки), ползвах си я доста години после (програмата) и изобщо не ми е хрумнало, че не стои добре на екрана. Ако искаш, да я потърся да ти я покажа...

П.С. Погледнах как се държи програмата ми при различни наклони. Това, което забелязвам, е, че първият и последният фрагмент от начертаната линия са сравнително близки по дължина:

Това е voronoi диаграма на точките които са решенията на карта 1600*1600:

[линк]



Както се вижда близо до Х-а няма някаква закономерност.

Благодаря. Решението, поне на пръв поглед, е хаотично

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




NE SUTOR ULTRA CREPIDAM

Това съм го решил лесно. Имам граф на свързаности, където координати не участват. Корекциите също се правят по този граф. Изчертаването става като приключат корекциите. Засега не е имало проблеми, защото обектите са прости - призми, пирамиди и паралелепипеди.