ostatnio pracuje troche nad grafika wektorowa 2D
i mam pytanie jak rozwiazac problemy z dokladnoscia i zaokraglaniem

podstawowe problemy z jakimi sie spotykam:

- mamy dane 2 punkty p0(x,y), p1(x,y) powiedzmy p0 jest podany a p1
obliczony nalezy sprawdzic czy to ten sam punkt czy dwa lezace powiedzmy
blisko siebie, wiadomo gdy d(p0, p1) == 0 to ten sam punkt ale to tez wiem

- mamy dana prosta zadana dwoma punktami p1,p2 i punkt p0
sprawdzic czy punkt p0 lezy na prostej czy powiedzmy bardzo blisko tej
prostej

korzystam z api Java gdzie mozna dosc elegancko zaokraglac
na wiele sposobow w gore i wdol ale nawet proste obliczenia
powoduja bledy ktore trudno oszacowac

do góry

On Sat, 18 Jun 2011 20:30:34 +0100 Radoslaw Jocz
<r...@p...onet.pl> wrote:

> ostatnio pracuje troche nad grafika wektorowa 2D
> i mam pytanie jak rozwiazac problemy z dokladnoscia i zaokraglaniem
>
> podstawowe problemy z jakimi sie spotykam:
> [...]
>
> - mamy dane 2 punkty p0(x,y), p1(x,y) powiedzmy p0 jest podany a p1
> obliczony nalezy sprawdzic czy to ten sam punkt czy dwa lezace
> powiedzmy blisko siebie, wiadomo gdy d(p0, p1) == 0 to ten sam punkt
> ale to tez wiem
>
> - mamy dana prosta zadana dwoma punktami p1,p2 i punkt p0
> sprawdzic czy punkt p0 lezy na prostej czy powiedzmy bardzo blisko
> tej prostej

Jeśli pracujesz na typach zmiennoprzecinkowych, to musisz przyjąć
sobie jakąś granicę błędu, np. 1e-6, czy 1e-5. Czyli np.
d(p0, p1) <= 1e-6, to p0=p1.

w.

do góry

W dniu 2011-06-18 21:39, Wojciech Muła pisze:


> Jeśli pracujesz na typach zmiennoprzecinkowych, to musisz przyjąć
> sobie jakąś granicę błędu, np. 1e-6, czy 1e-5. Czyli np.
> d(p0, p1)<= 1e-6, to p0=p1.
>
W mierze względnej to ok, bo dosłownie czytając wygląda jakbyś pisał o
różnicy bezwględnej. Chyba że twoje 'd' to ma oznaczać, ale nie
spotkałem się z takim zapisem.

Jeśli bazą do pytania są szersze przemyślenia, to zagadnienia rachunku
błędów są od 100-200 lat podstawą kształcenia
inzynieryjsko-technicznego. Kiedy błąd bezwzględny, kiedy względny, jak
się dodają i wpływają na siebie itd. Który błąd jest 'z pomiaru' i co
się dzieje jak podlega obliczeniom. Ja to wyniosłem z metod numerycznych
(kiedyś miało to dużo większe znaczenia dla programistów), a z innym
rozkładem akcentów z miernictwa elektrycznego (do końca będę to sobie
cenił), dobre laboratorium z fizyki nie złe.

do góry

Jacek Czerwinski wrote:
> W dniu 2011-06-18 21:39, Wojciech Muła pisze:
>
>
>> Jeśli pracujesz na typach zmiennoprzecinkowych, to musisz przyjąć
>> sobie jakąś granicę błędu, np. 1e-6, czy 1e-5. Czyli np.
>> d(p0, p1)<= 1e-6, to p0=p1.
>>
> W mierze względnej to ok, bo dosłownie czytając wygląda jakbyś pisał o
> różnicy bezwględnej. Chyba że twoje 'd' to ma oznaczać, ale nie
> spotkałem się z takim zapisem.
>
> Jeśli bazą do pytania są szersze przemyślenia, to zagadnienia rachunku
> błędów są od 100-200 lat podstawą kształcenia
> inzynieryjsko-technicznego. Kiedy błąd bezwzględny, kiedy względny, jak
> się dodają i wpływają na siebie itd. Który błąd jest 'z pomiaru' i co
> się dzieje jak podlega obliczeniom. Ja to wyniosłem z metod numerycznych
> (kiedyś miało to dużo większe znaczenia dla programistów), a z innym
> rozkładem akcentów z miernictwa elektrycznego (do końca będę to sobie
> cenił), dobre laboratorium z fizyki nie złe.
>
>
wszystko wiem ale pracujac z debuggerem widze ze np
niektore funkcje z biblioteki standardowej double Math.xxxx() robia
wieksze bledy nize wynikalo by to z precyzji zmiennej double
wiec co wtedy?

do góry

W dniu 2011-06-18 22:01, Radoslaw Jocz pisze:

>>
> wszystko wiem ale pracujac z debuggerem widze ze np
Co do debuggera, nie wiem jak ten, ale debugger Borlanda w swej
juzerfriedlości zaokrągla liczby do "ładnych". Kiedyś pod ich wpływem
kolega szedł w zaparte, że są dokładne i można na nich liczyć kasę.
Prawda była inna, miały różnice na którejś pozycji ...

> niektore funkcje z biblioteki standardowej double Math.xxxx() robia
> wieksze bledy nize wynikalo by to z precyzji zmiennej double
> wiec co wtedy?

Oczywiście że będą mniej dokładne. Taki szkolny przykład: małe różnice
dużych licz będą mieć nawet fatalnie duży błąd. Nawet Intel z 10 lat
temu strzelił tragicznego byka w jakimś Pentiumie.

I "co wtedy" oto jest pytanie ... na pewno należy się do tego dostosować
a nie negować.

Np specjaliści z numeryki wiedzą, który algorytm na zdrowy rozsądek
poprawny, ale bardzo pechowo narastają mu błedy i wynajdują inny, mniej
oczywisty ale bardziej 'stabilny numerycznie'. To na poziomie "Pro".

Zasadniczo każde zagadnienie (jak porównanie punktu i prostej) ma dwa
warianty odpowiedz: idealistyczny (naiwny) a profesjonalny.

Strasznie dawno się tym zajmowałem, pamiętam ogół a nie szczegóły.

do góry

Wojciech Muła wrote:
> On Sat, 18 Jun 2011 20:30:34 +0100 Radoslaw Jocz
> <r...@p...onet.pl> wrote:
>
>> ostatnio pracuje troche nad grafika wektorowa 2D
>> i mam pytanie jak rozwiazac problemy z dokladnoscia i zaokraglaniem
>>
>> podstawowe problemy z jakimi sie spotykam:
>> [...]
>>
>> - mamy dane 2 punkty p0(x,y), p1(x,y) powiedzmy p0 jest podany a p1
>> obliczony nalezy sprawdzic czy to ten sam punkt czy dwa lezace
>> powiedzmy blisko siebie, wiadomo gdy d(p0, p1) == 0 to ten sam punkt
>> ale to tez wiem
>>
>> - mamy dana prosta zadana dwoma punktami p1,p2 i punkt p0
>> sprawdzic czy punkt p0 lezy na prostej czy powiedzmy bardzo blisko
>> tej prostej
>
> Jeśli pracujesz na typach zmiennoprzecinkowych, to musisz przyjąć
> sobie jakąś granicę błędu, np. 1e-6, czy 1e-5. Czyli np.
> d(p0, p1) <= 1e-6, to p0=p1.
>
> w.
>
robie dokladnie tak samo np walidujac punkt lezacy na na danym odcinku
lub okregu itp ale z mojej praktyki wynika ze granica bledu musi byc
conajmniej o kilka rzedow wielkosci wieksza niz dokladnosc samego typu
na ktorym sie liczy np double a wiadomo jak przyjme ten parametr zbyt
maly lub zbyt duzy to nic dobrego z tego nie bedzie

zastanawiam sie w jakim stopniu wielkosc takiego bledu moze zalezec od
danego jezyka i jego api
np porownujac Java i C i czy w ogole takie rozwazania maja sens

do góry

>
>> niektore funkcje z biblioteki standardowej double Math.xxxx() robia
>> wieksze bledy nize wynikalo by to z precyzji zmiennej double
>> wiec co wtedy?
>
> Oczywiście że będą mniej dokładne. Taki szkolny przykład: małe różnice
> dużych licz będą mieć nawet fatalnie duży błąd. Nawet Intel z 10 lat
> temu strzelił tragicznego byka w jakimś Pentiumie.
>
> I "co wtedy" oto jest pytanie ... na pewno należy się do tego dostosować
> a nie negować.
>
> Np specjaliści z numeryki wiedzą, który algorytm na zdrowy rozsądek
> poprawny, ale bardzo pechowo narastają mu błedy i wynajdują inny, mniej
> oczywisty ale bardziej 'stabilny numerycznie'. To na poziomie "Pro".
>
> Zasadniczo każde zagadnienie (jak porównanie punktu i prostej) ma dwa
> warianty odpowiedz: idealistyczny (naiwny) a profesjonalny.
>
> Strasznie dawno się tym zajmowałem, pamiętam ogół a nie szczegóły.
>
>
wiem narastanie bledow to podstawa met numerycznych ale nawet
"proste" rachunki nie sa tu oczywiste

do góry

W dniu 2011-06-18 22:17, Radoslaw Jocz pisze:
> Wojciech Muła wrote:
>> On Sat, 18 Jun 2011 20:30:34 +0100 Radoslaw Jocz
>> <r...@p...onet.pl> wrote:

>
> zastanawiam sie w jakim stopniu wielkosc takiego bledu moze zalezec od
> danego jezyka i jego api
> np porownujac Java i C i czy w ogole takie rozwazania maja sens

Zasadniczo API do zmiennego przecinka na dziś oparte jest na tych samych
podstawach, IEEE itd.

Co do egzystencjalnego słowa "sens" ... Okreslenie czy punkt jest na
prostej na "sens" na wykładzie abstrakcyjnej geometrii. Ktoś z was
widział prawdziwy 'punkt' albo 'prostą'? W realnym życiu to jest pytanie
czy jak wbiję gwożdzia w namalowaną linię (która nie jest ani
nieskończenie cienka, ani nieskończenie długa, ani nie jest prosta),
przejdzie kryteria odbioru. Tylko tyle i aż tyle.

Rozwiązujesz zagadnienie teoretyczne czy praktyczne?

do góry

spojrzcie na ten kod nie rozumiem zbytno po co ktos
robil takie sztuczki z przesunieciami bitowymi << 14 >> 14

typedef struct point {
int x;
int y;
} point;

typedef struct line {
point p1;
point p2;
} line;

/*
* check_lines:
* This is based off an explanation and expanded math presented by Paul
Bourke:
*
* It takes two lines as inputs and returns 1 if they intersect, 0 if
they do
* not. hitp returns the point where the two lines intersected.
*
* This function expects integer value inputs and stores an integer value
* in hitp if the two lines interesect. The internal calculations are
fixed
* point with a 14 bit fractional precision for processors without floating
* point units.
*/
int check_lines(line *line1, line *line2, point *hitp)
{
/* Introduction:
* This code is based on the solution of these two input equations:
* Pa = P1 + ua (P2-P1)
* Pb = P3 + ub (P4-P3)
*
* Where line one is composed of points P1 and P2 and line two is
composed
* of points P3 and P4.
*
* ua/b is the fractional value you can multiple the x and y legs
of the
* triangle formed by each line to find a point on the line.
*
* The two equations can be expanded to their x/y components:
* Pa.x = p1.x + ua(p2.x - p1.x)
* Pa.y = p1.y + ua(p2.y - p1.y)
*
* Pb.x = p3.x + ub(p4.x - p3.x)
* Pb.y = p3.y + ub(p4.y - p3.y)
*
* When Pa.x == Pb.x and Pa.y == Pb.y the lines intersect so you
can come
* up with two equations (one for x and one for y):
*
* p1.x + ua(p2.x - p1.x) = p3.x + ub(p4.x - p3.x)
* p1.y + ua(p2.y - p1.y) = p3.y + ub(p4.y - p3.y)
*
* ua and ub can then be individually solved for. This results in the
* equations used in the following code.
*/

/* Denominator for ua and ub are the same so store this calculation */
int d = (line2->p2.y - line2->p1.y)*(line1->p2.x-line1->p1.x) -
(line2->p2.x - line2->p1.x)*(line1->p2.y-line1->p1.y);

/* n_a and n_b are calculated as seperate values for readability */
int n_a = (line2->p2.x - line2->p1.x)*(line1->p1.y-line2->p1.y) -
(line2->p2.y - line2->p1.y)*(line1->p1.x-line2->p1.x);

int n_b = (line1->p2.x - line1->p1.x)*(line1->p1.y - line2->p1.y) -
(line1->p2.y - line1->p1.y)*(line1->p1.x - line2->p1.x);

/* Make sure there is not a division by zero - this also indicates that
* the lines are parallel.
*
* If n_a and n_b were both equal to zero the lines would be on top
of each
* other (coincidental). This check is not done because it is not
* necessary for this implementation (the parallel check accounts
for this).
*/
if(d == 0)
return 0;

/* Calculate the intermediate fractional point that the lines
potentially
* intersect.
*/
int ua = (n_a << 14)/d;
int ub = (n_b << 14)/d;

/* The fractional point will be between 0 and 1 inclusive if the lines
* intersect. If the fractional calculation is larger than 1 or
smaller
* than 0 the lines would need to be longer to intersect.
*/
if(ua >=0 && ua <= (1<<14) && ub >= 0 && ub <= (1<<14))
{
hitp->x = line1->p1.x + ((ua * (line1->p2.x - line1->p1.x))>>14);
hitp->y = line1->p1.y + ((ua * (line1->p2.y - line1->p1.y))>>14);
return 1;
}
return 0;
}

do góry

>
> Rozwiązujesz zagadnienie teoretyczne czy praktyczne?

obecnie juz tylko praktycznie,
przyklad w gwozdziem to bardzo trafne
hehe

do góry