Térben elhelyezkedő poligonon áthaladó szakasz metszése
2013-03-18T18:44:22+01:00
2013-03-26T16:29:42+01:00
2022-08-07T14:35:31+02:00
hegdavid96
Üdv!

Most kezdtem el ismerkedni az analitikus geometriával ezért még a wikipédiás dolgokon túl nem igazán mentem.( nem is nagyon hiszem hogy tudnék már néhány helyen az is magas nekem de kezdem megmeg érteni) Hozzá teszem 10. osztályos vagyok. Szóval a kérdésem az lenne, hogy adott a térben egy poligon. A poligon pontjai egy síkon helyezkednek el. A síktól függetlenül adott egy pontpár ami egy szakaszt alkot. Szóval a kérdésem az lenne hogy hogyan lehetne meghatározni hogy a szakasz metszi e a poligont vagy nem?

Egy másik hasonló kérdésből amikor hasonló kérdés volt csak annyi könnyebbséggel hogy pligon helyett sík és szakasz helyett egyenes volt. Azt megértettem. Csak tovább lépni nem tudok.

Egy másik talán egyszerűbb kérdésem hogy van-e esetleg kifejezetten az analitikus geometriával foglalkozó könyv vagy dokumentum esetleg amit ajánlani tudnátok.
Mutasd a teljes hozzászólást!
Leírtam egy vázlatos pszeudokódot. A nehezebb kérdések itt még nem szerepelnek, de nézzed meg, hogy idáig érthető és használható-e?

Az általad is említett számábrázolási pontatlanságokból eredő veszélyek nem teljesen, de legnagyobbrészr kiküszöbölhetők, ha a gyakran szükséges (x==y) összehasonlításokat egy közelítő egyenlőséget eldöntő (equ(x,y)) függvénnyel helyettesítjük. Az érzékenység az eps(ilon) beálításval adható meg.

eps=0.00001 //érzékenység equ(x,y) { return ((x-y<eps)and(y-x<eps)? true:false); } // közelítő egyenlőség vizsgálata // 2-odrendű determináns | a b | det(a,b,c,d) {return a*d-b*c} | c d | //poligon első három pontja P1(p1x,p1y,p1z) P2(p2x,p2y,p2z) P3(p3x,p3y,p3z) // a*x+b*y+c*z+d=0 a poligon síkjának egyenlete, (a,b,c) a sík normálvektora // a (P1->P2)×(P1->P3) vektoriális szorzat (cross product) használatával a = det(p2y-p1y,p3y-p1y,p2z-p1z,p3z-p1z) b = -det(p2x-p1x,p3x-p1x,p2z-p1z,p3z-p1z) c = det(p2x-p1x,p3x-p1x,p2y-p1y,p3y-p1y) d = -a*p1x-b*p1y-c*p1z //az adott szakasz végpontjai: Q1(q1x,q1y,q1z) Q2(q2x,q2y,q2z) //a sík és szakasz közös pontját meghatározó egyenlet: //(a*(q2x-q1x)+b*(q2y-q1y)+c*(q2z-q1z))*t = -a*p1x-b*p1y-c*p1z-d left = a*(q2x-q1x)+b*(q2y-q1y)+c*(q2z-q1z) right= -a*p1x-b*p1y-c*p1z-d if(equ(left,0)) // t kiesik az egyenletből { if(equ(right,0)) // a szakasz benne van a síkban else // nincs közös pont, mert párhuzamosak } else { t = right/left if((t<0)or(1<t)) // a szakasz nem metszi a síkot (csak a meghosszabbítása) else // a szakasz metszi a sikot { mx= q1x+(qx2-qx1)*t // metszéspont koordimátái, M(my,my,mz) my= q1y+(qy2-qy1)*t mz= q1z+(qz2-qz1)*t //itt jön az M helyzetének felderítése } }

A metszéspont helyzetének meghatározásához könnyen áttérhetünk 2D-re, azáltal, hogy az (x,y,z) pontok helyett (x,y,0)-t veszünk, azaz a síkot z-vel párhuzamosan levetítjűk az xy síkra. Ha az elhelyezkedés miatt ez nem járható út, akkor a másik két alapsík valamelyikére való vetítés biztosan használható.


Mi legyen, ha a szakasz benne van a síkban? Ekkor is kérdés a közös pont?
Mutasd a teljes hozzászólást!

  • első blikkre:

    "
    Egy másik hasonló kérdésből amikor hasonló kérdés volt csak annyi könnyebbséggel hogy pligon helyett sík és szakasz helyett egyenes volt. Azt megértettem. Csak tovább lépni nem tudok.
    "

    ha abban az esetben a döféspontot meg tudtad határozni, akkor csak annyi a dolgod, hogy eldöntsd az a szakaszon ill. a poligonon "belül" van-e,
    Mutasd a teljes hozzászólást!
  • igen még ez is eszembe jutott, csakhogy azt nem tudom hogy hogy tudnám megállapítani hogy a pont a szakaszon belül van e az egyenesen vagy kívül, illetve, hogy hogyan kezeljem a poligont, elvégre ez egy külön sík egy külön 2D-s koordináta rendszer saját origóval. Jelöljek ki a síkon egy origót? és konvertáljam át a pontokat az újonnan kapott koordináta rendszerbe? Nagyon több ötletem nincs.
    Mutasd a teljes hozzászólást!
  • Mutasd a teljes hozzászólást!
  • Köszönöm az olvasnivalót :D Pontosan ilyen műre van szükségem. Ma még csak beleolvastam de holnap teljesen el fogom olvasni.
    Mutasd a teljes hozzászólást!
  • Voltak már hasonló témák pl., pl..


    Ha már megvolna a szakasz és a sík döféspontja, akkor még nem olyan könnyű megmondani, hogy az a sokszögön belül van-e?
    Például az alábbi sokszögnél szabad szemmel sem nyilvánvaló, hogy hol vagyunk bent és hol kínt.

    x-------------------------------------x | x-------------------------------x | | | x-------------------------x | | | | | | | | | | x----------------------x | | | | | | | | | | x-------------------------x | | | | x----------------------------x | | | | x-------------------------x | | | | | | | | | | | x------------------x | | | | | | | x---------x x-x | | | | | | | x--x | | | | | | | | | | | | | x---x | | | | | | | | | | x--x | | | x--x | | | | | | | | | x---x | x--x | | | | | | | x---------x | | | | | | | x------------------x | | | | | x--------------------------x | | | x-------------------------------x x--x

    Egyéb szempont: előfordulhat, hogy a szakasz teljesen benne van a síkban.

    ------------------------------------------------------------------------
    Hogyan dönthető el, hogy egy P pont kívül, vagy belül van?

    1)
    Vegyünk egy biztosan kinti Q pontot.
    Pl., a poligon csúcspontjai
    x koordinátái legnagyobbikánál nagyobb x-et és
    y koordinátái legnagyobbikánál nagyobb y-t véve kapott Q pont biztosan kívül van.

    2)
    Keressük meg a poligon összes oldalszakaszának (tehát nem oldalegyenesének)
    a PQ szakasszal való metszéspontját - ha van.

    3)
    Páros metszéspont esetén P külső,
    páratlan metszéspont esetén P belső pont.

    Legalábbis általában így van, de ha a PQ szakasz a poligon egy - vagy több - csúcspontján is átmegy, vagy
    valamely oldalával közös szakasza is van, akkor hasra estünk.
    Ilyenkor másik Q pont keresendő.
    Mutasd a teljes hozzászólást!
  • nézzük csak a szakaszt:

    adott két (különböző) pontod, ezek egyértelműen meghatároznak egy szakaszt a térben, és adott egy harmadik pont, amelyről tudod, hogy az előbbi kettő egyenesén van, és azt szeretnéd tudni, hogy valójában a szakaszon belül van-e, vagy nem?

    mivel rajta van a harmadik pontod az egyenesen, ezért azt nem kell ellenőrizned, hogy kielégíti-e a kettő által meghatározott egyenes egyenletét,

    tfh. a két pontod p1 = (x1, y1, z1), p2 = (x2, y2, z2), a harmadik p = (x, y, z),

    ha nem 3 dimenzióban gondolkodsz, hanem mondjuk 1-ben (mert egy dimenziós lenne a tered), akkor egyből adódik a megoldás (önkényesen vettem az x-et):
    ((x1 <= x és x <= x2) vagy (x2 <= x és x <= x1))
    2 dimenzióra hasonlóan:
    ((x1 <= x és x <= x2) vagy (x2 <= x és x <= x1)) és
    ((y1 <= y és y <= y2) vagy (y2 <= y és y <= y1))
    3-ra ezek szerint:
    ((x1 <= x és x <= x2) vagy (x2 <= x és x <= x1)) és
    ((y1 <= y és y <= y2) vagy (y2 <= y és y <= y1)) és
    ((z1 <= z és z <= z2) vagy (z2 <= z és z <= z1)) és

    persze gondolkodhatsz az egyenes mentén is, azaz, ha adott a két pontod p1, p2 (p1 != p2), akkor az p1*t + p2*(1-t) megadja az egyenesük összes pontját t-től függően (t tetszőleges valós szám),
    ha 0 <= t <= 1, akkor a két pont szakaszán belül vagyunk,
    azaz, ha van egy harmadik pontod, akkor ahhoz meghatározva a t-t, egyszerűen eldöntheted, hogy a szakaszon belül vagy-e (azaz azt vizsgálva, hogy a [0, 1] intervallumban van-e a t, vagy nem) (persze, ha utánagondolsz, vagy elkezded felírni, hogy a t-t vajon hogyan lehet meghatározni és nem akarsz majd osztani (mert az osztás "drága", meg "pontatlan is lehet"), és ezért azt gondolod, hogy csak az számít, hogy a t a [0, 1]-hez képest hogyan viszonyul, akkor a végén szerintem ugyanarra jutsz, mint fentebb, azaz ahhoz, hogy az adott koordinátákat kell egymáshoz képest vizsgálnod),

    a poligon már nehezebb kérdés,

    lehet, hogy akkor jársz a legjobban, ha felbontod háromszögekre, mert ekkor "visszavezetted" arra, hogy az így kapott háromszögek közül van-e olyan, amelyiken belül van-e a döféspont,

    aztán lehet, hogy én gondolom rosszul, meg az is lehet, hogy rosszul fejeztem ki magam és másoknak teljesen érthetetlen a gondolatmenetem,
    Mutasd a teljes hozzászólást!
  • szbzs.2:
    Tehát olyan program alkotandó, mely előállítja egy tetszőleges - pl. a fenti - poligont háromszögekre bontó átlókat. Amíg a kérdező nem zárja ki a konkáv sokszögeket, addig arra is számítani kell, hogy néhány átló részben, vagy teljesen kívül van.
    Egy pont belső/külső helyzetének eldöntését előbb (cs++ ... 2013.03.18. 23:29) vázoltam.


    hegdavid96
    Szakasz és sík metszéspontja.

    A szakasz végpontjai: P(x1,y1,z1) és Q(x2,y2,z2), a paraméteres egyenletrendszer:
    x = x1 + (x2-x1)*t y = y1 + (y2-y1)*t z = z1 + (z2-z1)*t (0<=t<=1)
    A sík egyenlete:
    a*x + b*y + c*z + d = 0
    .
    A közös pont(ok) kereséséhez a szakasz egyenleteit behelyettesítjük a sík egyenletébe:
    a*(x1 + (x2-x1)*t) + b*(y1 + (y2-y1)*t) + c*(z1 + (z2-z1)*t) + d = 0
    A kapott egyismeretlenes egyenletet megoldjuk:
    1) Egy megoldás:
    a PQ egyenes egy pontban metszi(döfi) a síkot,
    ha 0<t<1, akkor a szakasz egy belső pontja van a síkban,
    ha t=0 vagy t=1, akkor pedig P vagy Q.

    2) Nincs megoldás:
    a PQ egyenes párhuzamos a síkkal:

    3) Végtelen sok megoldás:
    az egész PQ egyenes benne van a síkban.
    Mutasd a teljes hozzászólást!
  • csak arra akartam utalni, hogy esetleg jobban jár, ha "transzformálja" a feladatot,

    nyilván a felbontás sem olyan egyszerű (bár biztos van olyan, akinek igen),

    nemcsak a konkáv sokszögekkel nem kézenfekvő a felbontás, hanem akkor sem, ha mondjuk van egy egyenesre eső három szomszédos csúcs, hiszen azok nem alkotnak "valódi" háromszöget, az is igaz, hogy jelen esetben ez nem biztos, hogy gond lenne, hiszen csak azért "daraboljuk" a poligont, hogy egyszerűbben számolhassunk (annak eldöntése, hogy egy adott pont egy háromszögön belül van viszonylag könnyebben meghatározható, szerintem már volt ilyen téma itt a prog.hu-n, lehet, hogy pont te adtál rá megoldást),

    egyébként lehet, hogy abba az irányba is lehetne gondolkodni, amit a "scanline poligon kitöltő" algoritmusnál "használunk", de ha jól értelmezem, akkor ez lényegében ugyanaz, amit leírtál: a metszéspontok párosságának vizsgálata,

    a hozzászólásod végén írtad "
    Ilyenkor másik Q pont keresendő.
    ", amiből nekem az derült ki, hogy a javasolt módszered azért nem annyira "egyértelmű", hiszen semmit nem írtál arról, hogy mi alapján válasszuk az új pontot, azaz előfordulhat, hogy megint "hasra estünk" (nyilván valamilyen stratégiát követve az 1) javaslatod alapján, pld. az egyik koordinátáját lépésenként növelve, egyszer csak jó pontot kell elméletileg választanunk, de...)
    Mutasd a teljes hozzászólást!
  • ... semmit nem írtál arról, hogy mi alapján válasszuk az új pontot
    Dehogynem írtam, - ld. 1) - de csak azért, mert annyira egyszerű.
    Nem is a Q pont a lényeg, hanem egy P-ből induló félegyenes kell.

    A hasraesés nem vészes, mert nagyon kicsi az esélye. A lehetséges félegyenesek (ill. Q pontok) között nagyságrendekkel kevesebb a szerencsétlen helyzetűek száma.
    Ez is lehetne valószínűségszámítási feladat, egy lottó 5-ösnek is nagyobb esélye van, mint annak, hogy harmadszori találgatással is használhatatlant választunk.
    Mutasd a teljes hozzászólást!
  • igen, arról írtál, hogyan válasszuk a Q pontot (kezdetben), csak én úgy értelmezem az általad később írtakat, hogy úgy választva is "hasra eshetünk", "
    Ilyenkor másik Q pont keresendő.
    ",
    én erről a másikról regélek, azért is írtam utána, hogy nyilván mondhatom azt, hogy mondjuk
    ++q.x;
    és ekkor már kisebb a valószínűsége, hogy megint hasra esünk, vagy ha igen, akkor mehetünk "még jobbra" és mivel a poligonunk véges pontból áll, ezért nyilván egyszer biztos vége lesz a hasra esésnek,

    én egy algoritmusnál nem szeretem az ilyen "bizonytalanságokat", csak ezért "kötekedtem",
    Mutasd a teljes hozzászólást!
  • ... mehetünk "még jobbra" ... nyilván egyszer biztos vége lesz a hasra esésnek ...

    Biztos vége lesz?

    Ezeknél - ráadásul az egyik konvex - akármennyi ++q.x után is használhatatlan lesz a Q, az idők végezetéig hasalni fogunk.
    x x-------x x-----x / \ | | | \ / \ | P | | \ Q / \ | x x---x x x / \ | | / P \ Q | | x * x x | | | | | | | | | | x-----------x x--------------------x
    Bizonyos helyzetekben érdemes megbarátkozni a véletlennel.
    (És a valószínűségszámítással.)
    Mutasd a teljes hozzászólást!
  • Köszönöm az eddigi válaszokat azonban két problémám lenne. Amit eddig leírtatok azt tökéletesen megértettem így azt hogy hogyan határozzuk meg hogy egy egyenesen lévő pont egy adott pontpár vagyis szakaszban van e vagy nincs azt maximálisan értem. És azt is hogy hogyan határozhatjuk meg hogy egy pont a poligonban van vagy nincs. Viszont rájöttem hogy ami korábban érthetőnek tűnt az mégsem annyira világos a számomra. Még sosem volt dolgom ilyenekkel, például mi az a t? értem hogy [0,1] intervallumból kell megadni de honnét tudjuk hogy a 0 és 1 közt lévő végtelensok számból mennyit is kéne megadni t-nek? És programozási nyelvben hogyan kéne értelmeznem az egyenlet megoldását. Ott nem olyan mint papíron mikor megoldja az ember, ott van egy műveletsor és egy végeredmény ez nem tiszta még nekem.
    Mutasd a teljes hozzászólást!
  • Egy példa.
    P( 3; 7;-3) Q( 9; 5; 5)

    Az egyenes (egyik) irányvektora: P->Q( 6;-2; 8), a paraméteres egyenletrendszer két változatban:
    x = 3 + 6*t x = 3*(1-t) + 9*t y = 7 - 2*t y = 7*(1-t) + 5*t z = -3 + 8*t z = -3*(1-t) + 5*t
    Ha t helyébe behelyettesítenénk az összes valós számot, akkor megkapnánk az egyenes összes pontját.
    Pl.
    t=0 ---> P( 3; 7;-3)
    t=1 ---> Q( 9; 5; 5)
    t=1/2 ---> ( 6; 6; 1) a szakasz felezőpontja.
    Ha 0<=t<=1, akkor a PQ szakasz pontjait,
    ha t<0 akkor P-ből a Q-val ellenkező irányba induló félegyenes,
    ha 1<t akkor Q-ből a P-vel ellenkező irányba induló félegyenes pontjait kapjuk.
    Legszemléletesebb, ha a t-t az időnek feleltetjük meg (ld."time") és behelyettesítéskor azt kapjuk meg, hogy egy mozgó pont hol van a térben abban a pillanatban.

    A feladatnál nincs mit behelyettesíteni, ott az egyenes egy pontját keressük, az egyenletből kapunk egy t értéket, mellyel meghatározható a pont.
    Ha 0<=t<=1, akkor a pont a szakaszon belül van (pl. Ha t=0.5, akkor a felezőpont, ha t=0.75, akkor a Q-hoz közelebbi negyedelő pont, stb.)

    A fenti
    a*(x1 + (x2-x1)*t) + b*(y1 + (y2-y1)*t) + c*(z1 + (z2-z1)*t) + d = 0
    egyenlet nagyon egyszerű lesz, hiszen csak a t ismeretlen, a többi betű helyére a megadott számok kerülnek és rendezés után ilyesmit kapunk: 3*t=7.
    Mutasd a teljes hozzászólást!
  • Köszönöm mostmár világosabb. A sík egyenletével még gondjaim vannak. Utánna olvastam, de ott teljesen máshogy vannak ezek leírva és nemigazán tudom megérteni.
    Amit írtál:

    a*x + b*y+ c*z+ d = 0

    Az a,b,c a síkot meghatározó normál vektor.
    Az x,y,z a az egyenes egyik irányvektora.
    de mi a "d"?

    A másik de az gondolom úgy van ahogy gondolom, ha megvan a t, akkor csak a behelyettesítésre használt egyenlettel transzformáljuk a P illetve Q pontot Lamda = t vel és gyakorlatilag megkapjuk a szakasz illetve a sík döféspontját.
    Innentől jön még egy dolog, ugyebár hogy meg kell határozni hogy
    ez a pont a poligon belsejébenv agy a külsejében van. Viszont az általatok leírt megoldások arra az esetre vonatkoznak hogy a poligon egy dimenziós síkon van és a síkon helyezkedik el az origó is. Gondolom célszerű lenne transzformálni a pozíciókat ha van döféspont a síkon, a meghatározott síkra. Erre esetleg valami módszert tudnátok javasolni?
    Mutasd a teljes hozzászólást!
  • köszönöm, de most egy kicsit összezavartál, nem egészen értem az ellenpéldáidat, mivel anno ezt javasoltad:
    "
    1)
    Vegyünk egy biztosan kinti Q pontot.
    Pl., a poligon csúcspontjai
    x koordinátái legnagyobbikánál nagyobb x-et és
    y koordinátái legnagyobbikánál nagyobb y-t véve kapott Q pont biztosan kívül van.
    "

    én egy ily módon megválasztott kiinduló Q pontra gondolom, hogy lesz a (q.x, y), (q.x+1, y), (q.x+2, y), ... sorozatnak olyan eleme, amelyre nem fog "elhasalni", mivel a leírásod szerint
    "
    Legalábbis általában így van, de ha a PQ szakasz a poligon egy - vagy több - csúcspontján is átmegy, vagy
    valamely oldalával közös szakasza is van, akkor hasra estünk.
    ",
    és mivel véges pontból áll a poligonunk, ezért a PQ csak akkor lehet gond, ha a P valamelyik csúcsban van, ellenben a P-n és a poligon bármely csúcsán átmenő egyenesek száma véges, legfeljebb annyi, amennyi csúcsa van a poligonnak, nem? (továbbá egy tetszőleges P = (p.x, p.y) pontra, a Qi = (q.x + i, q.y), Qj =(q.x + j, q.y) (i != j) csak akkor lehet egy egyenesen, ha a P a Qi, Qj egyenesén van, az pedig a fenti választás miatt (q.y nagyobb mint a poligon bármely csúcspontjának y koordinátája) biztosan nem metszi a poligont, nem?, azaz ekkor a P biztosan kívül kell essen),

    azzal persze egyetértek, hogy nem nem biztos, hogy "jó" egyesével léptetni, talán szerencsésebb a poligon kiterjedését (befoglaló téglalapját, mert a poligon síkjában vagyunk gondolom én) valamilyen mértékben figyelembe venni, stb.
    Mutasd a teljes hozzászólást!
  • Azt hogy hogyan lehet meghatározni, hogy a pont a poligonon belül illetve kívül található szerintem ebben a pdf fájlban nagyon jól leírják azokra a problémákra is kitérve amiket leírtatok:

    http://cgip.inf.unideb.hu/zichar/GIS/GIS_9Alg.pdf
    Mutasd a teljes hozzászólást!
  • A sík (u.n. implicit) egyenletében (a,b,c) valóban a(z egyik) normálvektor, de a d-nek nincs ennyire szemléletes tartalma. (Az origól való távolsághoz van némi köze, de most érdektelen, legfeljebb azt jó tudni, hogy az origót tartalmazó síkoknál d=0)

    Képzeljük el, hogy az összes lehetséges (x;y;z) számhármast behelyettesítjük az egyenletbe és amelyekre igaz az egyenlőség azokat megjelöljük valahogyan, végül a megjelölt pontokból épp az a sík rajzolódik ki.
    Pl. a 3x-4y+5z-6=0 egyenletű síknak pontja a (2;5;4), vagy a (10;1;-4) stb., mert 0-t adnak.
    Ennél több is tudható: a síkot kivéve a tér két részre oszlik, az egyik féltér pontjai pozitív, a másiké negatív értékeket adnak a behelyettesítésre.

    u.i.
    A 3x-4y+5z-6=0 síkot így is szokás írni:
    3x-4y+5z=6
    Mutasd a teljes hozzászólást!
  • Van néhány alapvető vektorgeometriai technika, amit nem elég megérteni, hanem rutinszerűen kell alkalmazni és bármilyen nyelven gyakorlati programokat írni rájuk.

    Néhány példa a legeslegelemibbek közül:
    - két egyenes metszéspontja;
    - egyenesek (párhuzamosak, vagy kitérőek) távolsága;
    - pont távolsága egyenestől;
    - pont tükrözése egyenesre;
    - pont vetítése egyenesre;
    - három ponttal megharározott sík egyenlete;
    - pont és egyenes által meghatározott sík egyenlete;
    - pont távolsága síktól;
    - pont tükrözése síkra;
    - sík tükrözése pontra;
    - pont vetítése síkra;
    - egyenes és sík döféspontja
    - egyenes és sík hajlásszöge;
    - síkok hajlásszöge;
    - metsző síkok közös egyenesének egyenlete;
    - terület és felszín;
    stb. stb. stb. stb. stb. stb.

    A mutatott jegyzet nem rossz, de már sok minden - pl. az itt felsoroltak - ismeretét feltételezi.

    A pont poligonhoz viszonyított helyzetével (kint/bent) is foglakozik. A "megoldás elve" a 7.oldalon olvasható. Az "elv" rendben volna, de vannak olyan helyzetek, amikor a vázolt eljárás elakad. Erről bőven szó volt már ebben a topikban: (cs++ ... 2013.03.18. 23:29) és (cs++ ... 2013.03.19. 13:59). A nehézségektől eltekintve két szakasz (tehát nem egyenes, hanem szakasz) metszéspontjának meghatározása sűrűn kell majd.


    Leírhatnád pontosabban mi is a feladat?
    Hogyan van megadva a poligon?
    Mutasd a teljes hozzászólást!
  • A fenti ábrákon y-ra nem, hanem csak az x koordinátára érvényesítettem a saját magam szabta feltételt. Aki még nem gondolta volna végig, az ott láthatja milyen bonyodalmak léphetnek fel.

    Előzőleg sajnos nem írtad, hogy a Q pontnak épp az általam javasolt megválasztására gondoltál. Ekkor csakugyan - rosszabb esetben is - a ++q.x alkalmazásával előbb-utóbb használható Q-t kapunk. Ebben tényleg igazad van, egyúttal az eredeti javaslatom célszerűségét is igazoltad.

    Pár mondatod nem teljesen világos, majd - napkelte után - megpróbálom értelmezni.
    Mutasd a teljes hozzászólást!
  • "
    Előzőleg sajnos nem írtad, hogy a Q pontnak épp az általam javasolt megválasztására gondoltál.
    "

    bocsánat, azt hittem, hogy ez egyértelmű volt (szbzs 2013.03.19. 12:26 > "
    nyilván valamilyen stratégiát követve az 1) javaslatod alapján, pld. az egyik koordinátáját lépésenként növelve, egyszer csak jó pontot kell elméletileg választanunk, de...
    ")
    Mutasd a teljes hozzászólást!
  • A feladat az lenne hogy írjunk egy függvényt, ami eldönti az alábbi bemenő adatokból:
    SzakaszA pontja,
    SzakaszB pontja,
    PoligonA pontja,
    PoligonB pontja,
    PoligonC pontja,
    ...
    PoligonN-edik pontja;
    hogy a Szakasz metszi-e a poligont, mind ez 3D-s térben, 3D-s koordináta rendszerben. a poligon pontjai pedig mindenféleképpen egy síkban vannak, viszont a szakasz nagy valószínűséggel nincs egy síkban a poligonnal, de nem kizárt. A pontok 3D-ben vannak megadva. Nagyvonalakban kezdem megérteni ezt az egészet nézzétek el nekem kérlek, hogy ennyire analfabéta vagyok, olyan dolgot szeretnék megérteni, amihez még messze nincs meg az iskolai végzettségem.
    Mutasd a teljes hozzászólást!
  • Eddig nem akartam firtatni, hogy mit is nevezel poligonnak, mert több értelemben is szokás használni a kifejezést.

    Fogadjuk el, hogy a pontok egy síkban vannak (koplanárisak) és ezt nem kell, bár lehetne ellenőrizni. Persze háromdimenziósként kezelendők, de nem ez a baj.

    Ha - egy síkban - megadunk néhány pontot és azokat egymás után szakaszokkal összekötjük, végül az utolsót az elsővel, akkor egy zárt töröttvonalat kapunk. A gond, hogy a sorrend nagyon nem mindegy, mert nagy esélye van annak, hogy a töröttvonal átmetszi saját magát. Ilyenkor mit jelent a "belül" és a "kívül"?

    Ha adott bármennyi koplanáris pont, akkor - általában - összeköthetők egymás után, hogy önmetszés nélkül, egy - konvex, vagy konkáv - síkidomot zárjanak körül. Ha van n db pontunk, de nincs semmi további információnk, akkor ezeket (n-1)! féleképpen lehet zárt töröttvonallá összekötni, többségük önmetsző lesz. Ezek közül megtalálni valamelyik nem önmetszőt nehezebb feladat, mellette eltörpülnek a fentebb emlegetett koordinátageometriai kérdések.

    Ezért volna célszerű minél pontosabban megírnod a tényleges feladatot.
    Mutasd a teljes hozzászólást!
  • Bocsánat ezt tényleg nem említettem. A koordináták sorrendben vannak. Viszont eszembe jutott még egy probléma. Ugyebár a számábrázolási pontatlanságok miatt valószínűleg nemigazán lesznek tökéletesen egy síkban ezek a pontokk sosem, ezért valószínűleg úgy lenne a legjobb, ha a poligon első 3 pontját vennénk alapul a sík megadásához, a többi pont pedig lényegébena síkon van de valóságban apontatlanságok miatt nem, ezért a további pontoknak pedig a síkra vett merőleges vetületét lenne szerintem célszerű venni.
    Mutasd a teljes hozzászólást!
  • Leírtam egy vázlatos pszeudokódot. A nehezebb kérdések itt még nem szerepelnek, de nézzed meg, hogy idáig érthető és használható-e?

    Az általad is említett számábrázolási pontatlanságokból eredő veszélyek nem teljesen, de legnagyobbrészr kiküszöbölhetők, ha a gyakran szükséges (x==y) összehasonlításokat egy közelítő egyenlőséget eldöntő (equ(x,y)) függvénnyel helyettesítjük. Az érzékenység az eps(ilon) beálításval adható meg.

    eps=0.00001 //érzékenység equ(x,y) { return ((x-y<eps)and(y-x<eps)? true:false); } // közelítő egyenlőség vizsgálata // 2-odrendű determináns | a b | det(a,b,c,d) {return a*d-b*c} | c d | //poligon első három pontja P1(p1x,p1y,p1z) P2(p2x,p2y,p2z) P3(p3x,p3y,p3z) // a*x+b*y+c*z+d=0 a poligon síkjának egyenlete, (a,b,c) a sík normálvektora // a (P1->P2)×(P1->P3) vektoriális szorzat (cross product) használatával a = det(p2y-p1y,p3y-p1y,p2z-p1z,p3z-p1z) b = -det(p2x-p1x,p3x-p1x,p2z-p1z,p3z-p1z) c = det(p2x-p1x,p3x-p1x,p2y-p1y,p3y-p1y) d = -a*p1x-b*p1y-c*p1z //az adott szakasz végpontjai: Q1(q1x,q1y,q1z) Q2(q2x,q2y,q2z) //a sík és szakasz közös pontját meghatározó egyenlet: //(a*(q2x-q1x)+b*(q2y-q1y)+c*(q2z-q1z))*t = -a*p1x-b*p1y-c*p1z-d left = a*(q2x-q1x)+b*(q2y-q1y)+c*(q2z-q1z) right= -a*p1x-b*p1y-c*p1z-d if(equ(left,0)) // t kiesik az egyenletből { if(equ(right,0)) // a szakasz benne van a síkban else // nincs közös pont, mert párhuzamosak } else { t = right/left if((t<0)or(1<t)) // a szakasz nem metszi a síkot (csak a meghosszabbítása) else // a szakasz metszi a sikot { mx= q1x+(qx2-qx1)*t // metszéspont koordimátái, M(my,my,mz) my= q1y+(qy2-qy1)*t mz= q1z+(qz2-qz1)*t //itt jön az M helyzetének felderítése } }

    A metszéspont helyzetének meghatározásához könnyen áttérhetünk 2D-re, azáltal, hogy az (x,y,z) pontok helyett (x,y,0)-t veszünk, azaz a síkot z-vel párhuzamosan levetítjűk az xy síkra. Ha az elhelyezkedés miatt ez nem járható út, akkor a másik két alapsík valamelyikére való vetítés biztosan használható.


    Mi legyen, ha a szakasz benne van a síkban? Ekkor is kérdés a közös pont?
    Mutasd a teljes hozzászólást!
  • "
    ha a poligon első 3 pontját vennénk alapul a sík megadásához
    "

    ha "matematikai" (geometriai) szempontból közelítünk, akkor elméletileg jól gondolhatod, de...

    honnan tudod, hogy az első 3 pont valóban megad egy síkot, azaz a 3 pont háromszöget alkot, és esetleg nem egy egyenesen van?

    mondhatod erre, hogy nem szokás egy egyenest egy csúccsal "megtörni", de a "gyakorlatban" meg pont, hogy az ilyen esetek szoktak problémákat okozni,

    azaz nem tudunk arról semmit, hogy a poligonod hogyan jött létre, és ez "fontos" lehet,

    elsősorban arra gondolok, hogy én évekig felhasználói szinten foglalkoztam (professzionális) 2D/3D-s programokkal és rengetegszer belefutottam abba, hogy a nem matematikai, hanem a "szabad hozzáállás" milyen galibát okozhat, sokszor én is elsőre tanácstalan voltam, hogy mi lehet a gond, mert esetleg ismertem a "szükséges módszer" hátterét is, és nem értettem, hogy a programozóknak miért okozott nehézséget egy ismert, "csontig lerágott" algoritmus implementálása, aztán beugrott, hogy ...

    egy egyszerű példa: tfh. a feladatod az előbbi és csinálsz egy GUI-t hozzá, ahol a "felhasználó" tesztelheti az implementációdat, azaz megadhatja a sík és a szakasz pontjait, egyszer van az, ahogyan te is említetted, nem biztos, hogy a sík megadott pontjai tényleg egzaktul egy síkot adnak, erre persze használhatod a cs++ által javasolt módszert: valamilyen epszilon eltérést megengedsz, megpróbálod azt kordában tartani, de mint írta a pontatlanságok csak legnagyobbrészt kiküszöbölhetők,

    de (itt jön az én példám): szerintem meg sem kötheted a felhasználó kezét, hogy ne adjon meg egymás után 3 (vagy több) olyan csúcsot, amely 1 egyenesen van,
    erre mondhatod: miért nem köthetem meg a kezét? egyszerű a megoldás: ellenőrzöm, hogy az adott csúcs megadásánál az az előbbi kettővel egy egyenesen van, és ha igen, akkor ...?
    mit csinálsz akkor? nem engeded "lerakni" a csúcsot? ez nem jó megoldás szerintem, mert ez nagyon idegesítő működés lehet, a felhasználó nem fogja érteni, mert nem látja, hogy egy egyenesen van (vagy nem akarja elfogadni, hogy ezt nem lehet, miért, nem tudja ezt kezelni a program? ennyire béna?) és nem fogja érteni, hogy miért nem tudja "lerakni" a pontot,
    erre persze jön az újabb ötlet: kiírunk valamilyen figyelmeztetést, ez szerintem talán csak akkor "elfogadható", ha az tényleg látható, "feltűnő", de nem veszi el a "fókuszt" (a "fókuszon" most az egér aktuális pozícióját értem, amire koncentrál a felhasználó), emiatt meg szerintem megoldhatatlan, vagy nagyon sokat kell rajta gondolkodni, hogy milyen valódi (vizuális) megoldást válassz (az például szerintem nyilván nem jó, hogy feldobsz egy figyelmeztető ablakot, mert azt valahogyan "be kell zárni", és emiatt nyilván el kell venned a "fókuszt", ha nem konkrétan "bezáró/elfogadó" gombot raksz ki (hanem mondjuk csak azt figyeled, hogy valamennyire elmozgatta az egeret, és ha igen, akkor bezárod az ablakot, így a felhasználói szinten nyilván "keresztbe" raktál, mert "el kellett" mozgatnia az egeret, "na és, mi van ekkor?", szerintem zavaró), ha minimális elmozdulást figyelsz, akkor ráadásul nem is biztos, hogy "el tudja olvasni" az üzenetet, mert beugrik az ablak, "megijed", hirtelen kicsit mozgat az egérrel és már el is tünteted(?), nem látott belőle semmit, nem is érti, hogy mi volt ez a villanás), jöhet persze az ötletelés: hogy csak bezáró billentyű van és azt kell lenyomnia, azaz nem foglalkozunk a mutató eszközzel, az egérrel, ez már tetszetősebb, de szerintem zavaró a figyelmeztető ablak,
    ekkor jöhet az újabb ötlet: színezzük az aktuális szakaszt: legyen mondjuk piros, ha az előbbi már elfogadott szakasszal egy egyenest alkot, ellenben meg fehér, na ez már talán tetszik, ezt már elfogadhatónak tartanám,
    de inkább azt mondom, hogy ne kössük meg a kezét, rakjon le oda csúcsot, ahova akar, és hozok még indokokat, hogy miért jobb így,
    nyilván az az ésszerű viselkedés, hogy utána "szerkesztheti" is a csúcsokat, nem? a szerkesztésen azt értem, hogy beszúrhat újabbat, törölhet, mozgathat, ... és ekkor megint valahogyan kezelni kell azt, hogy esetleg egy egyenesre eshet három egymást követő (az újabb csúcs hozzáadásánál ez a kiindulás, hiszen nyilván azt vélhetőleg egy adott szakaszra "rakja", csak arrébb akarja vinni, azaz egy adott szakaszt akar megtörni),
    továbbá: mivel a pozicionáló eszközöd, az egered a képernyő koordináta rendszerébe képződik le valójában (hiába a "rajzfelületed" annak nem az 1:1 leképezése, de "eseményként" általában így kapod meg), (mondhatod erre, hogy a te egéreseményfigyelőd/kezelőd, ennél pontosabb, mert x ppi-ben megkaphatod az értéket, ez ok is, de...), ezért valójában egy négyzetrácson helyezhet el csak csúcsokat, és nyilván bizonyos esetekben 3 pont egy négyzetrácson egy egyenesre eshet, az egyik pontot a szomszédosra mozgatva meg nem feltétlenül látszik majd az, hogy megtörik az egyenes, de matematikailag meg már töröttvonal lesz, és ez megint összezavarhatja a felhasználót,
    stb.

    tudom, te semmit nem írtál a GUI-ról, bemenő pontjaid adataid vannak,

    csak arra akartam felhívni a figyelmedet, hogy a legtöbb grafikai algoritmus gyakorlati implementációjánál rengeteg olyan dolog előjön, amire elméletben nagyon "nehéz" felkészülni, azaz sokszor többet kell foglalkozni az ilyen "problémákkal", mint magával az elméleti megoldás lényegi implementációjával,

    jogos ez a kérdés: ki az a h.ly., aki úgy ad meg egy poligont, hogy 3 egymást követő csúcsa egy egyenesen van? mindenki döntse el saját maga, szerintem, (azt is mondhatom, hogy bizonyos esetekben, ez az adott programtól, annak céljától stb., függően esetlegesen jogos igény is lehet erre),


    az epszilonnal kapcsolatban jutott eszembe a következő: anno sok-sok évvel ezelőtt, valamelyik ALU tervezése közben az egyik mérnök felvetette, hogy talán jobb lenne a lebegőpontos számok ábrázolási pontatlansága miatt az egyenlőségvizsgálatnál valamilyen epszilon értéket figyelembe venni, elsőre nagyon jónak tűnt az ötlet, de nyilván elvetették, mert így elveszhetett volna az egyenlőség következő tulajdonsága: ha a=b és b=c, akkor a=c
    (pld. legyen az epszilon=0,75, az a=0, a b=0,5 a c=1, (direkt olyan számokat választottam, amelyek kettedes tört alakja is véges)),

    sajnos a te esetedben is fennállhat az a gond, hogy (ugyanakkora epszilon érték mellett) esetleg nem mindegy a síkot meghatározó 3 pont megválasztása,
    de szerintem ezzel egyszerűen nem tudsz mit kezdeni, jobb, ha együtt élsz vele, vagy megpróbálhatsz agyalni is, hogy mit lehetne tenni... szerintem nincs általános, jó megoldás, pont azért mert "nem tudhatod", hogy a síkodat alkotó pontok "pontatlansága" honnan ered, vagy, hogy annak (a döféspont meghatározásának) milyen olyan valódi következményei lesznek, amikre az hatással lehet, szerintem,
    Mutasd a teljes hozzászólást!
  • Az equ-t értem.
    A determinánst nemigazán értem.
    Mivel a determinánst nem értem ezért a sík egyenletébe való behelyettesítést sem igazán.
    A sík és a szakasz egyenletét amit megjegyzésként írtál azt nagyjából értem, ott van a közös pont ahol a két egyenlet megoldása megegyezik.
    A left-et és a right-ot egyáltalán nem értem hogy micsoda.
    Így gyakorlatilag az egész további részt sem. (kivéve azt a rászt amikor megnézzük hogy a szakasz vagy a meghosszabbítása metszi-e a síkot)

    Ettől függetlenül eddig tökéletesen működik tehát hiba nélkül lefut.

    Ha a szakasz benne van a síkban akkor azt kellene megnézni hogy a szakasz áthalad e a poligon.


    Mutasd a teljes hozzászólást!
  • Amiket nem értettél azok jelenleg nem is fontosak. A determináns alapvető fogalom ebben a témában, de pillanatnyilag ez is nélkülözhető.
    Most csak annyit kell látni, hogy a terjengős képletek helyett kisebb részletekben végezzük a számolást.

    A "left" és a "right" is csak pillanatnyi segédváltozó. Az egyenes paraméteres egyenletrendszerét a sík egyenletébe helyettesítve algebrai szempontból a legegyszerűbb egyismeretlene eldőfokú egyenletet kapunk, viszont ez nagyon terjedelmes, tehát
    (.............................)*t = ................ helyett, tömören:
    left*t = right

    Nem csak a leírás, hanem a programozás miatt is célszerű egy-egy hatalmas méretű és többször használandó képlet eredményét ilyen rögtönzött segédváltozókban tárolni, mint többször ugyanazt kiszámolni.

    A matematikai rész megértéséhez a vektoriális szorzat (cross product) fogalmával érdemes ismerkedni és azt megérteni, hogy három (nem kollineáris) pont síkjának normálvektorát hogyan kapjuk meg ezzel.

    Majd amint lesz kis időm, leírom a pont helyzetét (bent/kint) meghatározó algoritmust.
    Mutasd a teljes hozzászólást!
  • Megpróbáltam C-hez közeli kódolással vázolni egy pontnak a poligonhoz való helyzetét eldöntő algoritmust. Lehetne az alakzatokhoz alkalmasan definiált osztályokat megadni, de most nem ez a fontos - nem is tudom milyen nyelven kódolod?

    Volnának esetek - fentebb sok szó esett róluk - amikor a speciális elhelyezkedést külön kellene kezelni. Most ezzel nem foglalkoztam, nézd meg hogy ez használható-e, aztán még visszatérhetünk rájuk, viszont a legtöbb általános esetben ennek működnie kellene.


    A poligon pontjainak x és y koordinátái, a z-ket 0-nak véve:
    (Vagyis a poligon síkjának az xy alapsíkra való vetítése, amit bizonyos speciális helyzetekben módosítani kell.)

    p[0].x, p[0].y,
    .............
    p[n-1].x, p[n-1].y,

    qx,qy
    a vizsgált pont koordinátái (itt is qz-t 0-nak van véve).

    /////////////////////////////////////////////////////////////////////////////// /* a függvény azt dönti el, hogy a poligon k. és köv. pontja közötti szakasza metszi-e a vizsgél pontból hízott félegyenest? */ int intersection(k, // a poligon szögpontjának sorszáma, 0<=k<n qx,qy) // a vizsgált pont { // visszatérési érték ('bool' is lehetne): // 0: nem metszi, vagy érvénytelen; 1: metszi l=(k<n-1)? k+1: 0; // 'l', a 'k" utáni sorszám p1x=p[k].x; p1y=p[k].y; // az épp visgált szakasz végpontjai p2x=p[0].x; p2y=p[0].y; /* szakasz: (p1x+u*(p2x-p1x) , p1x+u*(p2x-p1x)) (0<=u<=1) félegyenes: (qx+v , qy) (0<=v) ('u' és 'v' a 't'-nek megfelelő paraméterek.) az egyenletrendszer: p1x+u*(p2x-p1x) = qx+v p1y+u*(p2y-p1y) = qy u és v az ismeretlenek ---> v*(p2y-p1y)=(p1x-qx)*(p2y-p1y)-(p1y-qy)*(p2x-p1x) */ left = p2y-p1y; right = (p1x-qx)*(p2y-p1y)-(p1y-qy)*(p2x-p1x); if(equ(left,0)) return 0; // illeszkednek egymásra v. párhuzamosak else v=right/left; if(v<0) return 0; // érvénytelen, mert csak a félegyeses meghosszabbítása metszené u = (qy-p1x)/(p2y-p1y); if(equ(u,0)) return 0; // ez a végpont nem számít if(equ(u,1)) return 1; // ez a végpont számít if((0<u)and(u<1)) return 1; // a szakasz belseje else return 0; // szakasz meghosszabbítása } /////////////////////////////////////////////////////////////////////////////// int points() { //a metszéspontok száma metszi=0; for(i=0; i<n; i++) sum += intersection(i,qx,qy) return metszi; } /////////////////////////////////////////////////////////////////////////////// if(points()%2==1) //belső (ill. határpont) else //külső pont ///////////////////////////////////////////////////////////////////////////////
    Mutasd a teljes hozzászólást!
  • Köszönöm. És abban az esetben ha az XY síkra való kivetítés nem alkalmazható, akkorelég csak kicserélni például az Y-t Z re így XZ síkra kivetítve? vagy arra más egyenletet is kellene alkalmazni? (nyilván figyelve arra hogy a poligon pontjainál is a jó koordinátákat alkalmazzuk)

    És még annyi hogy ezt alkalmazhatom e arra az esetre is amikor az egyenes a síkban van?
    Mutasd a teljes hozzászólást!
abcd