A meghatározás a pont a háromszög - számítógépes kód
Adott: Van egy háromszög, csak azt tudjuk, a koordinátákat a csúcsok. Van egy pont, tudjuk koordinátáit.
Mit kell tudni: telepíteni kell a tartozék pont a háromszög.
Ez a cikk megérti különböző módszerek meghatározására pont tartozik a háromszög.
Ebben az eljárásban az első terület 3 háromszögek, amelyek egy adott pont mindkét oldalán a háromszög. A mi esetünkben (ábra. 1) háromszögek ABP, BCP, a CAP és a területet s1, s2, s3, ill.
Aztán ott van a terület az ABC háromszög.
Talált tér képest - ha az összeg 3 négyzet egyenlő a területet az egész háromszög, az azt jelenti, hogy az a pont tartozik a háromszög. Összehasonlításképpen, mint általában, adja meg a hibát.
Mivel mi már csak ismert a pontok koordinátáinak, minden területen vannak Heron-képlet. dús műveletek, világos, hogy miért ez a módszer nagyon időigényes.
A legegyszerűbb alkalmazása az algoritmus:
Minden relatív!
Tehát abban az esetben, 3. ábra, a lényeg feküdjön a bal oldalon a vektorok tartoznak a háromszög.
A harmadik módszer, hogy rágyújtok a legérdekesebb számomra.
Az az elképzelés, annak használata akkor keletkezik, amikor nézi a háromszög felében paralelogramma ...
Ez a módszer először ellenőrizni papíron. Miután az összes optimalizálási képleteket, hogy minden összejött, rájöttem, hogy a kódot, ahol bebizonyosodott, hogy nagyon sikeres és eredményes. Már eredményes 2 korábbi módszerek:]
1) egyik csúcsa a háromszög tegye a koordinátákat (0, 0);
2) két oldalán kibocsátó ettől a vertex képviseli vektorként.
Így ki ez a rendszer úgy tűnik, az egyszerű feltételek megtalálása a P pont közötti vektorok b és c. (4.)
Kóddal láthatjuk, milyen az új koordinátáit B és C pontok, amelyek mindkét vektor b és c (4.). Egy új pont koordinátáit P vektorba (Px, Py). A következő a képlet, hogy én korábban svol az általános megjelenését és egyszerűsíteni kell.
Max alapvető műveleteket fordul 13 (4). Egyáltalán nem rossz:]
Ez egy viszonylag jól ismert módszer, különösen, ha a pont határozza meg a tagság az sokszög. Gyakran ez a módszer az úgynevezett „sugárkövetés”, bár ez nem teljesen helyes, mert sugárkövetéssel - számításon utazási fénysugarak egy 3D-s jelenetet.
A lényeg az, hogy ettől a ponttól a elindulna egy fénysugár a bármely tengely bármely irányban.
Ezután ellenőrzik a kereszteződés az a sokszög oldalainak és nyomon követi kereszteződéseket.
Így, az azt jelenti, hogy kívül esik a sokszög, ha a szám páratlan, az azt jelenti, hogy a lényeg benne, ha a metszéspontok száma páros.
5. ábra két kísérleti pontokat P és K, a gerenda egyik metszéspontja P oldalán a háromszög, így a P pont tartozik az ábra mutatja, a K pont nem szerencsés - ő volt két metszéspontja.
Mint a normál I egyszerűsített (a háromszög jelent), de nekem úgy tűnik, hogy talán a meredek ...
És így, kiderül mintegy 30 műveleteket.
Nos, itt is jön az izgalmas rész! Aki gyorsabb és erősebb. ]
Töltöttem a következő paramétereket a teszt (bár ez függ a CPU):
- az ismétlések számát az algoritmus a szimuláció 1 = 4000000.
- számú szimulációk minden algoritmus = 1000.
Mit is mondhatnék, a vektor módszer jó)
Ezzel biztosan versenyben második módja képest a pontot, de a fő különbség az, hogy a rel. pont szigorú orientáció oldalán a háromszög, és a vektor nem fontos, ezért hidegebb)