algoritm: inne eller ute ?

[persika]

Hur avgör man i ett program om en punkt ligger innanför eller utanför en oregelbunden månghörning ? Hur är algoritmen för det ?

[RasmusB]

Du rör dig ut mot bildens kant och räknar efter hur många gånger du korsar en polygonkant. Udda antal korsningar = innanför, jämnt = utanför.

Edit:
http://freespace.virgin.net/hugo.elias/ ... _polyd.htm

Kolla under "Does a point lie within a polygon?"

[SvenW]

Ett tänkbart sätt, som inte nödvändigtvis är det bästa, är att gå runt månghörningen och för varje segment se om punkten ligger till höger eller vänster om segmentet, och sedan ta ett majoritetsbeslut.
För höger/vänster beslut kan man ta vektorprodukten för respektive segment.
Jag har sådana basfunktioner i Hec.
http://w1.318.comhem.se/~u31829222/index.html

Välj senaste version. Titta i utils1.c, specifikt vector_product_length ();

PS. Här finns även funktioner för att se om man korsar ett segment, som behövs i metoden ovan (RasmusB's inlägg)

[persika]

Intressanta svar!

Ang. första svaret: Om man betraktar månghörningen som ett antal linjer och och en linje mellan punkten och nånstans utanför, så ska man då räkna antal skärningar som "punktlinjen" har med de övriga. Lite jobbigt specialfall när linjen skär precis innifrån ett hörn.

Ang. andra svaret: Gjorde några skisser med papper o penna med olika månghörningar, fick inte alltid rätt svar.

[JonasJ]

Titta även här http://www.faqs.org/faqs/graphics/algorithms-faq/ under punkt 2.03.

Det som RasmusB skrev är vad jag vet en ganska standardlösning för detta problem.