Pont sokszög
A számítógépi geometria ismert probléma pont meghatározására tartozik a sokszög. A gépen, adott sokszög és egy pontot. Szükséges, hogy megoldja a kérdést, hogy a pont a sokszög.
A sokszög lehetnek konvex. és a nem-konvex. Általában azt feltételezzük, hogy a sokszög egyszerű, hogy van, anélkül, hogy magától csomópontok, de a probléma úgy kell tekinteni, nem egyszerű sokszög. Az utóbbi esetben, különböző módokon tagság megállapításának a sokszög eltérő eredményekre vezethetnek. Megkülönböztetni algoritmus nélkül az előfeldolgozás és algoritmusok a kezelés előtti, amelynek során létrehoz néhány adatszerkezetek, amelyek lehetővé teszik a gyorsabb a jövőben, hogy válaszoljon számos kérelmek kellékek pont ugyanarra a sokszög.
sugárkövetéssel eljárás [szerkesztés | szerkesztés wiki szöveg]
Elszámolása a keresztezések számát [szerkesztés | szerkesztés wiki szöveg]
Módszerek eltérően működik egy önmagát metsző sokszög külföldön. Balra: páros-páratlan szabály. Jobbra: nulla kanyargós szabályt.
Az egyik szokásos meghatározási módszerek pont tartozik egy tetszőleges egyszerű poligon a következő. Felhívjuk egy sugár egy adott pontján egy tetszőleges irányba (például a pozitív irányban a vízszintes tengely), és hány alkalommal a sugár metszi a széleit a sokszög. Elég járni egy hurkot a széleit a sokszög és meghatározza, hogy a sugár metszi minden élét. Ha a metszéspontok száma páratlan, akkor kijelenthető, hogy a lényeg belül fekszik sokszög akkor is, ha - a külső. Ennek alapja az az egyszerű megfigyelés, hogy ha mozog a vonal keresztezi minden határpont váltakozva jelenik meg belülről, kívülről a sokszög. Az algoritmus alatt ismert olyan neveket, mint keresztezési száma (szám) algoritmus vagy a páros-páratlan szabály.
Az algoritmus nehézséget jelent a szélsőséges esetben, ha a sugarat keresztezi a csúcs a sokszög. Az egyik technika legyőzni azt kell feltételezni, hogy az ilyen a sokszög csúcsai fekszenek végtelenül fölött (vagy alatt) a direkt nyaláb, és így a kereszteződés valójában nem. [1] Tehát, a gerenda keresztezi a szélén számít, ha az egyik végén a bordák fekszik szigorúan alatt a gerenda, és a másik végén - felett vagy nyugszik a gerenda.
Az algoritmus fut időben O (N) egy, az N-gon.
Számviteli sebesség [szerkesztés | szerkesztés wiki szöveg]
A görbe teszi két forradalom pont körül.
Tekintsük a fordulatok száma, amely megkönnyíti az orientált határa egy sokszög köré az adott pont P. algebrai topológia, ez a szám az úgynevezett index pont képest a görbe. [2] Meg lehet kiszámítani a következők szerint. Mint korábban, a kibocsátás a nyaláb P tetszőleges irányba, és megvizsgálja a bordák, amelyek azt keresztezi. Mindegyik kereszteződés rendelni száma +1 vagy -1, attól függően, hogy a sugár metszi a szélén - az óramutató járásával megegyező (jobbra) vagy ellentétes irányban (jobbról balra). Ez a két esetet lehet megkülönböztetni a jele a skalár szorzat közötti vezetőborda és a vektor irányára merőleges vektor a gerenda. [3] Az összege a kapott értékeket az index pont képest a görbe. Az összeg lehet pozitív vagy negatív, attól függően, hogy a tájékozódás a határon. Ha ez nem nulla, akkor azt feltételezzük, hogy a lényeg belül van egy sokszög, vagy - azon kívül.
Ilyen algoritmus az úgynevezett nulla kanyargós szabályt. [3]
Az egyszerű sokszög, ez a módszer ugyanolyan jól működik, mint a módszer alapján megszámoljuk a kereszteződéseket. A különbség a kettő között látható, ha figyelembe vesszük önmagát metsző sokszög kerettel.
Összegzési módszert sarkok [szerkesztés | szerkesztés wiki szöveg]
Lehetőség van annak meghatározására, hogy a P pont a sokszög belsejében csúcsok C V0. V1. Vn = V0. kiszámításakor az összege:
# X03D5; i = arccos # X2061; (P V i # X2212; 1 # X22C5; P V i | P V i # X2212; 1 | # X22C5; | P V i | ) S i g N (d e t (P V i # X2212; 1 P V i)). = \ ARccOS \ left (\ cdot PV_> | \ cdot | PV_ | >> \ right) jel \ left (detPV _ \\ PV_ \ end> \ right)>.Azt bizonyítja, hogy ez az összeg nem, hogy más, mint a tekercset száma a P pont tekintetében a sokszög határán, akár állandó tényező a 2 # X03C0; . Mi ezért feltételezzük, hogy az a pont kívül esik a sokszög, ha az összeg nulla (vagy közel ahhoz, hogy ez, ha a közelítő számtani használjuk). Azonban ez a módszer nagyon praktikus, mivel nem igényel költséges számítási műveleteket minden egyes éle (inverz trigonometrikus függvények, négyzetgyökök), és „a legrosszabb a világon” algoritmussal meg is nevezték ezt a feladatot. [1]
K. Weiler ajánlottak gyakorlati változata ez a módszer, elkerülve a költséges műveletek és hozzávetőleges számítások. [4] Kimutatták, hogy az összeg a szögek segítségével számítható csak a sokszög pont osztályozó működését negyedelésekben pont körül P. Weiler algoritmus és némi javulás hozzá vannak leírva [5].
Algoritmusok c előkezelés [szerkesztés | szerkesztés wiki szöveg]
Konvex és a csillag sokszögek [szerkesztés | szerkesztés wiki szöveg]
Kiegészítő pont a konvex csillaginkubátorokban N -gon segítségével határozható meg a bináris keresés O (log N), a beruházás O (N) memória és az O (N) idő előfeldolgozás. [6]
Tetszőleges sokszög [szerkesztés | szerkesztés wiki szöveg]
A probléma egy pont tartozik egy tetszőleges egyszerű poligon lehet úgy, mint egy speciális esete a probléma lokalizálását a pontot egy sík al-osztály. Az N-gon, ezt a problémát meg lehet oldani az időben O (log 2 N) O (N) a memória és az O (N log N) idő előfeldolgozás. [7]
Megjegyzések [szerkesztés | szerkesztés wiki szöveg]
Források [szerkesztés | szerkesztés wiki szöveg]
- Kábítószer F. Sheymos M. 2.2: Feladatok pont lokalizáció. // Computational Geometry: Bevezetés. - Moszkva: Mir, 1989.