---

Hej

Er der nogen der vil hjælpe mig med en måde til at bestemme om et
punkt er indenfor eller udenfor en figur i et koordinatsystem.

Det skal ikke bare kunne være en tre- eller firkant, men også et
vilkårligt polygon.

Jeg er ikke matematiker og aner derfor ikke om det er relativt enkelt
eller uhyre kompliceret. Hvis det sidste er tilfældet er jeg også glad
for bare at få dén oplysning.

På forhånd tak

---

"Erik" <nettet@stofanet.dk> wrote in message
news:619f1747.0411100049.5ca431fd@posting.google.com...
> Hej
>
> Er der nogen der vil hjælpe mig med en måde til at bestemme om et
> punkt er indenfor eller udenfor en figur i et koordinatsystem.
>
> Det skal ikke bare kunne være en tre- eller firkant, men også et
> vilkårligt polygon.
>
> Jeg er ikke matematiker og aner derfor ikke om det er relativt enkelt
> eller uhyre kompliceret. Hvis det sidste er tilfældet er jeg også glad
> for bare at få dén oplysning.

Dette her har jeg brugt til noget GPS alarm:

http://graphics.cs.ucdavis.edu/~okreylos/TAship/Spring2000/PointInPolygon.html

http://www.acm.org/pubs/tog/editors/erich/ptinpoly/

--
mvh/rg. Christian
I would have to ask the questioner. I haven't had a chance to ask
the questioners the question they've been questioning.
-- George W. Bush, Austin, Texas, Jan. 8, 2001

---

nettet@stofanet.dk (Erik) writes:

> Er der nogen der vil hjælpe mig med en måde til at bestemme om et
> punkt er indenfor eller udenfor en figur i et koordinatsystem.
>
> Det skal ikke bare kunne være en tre- eller firkant, men også et
> vilkårligt polygon.
>
> Jeg er ikke matematiker og aner derfor ikke om det er relativt enkelt
> eller uhyre kompliceret. Hvis det sidste er tilfældet er jeg også glad
> for bare at få dén oplysning.

Den traditionelle metode er: Tegn en streg fra punktet til et sted,
man ved er udenfor figuren. Hvis stregen krydser figurens kant et
ulige antal gange, så er punktet inde i figuren, ellers er den
udenfor.

Men en polygon skal man altså finde ud af hvor mange af polygonens
kanter, stregen krydser. Man skal passe lidt på i de punkter, hvor to
kanter mødes, så man ikke kommer til at tælle dem med to gange.

   Torben

---

Torben Ægidius Mogensen wrote:
> nettet@stofanet.dk (Erik) writes:

>>Er der nogen der vil hjælpe mig med en måde til at bestemme om et
>>punkt er indenfor eller udenfor en figur i et koordinatsystem.
>>
>>Det skal ikke bare kunne være en tre- eller firkant, men også et
>>vilkårligt polygon.
>>
>>Jeg er ikke matematiker og aner derfor ikke om det er relativt enkelt
>>eller uhyre kompliceret. Hvis det sidste er tilfældet er jeg også glad
>>for bare at få dén oplysning.
>
>
> Den traditionelle metode er: Tegn en streg fra punktet til et sted,
> man ved er udenfor figuren. Hvis stregen krydser figurens kant et
> ulige antal gange, så er punktet inde i figuren, ellers er den
> udenfor.
>
> Men en polygon skal man altså finde ud af hvor mange af polygonens
> kanter, stregen krydser. Man skal passe lidt på i de punkter, hvor to
> kanter mødes, så man ikke kommer til at tælle dem med to gange.

Torbens metode er illustreret her. Bemærk, at den også virker, hvis
der er huller i figurene.

<http://astronomy.swin.edu.au/~pbourke/geometry/insidepoly/>

--
Jens Axel Søgaard

---

Jens Axel Søgaard <usenet@soegaard.net> writes:

> > Den traditionelle metode er: Tegn en streg fra punktet til et sted,

Hvad med spørgsmålet: Går en given linie gennem en given polygon? Er
det lige så nemt?

--
Brian (remove the sport for mail)
http://www.et.dtu.dk/staff/be/be.html

---

Brian Elmegaard wrote:

> Jens Axel Søgaard <usenet@soegaard.net> writes:

>>>Den traditionelle metode er: Tegn en streg fra punktet til et sted,

> Hvad med spørgsmålet: Går en given linie gennem en given polygon? Er
> det lige så nemt?

Nej, det er nemmere.

For hver side i polygonen finder du af, om siden skærer linjen.
Hvis ingen sider skærer linjen, skærer den ikke polygonen; ellers
gør den.

Nu spurgte hverken du eller Erik ikke om trekanter, men Kai Birger
Nielsen forklarer så godt, hvordan man klarer problemet "Er punktet
i trekanten?" elegant:

<http://www.246.dk/trekant.html>
--
Jens Axel Søgaard

---

Jens Axel Søgaard <usenet@soegaard.net> writes:

> Nej, det er nemmere.

Nå ja. Sådan må det være. Tak.

--
Brian (remove the sport for mail)
http://www.et.dtu.dk/staff/be/be.html

---

Tak alle sammen for jeres svar - det var enklere end jeg troede.

---

nettet@stofanet.dk (Erik) wrote in
news:619f1747.0411100049.5ca431fd@posting.google.com:

> Hej
>
> Er der nogen der vil hjælpe mig med en måde til at bestemme om et
> punkt er indenfor eller udenfor en figur i et koordinatsystem.
>
> Det skal ikke bare kunne være en tre- eller firkant, men også et
> vilkårligt polygon.
>
> Jeg er ikke matematiker og aner derfor ikke om det er relativt enkelt
> eller uhyre kompliceret. Hvis det sidste er tilfældet er jeg også glad
> for bare at få dén oplysning.
>
> På forhånd tak

Vi bruger følgende metode her på bjerget:
Find vinklen på hver af vektorene fra punktet til polygonens hjørner.

Er punktet inden for polygonens hjørner er summen af vinklerne 0 eller 360
Er punktet uden for, er vinklen noget andet

Om det virker på figurer der er krøllet inden i sig selv er jeg ikke helt
sikker på.


--
Kind regards Jens Borchert Pedersen
Odense Steel Shipyard Ltd. PO Box 176 , DK-5100 Odense C , DENMARK
mailto:jp@oss.junkdk | http://www.oss.junkdk
phone: +45 6397 1027 | fax: +45 6397 2360