Komolyabb koordináta geometria, pont benne van e a sokszögben?

Feltételezem, tudod a pontok sorrendjét is, mert ha nem, akkor a pontok magukban nem határozzák meg a sokszöget, tehát nincs megoldás.

Vektorokat húznék a pontból a sokszög csúcsaihoz, sorrendben. Utána ezeknek a vektoroknak az irányát vizsgálnám (merre forognak, hányszor változtatnak forgásirányt stb.) Lehet, hogy nem segít, de elsőnek erre indulnék el.

2D

Sokkal egyszerűbb, mint gondolnátok. Ha a poligon csúcspontjainak koordinátái megvannak akkor csak annyit kell tenni, hogy a pontból BÁRMELY koordináta tengely irányába (nem kell a koordináta rendszer tengelyébe esnie, de könnyebb azzal számolni) félvégtelen egyenest kell húzni, majd meg kell számolni, hogy mennyi oldallal van metszéspontja. Ez az összeg+1 páros akkor benne van, ha páratlan akkor nincs.

Rajzold le, ellenőrizd. Lehet konkáv, konvex, tökmindegy.

Az algoritmusodnak el kell tudnia dönteni, hogy ha a pont éppen valamelyik oldalra esik, akkor azt bentinek, vagy kintinek tekinted.

Algoritmus:

A pont koordinátáiból illetve a poligon koordináták segítségével felveszel egy olyan szakaszt, aminek egyik pontja a 'pont', másik pedig egy olyan ami BIZTOSAN a poligonon kívülre esik. (megkeresed a poligon x koordinátinak maximumát, és szorzod 2-vel) Ez a félvégtelen!!!

Felveszed az első és második koordinátát a poligonból, egyenes egyenlete, majd vizsgálod, van-e metszéspont. Utána a 2. és 3. pontra írod fel az egyenletet, megint vizsgálod.

Így végig, de ne felejtsd el a legutolsónál az utolsó és az elsőre kell felírni az egyenletet! :-)

hát ez nekem is ködös volt, de ha valaki kifejtené, vagy ábrázolná pontosan mi is történik annak örülnék mert érdekel. Azok alapján amit felfogtam belőle kérdezném:

Ha már egyszer úgy is meg kell határoznod az oldalak egyenleteit, mert hogy enélkül metszést sem tudsz vizsgálni, meg te is mondtad, hogy szükség van ezekre az egyenletekre, akkor nem egyszerűbb egyből egyenlőtlenségnek felírni, tehát hogy a poligonod melyik féltérben van az alapján? És ezután már metszéseket sem kell vizsgálnod meg semmit, csak a keresett pont koordinátáit behelyettesíted a változókba és ennyi..

mondok példát:

(0,0) (0,1) (1,1) (0,1) pontok áldal meghatározott egység oldalú négyzet, érdekel minket, hogy az (x,y) pont belül van vagy kívül:

x<1

x>0

y<1

y>0

ez a négy egyenlőtlenségünk, ahogy félsíkok metszeteként meghatároztuk a négyzetet, ide behelyettesítjük az x-et és y-t, ha mindegyikre igaz jön ki (tehát és művelet van köztük), akkor belül van, ha létezik ami nem teljesül, akkor kívül. És ez akárhány dimenzióban működik, és az egyenletek kiszámolása után már semmilyen extra pont hozzávétel, vagy segéd szakasz vagy segéd egyenes, semmi sem szükséges hozzá. Lehet valamit félre értelmezek, de én tényleg nem értem, hogy miért nem ez az egyszerűbb.

Csak pont ezeknek az egyenlőtlenségeknek a felírása a nehéz. Mármint hogy kisebb legyen vagy nagyobb. Persze, felrajzolva, ránézve egyszerű, de itt egy programnak kell "felismernie" a helyzetet. Bár lehet, hogy ezt nem olyan bonyolult algoritmizálni, mint én gondolom.

A vonalhúzogatás és metszéspont-számolgatás szerintem sem járható út, mert metszéspontot mindig kapunk (hacsak nem párhuzamosan haladunk az egyik egyenessel), de az nem biztos, hogy az oldalszakaszon lesz. Ezt megint külön kéne vizsgálni.

Sziasztok!

Pedig tényleg így kell, sőt algoritmust is sokkal egyszerűbb írni rá, illetve konvex, konkáv mindegy neki.

Ha a pont éppen ráesik a poligon egyik oldalára, akkor a programot simán ki kell ugrasztani a ciklusból és csak annyit kell tenni, hogy belső pontnak, vagy külsőnek tekintjük. Ezt írtam fentebb is. Az algoritmust nagyon könnyű átírni úgy, hogy ha a vizsgálandó pontból húzott szakasz átmegy egy csúcsponton, akkor egész egyszerűen alfa szöggel elforgatjuk ezt a szakaszt, majd újra vizsgáljuk.

A félteres megoldásra:

Ha a síkidom olyan, hogy pl 5 szög, de olyan, hogy rendes négyzet alpú de, az 5. pont pedig "bent" a felső oldalhoz közel van, akkor hogyan döntöd el?

A másik válaszolónak:

Metszéspontot kapunk, de mint fentebb írtam az a lényeg hogy MENNYIT!!!

Ha a metszéspontok száma + 1 páros, akkor...., ha páratlan akkor.......