Janojen risteäminen
Jani Tiainen
selville risteääkö kaksi janaa toisensa vai
ei. Janat ovat kaksiulotteisessa avaruudessa
(XY-tasossa). Siis riittää kun saadaan
selville risteääko janat vai ei, risteämis-
piste on toisarvoinen seikka.
Internet on asiasta hyvin niukka, ja omistakin
matematiikan opinnoista on jo tovi kulunut.
--
- ReDe
"Osaan asioita joita en ole vielä edes oppinutkaan!"
Jani Vuorinen
(x3,y3) ja (x4,y4) niin eikös se menisi näin:
int a = min(y1,y2)
int b = max(y1,y2)
int c = min(y3,y4)
int d = max(y3,y4)
if ((c>a && c<b) ||
(d>a && d<b))
{
// Risteää
}
Hmm... Noinkohan se nyt menee. Tosin ihan matemaattisesti toi ei
muistaakseni ollut mikään ihme juttu - siten saa helposti myös risteämis
koordinaatin. Kukapa muistaa miten se menikään?
Jani Tiainen wrote in message <8108h6$i...@cs.joensuu.fi>...
J{rvinen Hannu-Matti
Jani Vuorinen <jani.v...@nokia.com> wrote:
>Jos koordinaatit on ekalle janalla (x1,y1) ja (x2,y2) sekä toiselle janalle
>(x3,y3) ja (x4,y4) niin eikös se menisi näin:
>
>int a = min(y1,y2)
>int b = max(y1,y2)
>int c = min(y3,y4)
>int d = max(y3,y4)
>
>if ((c>a && c<b) ||
> (d>a && d<b))
>{
> // Risteää
>}
Eihän tuo ota mitenkään huomioon sitä, ovatko janat edes lähellä toisiaan
x-koordinaatin suunnassa. Lisäksi jos y-koordinaatti sattuu olemaan
sama, vertailu menee mönkään.
Kun kerran tunnet kaksi pistettä kummaltakin janalta, niin
laske ne suorat, joilta janat on katkaistu. Ratkaise sitten
suorien leikkauspiste, jonka jälkeen on jotakuinkin helppoa
päätellä se, onko ko. piste molempien janojen sisäpuolella.
--
Hannu-Matti Järvinen, h...@cs.tut.fi
Jani Tiainen
> Hmm... Noinkohan se nyt menee. Tosin ihan matemaattisesti toi ei
> muistaakseni ollut mikään ihme juttu - siten saa helposti myös risteämis
> koordinaatin. Kukapa muistaa miten se menikään?
Löysinkin jo ihan matemaattisemmat perusteet. Ensimmäiset hakusanat
olivat vain vähän väärät...
Että näin...
Jani Tiainen
> Jani Vuorinen (jani.v...@nokia.com) wrote:
> > Hmm... Noinkohan se nyt menee. Tosin ihan matemaattisesti toi ei
> > muistaakseni ollut mikään ihme juttu - siten saa helposti myös risteämis
> > koordinaatin. Kukapa muistaa miten se menikään?
>
> Löysinkin jo ihan matemaattisemmat perusteet. Ensimmäiset hakusanat
> olivat vain vähän väärät...
Otetaanpa sitten jatkoa, kun ei enää suju ollenkaan, eli nyt sitten
pitäisi saada järjestettyä laatikon yhdeltä sivulta lähtevät
janat sellaiseen järjestykseen, etteivät ne risteä keskenään.
Jaa, niin piirtelen suorakulmaista, ei planaarista kaaviota,
jos se nyt jotakuta kiinnostaa. Ei ihan niitä triviaalimpia
hommia.
Jani Vuorinen
>x-koordinaatin suunnassa.
Niin no joo.. siis sama homma x suunnassa tietysti.. tuon y suuntaisen ehdon
täytyttyä.
> Lisäksi jos y-koordinaatti sattuu olemaan
>sama, vertailu menee mönkään.
Totta.
Jani Tiainen
Osataanpas sitä olla sitten viksuja. Algoritmini pelitti sittenkin
juuri kuin se on suunniteltu. :)
Ongelmana onkin nyt, että on tapauksia joissa janat eivät risteä, mutta
kun sitten suorat taivutetaan suorakulmaisiksi, ne risteävätkin.
Millähän keinolla saisi jo tuossa vaiheessa missä niitä ei ole vielä
taivutettu tarkistettua sen, tulevatko ko. janat sitten suorakulmaisena
risteämään....
Vai pitääkö taivutuksen jälkeen tutkia erikseen kumpikin tuon
suorakulmaisen viivan segmentti.
Aki M Suihkonen
Jani Tiainen <jt...@cs.joensuu.fi> wrote:
>Nytpä iski paha nakki, pitäs nimittäin saada
>selville risteääkö kaksi janaa toisensa vai
>ei. Janat ovat kaksiulotteisessa avaruudessa
>(XY-tasossa). Siis riittää kun saadaan
>selville risteääko janat vai ei, risteämis-
>piste on toisarvoinen seikka.
>
Otetaan janat [ax i*ay] - [bx i*by] ja [cx i*cy]-[dx i*dy].
Rotatoidaan vektorit a-b ja c-d siten, että vuorotellen
jompi kumpi vektori on muotoa [0 0]-[x 0].
merkintä (x)^ tarkoittakoon x:n kompleksikonjugaattia, eli
[a + b*i]^ = [a - b*i]
c' = (c-a) * (b-a)^
d' = (d-a) * (b-a)^
// Nyt voidaan vertailla helposti, onko vektori c-d vektorin a-b
// 'ylä-', tai 'alapuolella':
if (Imag{c'} < 0 AND Imag(d') < 0) then return FALSE;
if (Imag(c') > 0 AND Imag(d') > 0) then return FALSE;
// jäljellä on vielä tapaus, jossa vektori c-d ylittää reaali-akselin, mutta
// ei välttämättä janaa a-b
a' = (a-c) * (d-c)^
b' = (b-c) * (d-c)^
if (Imag(a') < 0 AND Imag(b') < 0) then return FALSE;
if (Imag(a') > 0 AND Imag(b') > 0) then return FALSE;
return TRUE;
esim. Imag(c') =
Imag ((cx-ax) +i(cy-ay) * (bx-ax) - i(by-ay))
= (cy-ay)*(bx-ax)-(by-ay)*(cx-ax)
--
Problems 1) do NOT write a virus or a worm program
"A.K.Dewdney, The New Turing Omnibus; Chapter 60: Computer viruses"
Kimmo
>
> In article <pBPY3.79$kq1....@news2.nokia.com>,
> Jani Vuorinen <jani.v...@nokia.com> wrote:
> >Jos koordinaatit on ekalle janalla (x1,y1) ja (x2,y2) sekä toiselle janalle
> >(x3,y3) ja (x4,y4) niin eikös se menisi näin:
> >
> >int a = min(y1,y2)
> >int b = max(y1,y2)
> >int c = min(y3,y4)
> >int d = max(y3,y4)
> >
> >if ((c>a && c<b) ||
> > (d>a && d<b))
> >{
> > // Risteää
> >}
>
> sama, vertailu menee mönkään.
>
> laske ne suorat, joilta janat on katkaistu. Ratkaise sitten
> suorien leikkauspiste, jonka jälkeen on jotakuinkin helppoa
> päätellä se, onko ko. piste molempien janojen sisäpuolella.
> --
> Hannu-Matti Järvinen, h...@cs.tut.fi
Tarkistetaan vain kulmakertoimet, jos eroavat niin risteää.
eli onko
(x2-x1)/(y2-y1) != (x4-x3)/(y4-y3)
jos on niin risteää (muulla ei käsittääkseni ollut väliä)
J{rvinen Hannu-Matti
>J{rvinen Hannu-Matti wrote:
>> Kun kerran tunnet kaksi pistettä kummaltakin janalta, niin
>> laske ne suorat, joilta janat on katkaistu. Ratkaise sitten
>> suorien leikkauspiste, jonka jälkeen on jotakuinkin helppoa
>> päätellä se, onko ko. piste molempien janojen sisäpuolella.
>Tarkistetaan vain kulmakertoimet, jos eroavat niin risteää.
>
>eli onko
> (x2-x1)/(y2-y1) != (x4-x3)/(y4-y3)
>jos on niin risteää (muulla ei käsittääkseni ollut väliä)
Tuo toimii, jos kyseessä ovat suorat. Mutta kun kyseessä
ovat janat, ei leikkauspistettä välttämättä ole, vaikka
kulmakertoimet olisivat erisuuria. (Samoillakin kulmakertomilla
voi "risteämistä" tulla, jos kyseessä sattuu olemaan tismalleen
sama suora. Onko se sitten risteämistä vai yhteensulautumista,
riippuu tietenkin siitä, miksi se risteäminen ylipäätään oli
tärkeää tietää.)
--
Hannu-Matti Järvinen, h...@cs.tut.fi
Juho Cederström
Mikko Nuotio <mikko....@kolumbus.fi> wrote:
> on vain yksi tapaus jossa kaksi janaa _ei_ risteä eli jos ne ovat
s/jana/suora/g;
Suora on viiva, joka tulee äärettömyyksistä ja jatkuu äärettömyyksiin. Jana
on vaikkapa pisteet A ja B yhdistävä viiva.
--
Juho Cederström - cederstrom<a>kolumbus.fi s/<a>/@/
Seppo Mustonen
: Nytpä iski paha nakki, pitäs nimittäin saada
: selville risteääkö kaksi janaa toisensa vai
: ei. Janat ovat kaksiulotteisessa avaruudessa
: (XY-tasossa). Siis riittää kun saadaan
: selville risteääko janat vai ei, risteämis-
: piste on toisarvoinen seikka.
: Internet on asiasta hyvin niukka, ja omistakin
: matematiikan opinnoista on jo tovi kulunut.
: --
: - ReDe
: "Osaan asioita joita en ole vielä edes oppinutkaan!"
Tätä samaa ymmärtääkseni kysyttiin puolitoista vuotta sitten
tässä uutisryhmässä. Vastasin silloin seuraavasti:
Olkoon janojen päätepisteet seuraavat:
Jana 1: (X11,Y11) ja (X21,Y21)
Jana 2: (X12,Y12) ja (X22,Y22).
Sen suoran yhtälö, joka sisältää janan 1, voidaan kirjoittaa
parametrimuodossa
(1) X = X11 + t*(X21 - X11)
(2) Y = Y11 + t*(Y21 - Y11),
missä parametrin t vaihdellessa välillä (0,1) piste (X,Y)
"piirtää" janan 1.
Vastaavasti janaa 2 vastaavan suoran yhtälö on
(3) X = X12 + u*(X22 - X12)
(4) Y = Y12 + u*(Y22 - Y12),
missä nyt parametrin u vaihdellessa välillä (0,1) piirtyy jana 2.
Suorien leikkauspisteet saadaan silloin yhtälöistä
(1)=(3) ja (2)=(4)
eli syntyy lineaarinen yhtälöryhmä
X11 + t*(X21 - X11) = X12 + u*(X22 - X12)
Y11 + t*(Y21 - Y11) = Y12 + u*(Y22 - Y12)
joista ratkaistaan t ja u. Jos tässä ratkaisussa sekä 0<=t<=1
että 0<=u<=1, janat leikkaavat toisensa (tai niillä on
yhteinen piste).
SM