Průsečík dvou úseček

28.3.2009 22:40 | Přečteno: 12578× | Jiné | poslední úprava: 29.3.2009 13:49

Dělal jsem úkol z programování, ale nějak špatně to funguje.

Mám 2 úsečky, každá je zadaná dvěma body. Mám zjistit jestli jsou rovnoběžné, různoběžné, kolmé, jestli leží na jedné přímce a v tomto případě jestli se nepřekrývají. Pokud mají průsečík, vypsat ho.

Vyřešil jsem to nějak takto:

• Z bodů zjistím k a q pro rovnici přímky y = kx + q
• Porovnám káčka, pokud jsou stejné, budou rovnoběžné nebo ležet na stejné přímce. Pak porovnám qéčka a jestli jsou stejné, leží na jedné přímce. Pak zjistím, jestli jeden z krajních bodů 2. úsečky leží na 1. úsečce, popř. jeden z krajních bodů 1. úsečky na 2. úsečce (zde stačí otestovat jen jeden bod).
• Pokud jsou káčka jiná, jsou různoběžné. Kolmost otestuji vzorečkem k1 * k2 + 1 == 0. Pak najdu průsečík přímek (k1*x + q1 = k2*x + q2, potom dopočtu y) a zjistím, jestli bod leží na obouch úsečkách.

A právě ve zjišťování, zda je bod na úsečce je zakopaný pes. Zjišťuji to takto:

• Zjistím délku úsečky sqrt((A.x - B.x)^2 + (A.y - B.y)^2)
• Zjistím vzdálenost bodu od obouch bodů úsečky sqrt((A.x - bod.x)^2 + (A.y - bod.y)^2) + sqrt((B.x - bod.x)^2 + (B.y - bod.y)^2)
• Výsledky porovnám

Problém ale je, že např. při hodnotách AB = {{0,0}, {2,2}} a CD = {{0,2},{3,-3}} dostanu, že bod na úsečce neleží, protože
2.82842712474619029094924371747765690088270947265625 není to samé jako
2.82842712474918984686003386741504073143005371093750

Tak co teď s tím? Jak jinak zjistit, jestli tam ten bod leží nebo ne?

Update

Dá se tohle ještě zkrátit?
       

Komentáře

[Sleep_Walker]

A[xa,ya], B[xb,yb], usecka AB lezi na primce s rovnici y=ax+b

lezi bod X[xx,yx] na usecce AB?

aby lezel na usecce, musi splnovat 2 podminky:

a) lezet na prislusne primce - overis, zda plati rovnost po dosazeni souradnic do y=ax+b

b) X lezi "mezi" A a B - otestujes, zda min(xa,xb) < xx < max(xa,xb) && min(ya,yb) < yy < max(ya,yb)

pokud splnuje obe podminky, lezi na usecce. Timto se vyhnes velkym cislum.

Ber to jako odpoved na otazku. Zbytek nekomentuji :)

[Jardík]

Super, a teď je problém zase jinde a sice ve směrnici, kterou to nevypočítá přesně a tak nedostanu rovnost pro rovnici přímky Neporadí někdo, jak to všechno udělat bez toho nepřesného dělení? Nebo nějakou rychlou třídu "zlomek"

[Let_Me_Be]

Neni nic jako nepresne deleni. Problem je v reprezentaci realnych cisel v pocitaci.

Je docela smutne, ze misto zrejme odpovedi se zde objevuji naprosto nesmyslne rady.

V zadnem programu by se nemelo za zadnych okolnosti objevit porovnavani hodnot typu float/double/long double na (ne)rovnost. To je cely problem.

[Vin]

Tak neděl, ale násob - test rovnosti ("rovnici") k_AB == k_CD můžeš vyjádřit jako (y_B - y_A)/(x_B - x_A) == (y_D - y_C)/(x_D - x_C), což je ekvivalentní (y_B - y_A)*(x_D - x_C)  == (y_D - y_C)*(x_B - x_A) (což je ekvivalentní nulovému skalárnímu součinu normály prvního vektoru a druhého vektoru, jak jsem poznamenal v odpovědi Platonixovi)

Ovšem, také záleží, co máš na vstupu.

[Jardík]

Na vstupu mám 2 body pro každou úsečku.

Tak jsem to upravil, většinu dělení převedl na násobení. Už to projde s {{0,0},{2,2}},{{0,2},{3,-3}}, ale zase mi to neprojde testem na progtestu s hodnotami {{4,7},{12,8}},{{5,11},{40,-300}}, protože to nepřesně počítá x-ovou a y-ovou souřadnici průsečíku, protože tam se mi dělelní nepodařilo zbavit.

[Josef Kufner]

Nejde o dělení ani o násobení. Jde o reprezentaci čísla jako takového. 0,1 prostě nemá v binární soustavě ukončený desetiný rozvoj a spousta dalších čísel také ne.

Výpočty s plovoucí desetinou čárkou se dělají tak, že omezíš počet operací při kterých vznikají největší chyby nebo je přepíšeš tak, aby chyba byla co nejmenší (sčítat/odčítat srovnatelně veliká čísla, násobit/dělit co nejméně a pokud možno už nepočítat s výsledky násobení či dělení, aby se chyby nesčítaly).

Porovnávání uďeláš odečtením a porovnáš zda je absolutní hodnota výsledku menší než požadovaná tolerance. Tedy místo A == B uděláš abs(A - B) < epsilon, kde epsilon je např. 1E-10.

[Let_Me_Be]

Vzdej to, on je proste blbej. Uz to mu to sem napsalo nekolik lidi.

[deda.jabko]

spatne zvladnuta analyza...

vybral sis blbou reprezentaci usecky pro dany jazyk... takze doporucuji vymenit jednu vec z toho...

bud zustanes u jazyka a pouzijes lepsi reprezentaci, ktera netrpi tak vyraznymi neduhy...

nebo pouzijes nejaky normalni jazyk, ktery zvlada pocitani s racionalnimi cisly a muzes zustat u parametrickeho vyjadreni primky.

[Jardík]

Co je to analýza?

[Josef Kufner]

Rozbor zadání a případně i zevrubný návrh klíčových komponent a datových typů. (V tomto kontextu.)

[Sleep_Walker]

Uf, mas recht, tohle mi nedoslo. Mel bych si odpoved vice rozmyslet.

[hikikomori82]

const DELTA = 0.000001 - definovana presnost

if abs(k1-k2) < DELTA then ... k1 a k2 su v ramci danej presnosti rovnake

[AHAHA]

Neni to sice idealni reseni, ale rozhodne nejjednodussi a v realnych aplikacich je to asi uplne jedno.

Jen je potreba zvolit vhodny odstup delty a presnosti reprezentace realneho cisla v zavislosti na poctu operaci, aby chyba nikdy nepresahla velikost delty.

[peterh]

Toto je standardne riesenie ktore sa uci aj na numerickej matematike, proste sa treba zmierit s konecnou presnoustou cisel s poh. rad. ciarkou. Ked to chces presne tak to rataj symbolicky cez zlomky..

[Platonix]

Nebylo by jednodušší napočítat směrové vektory obou úseček (to pomocí rozdílu souřadnicí jejich bodů). Potom stačí provést skalární součin těchto vektorů. Je-li roven nule, jsou kolmé, je-li roven 1 jsou rovnoběžné. Je-li něco mezi, tak jsou obecně různoběžné.

[Vin]

 

je-li roven 1 jsou rovnoběžné.

Co třeba (1,1) a (-1,-1)? Ne, tohle by se testovalo přes normálový vektor - pokud je normálový vektor prvního vektoru kolmý na druhý vektor (tedy skalární součin druhého vektoru a normály prvního je roven nule). Normálový vektor (a,b) = (-b,a)

 

Ale jinak dobrý - už jsem chtěl v předešlém vlákně odpovědět, jak řešit situaci se zlomky - tohle je o poznání elegantnější.

[Vin]

I když - je to vlastně to samý, co jsem chtěl navrhnout, jenom jinak vyjádřený.

[Platonix]

Není třeba testovat přes normálový vektor. Skačí, když malinko opravím ten svůj návrh: bude se počítat absolutní hodnota skalárního součinu. Jo jinak je samozřejmě třeba vektory normovat!

Tedy celý vzoreček by byl asi takovýto:

1. najdu směrové vektory pomocí rozdílu souřadnic obou bodů

2. spočítám výraz: (skalární součin 1 a 2 vektoru)^2/((skalární součin 1 a 1 vektoru)^2*(skalární součin 2 a 2 vektoru)^2)

3. je-li výsledek 1 - rovnoběžné, 0 - kolmé, něco mezi jsou obecně různoběžné svírají úhel = acos(sqrt(výsledek))

[Vin]

No, ale těm operacím bych se radši vyhnul - narůstá časová složitost a dochází k nepřesnostem (normála je levná).

[Platonix]

Nevím, co je na normále tak super. Samozřejmě musíš ty vědět, jaké funkce má ten program poskytovat. Já navrhuji řešení, které je robustní (neselže při vyšším počtu rozměrů) a je naprosto standardní (opírá se o definice skalárního součinu a příslušné věty). Alternativně můžeš na 0 testovat skalární součin obou vektorů a zároveň jednoho vektoru a normálového k druhému. Přijde mi to ale zbytečné, když se vše dá ošetřit jedním vzorečkem.

[droid]

Časová složitost je stejná.

[Platonix]

Jo a nedoporučuji normálový vektor používat protože pro více dimenzí je problém s jeho definicí (je nejednoznačný). Např.: Jaký bude normálový vektor k vektoru (1,1,1). Je to totiž celá normálová rovina.

[Vin]

To ale není tenhle případ.

[default]

Ty vole! Tyhle problémy bych chtěl mít!

[rastos]

Náhodou s týmto problémom sa potýkam pomerne často (v jednom nemenovanom CAD systéme). Predstav si, že potrebuješ spraviť union alebo prienik dvoch polygónov, z ktorých každý môže mať stovky až tisícku hrán. A prípadne tých polygónov môže byť stovka a potrebuješ bleskovo vedieť či sa niektoré z nich prekrývajú alebo nie. Bleskovo znamená - v obsluhe eventu na pohyb myši. Ľudia, ktorí tieto problémy majú a dokážu ich riešiť, sú celkom dobre platení.

[David Jaša]

Což díky moorovu zákonu a neoptimalizovanosti "běžných" programů vede k paradoxním situacím, kdy i tyto šílenosti proběhnou rychleji, než vykreslení tabulky v OpenOffice...

[Jardík]

Mně už to nepřemejšlí, jde tohle nějak zkrátit?

    (By - Ay)(CyDx - CxDy) - (Dy - Cy)(AyBx - AxBy)
y = ---------------------------------------------
        (By - Ay)(Dx - Cx) - (Dy - Cy)(Bx - Ax)

[Saljack]

Tak nastav řád, při kterém už je to zanedbatelné.

[Jardík]

Příloha:

• main.cpp (4005 bytů)

Tak jsem to nějak spatlal dohromaci, dělení jsem omezil jak jen to šlo. S ukázkovými hodnotami, co jsou na progtestu mi to projde, ale přesto mi progtest dal jen 3.6 ze 4, že prý tam byla 90.91 úspěšnost při "Extenzivní test náhodnými vstupy". Můžete na to někdo kouknout, co tam mám špatně? Prosím ...

[Jardík]

To mě teda poserte, udělal jsem to znovu se směrnicema, napsal jsem si třídu "zlome", jelikož jsou na vstupu jen celá čísla, a ten šmejd mi pořád nechce dát 4b a ještě mi hlásí, že to neprošlo kompilátorem s parametrem -pedantic, přitom u mě to s ním projde, všechno určitě funguje, jak má. To musej mít nějaký rozbitý.

[Jardík]

Příloha:

• main.cpp (5517 bytů)

Tady to je

[Jardík]

zlome = zlomek

[morph]

 Nevim proc presne to neproslo tobe, ale v tom modu -pedantic si to zkus nejdriv zkompilovat na progtestu v sekci prekladace. Muze ti to na tvym systemu hazet jiny warningy nez u nich a uz to neprojde..

[David Jaša]

Z bodů zjistím k a q pro rovnici přímky y = kx + q

Tímto tvarem rovnice nejsi schopen popsat přímky rovnoběžné s osou y - ty chyby by mohly být pokusy počítače o dělení různých čísel nulou (ale nejsem programátor, takže netuším, jestli je to správný výklad). Blbuvzdorný tvar rovnice přímky v rovině je:  ax + by +c = 0 , kde "a" a "b" jsou pořadnice normálového vektoru k úsečce a c je konstanta, která se dopočítá dosazením souřadnic bodu ležícího na přímce za "x" a "y".

Ve tří- a vícerozměrném prostoru ti pak nezbyde, než přímky vyjadřovat parametrickými rovnicemi {x}T = {a}T + {b}Tt , kde vektor "x" jsou souřadnice libovolného bodu na přímce, vektor "a" souřadnice známého bodu ležícího na přímce, vektor "b" souřadnice směrového vektoru přímky a "t" je parametr.

[David Jaša]

PS: překvapuje mě páni programátoři, že jste si tohoto háku v návrhu algoritmu ještě nevšimli...

[CEST]

Hehe, prošel jsem dizkuzi až sem, abych taky zjistil, že až tebe trklo a nikoho před tebou, že ta rovnice je rovnice funkce a ne rovnice přímky (úsečky) v rovině. Jinak řešení je opravdu použít porovnání rozdílu abs A a B vůči nějaké konstantě určující přesnost.

[Jardík]

A no jo ... stane se, už je pozdě něco měnit, termín byl 23:59

[CEST]

Tak to myslim nebudes mit dobre, staci, aby ucitel zadal jednu usecku jako A[5,1], B[5,3] a jsi v riti, protoze dojde k deleni nulou (k je nekonecno).

[M. Lox]

A IMHO se přítomnost bodu na úsečce dá zjistit jednoduše:
Úsečka je A[a,b], B[c,d], bod C[e,f]. Bod, který leží na „její“ přímce leží i na úsečce, pokud platí: když je a<c, tak musí být a<e<c; když je a>c, tak a>e>c; když a=c, tak se testuje to samé s b, f a d (protože je rovnoběžná s y).
Nebo ne?

[David Jaša]

jo

ale aby to mělo smysl, je potřeba napřed určit rovnoběžnost a shodnost - to ručně ještě před výpočtem průsečíku, pokud dotyčný programovací neumí korektně vyjádřit matematické konstrukce 0x = 0 (úsečky leží na jedné přímce, je potřeba spočítat překryv) a 0x != 0 (úsečky leží na dvou různých rovnoběžných přímkách).

[Jardík]

Tak jsem to spatlal s ax + by + c = 0, na progtest to už ale odeslat nemůžu. Ještě zítra na přednášce zkusím ukecat lektora, jestli by to ještě nevzal (cviko máme až ve čt), ale nejspíš ne.

Takto jsem řešil:

vektorový součin = 0 -> rovnoběžné/na společné přímce
  c1 == c2 -> na společné přímce
    A, B na CD nebo C na AB -> překrývají se
    jinak ne
  jinak rovnoběžné
skalární součin směrových vektorů = 0 -> kolmé
jinak různoběžné
ze soustavy průsečík (jako "zlomek", abych mohl přesně zjišťovat, jestli leží na úsečce)
průsečík na AB a CD -> průsečík úseček

Hlavní je, že to funguje, jenom by to asi příště chtělo pořádnou analýzu, což nemám rád

[David Jaša]

Hlavní je, že to funguje, jenom by to asi příště chtělo pořádnou analýzu, což nemám rád

Hm, tak v tomhle se informatika od stavařiny moc neliší. Když se člověk vybodne na pořádnou analýzu, tak potom vycházejí v lepším případě nesmysly a v horším správně se tvářící úplně špatné výsledky...