---

Hvordan afgør man matematisk hvornår et punkt ligger indenfor eller udenfor
for det areal en vilkårlig trekant dækker?

Venlig hilsen,
Morten

---

Scripsit "Morten Larsen" <m-larsen@post6.tele.dk>

> Hvordan afgør man matematisk hvornår et punkt ligger indenfor eller udenfor
> for det areal en vilkårlig trekant dækker?

Jeg går ud fra at du har dine punkter liggende i et koordinatsysstem.
Så er det mest nærliggende:

For hver af siderne a, b, og c: tjek at dit punkt ligger på samme
side af siden (!) som det modstående hjørne.

Det enkelte tjek kan udføres ved hjælp af følgende regel:

Hvis en linje går gennem de to forskellige punkter (x1,y1) og
(x2,y2), har den ligningen

(y1-y2)*x + (x2-x1)*y + x1*y2-x2*y1 = 0

Venstresiden er positiv når (x,y) er på den ene side af linjen,
negativ når (x,y) er på den anden side af linjen.

--
Henning Makholm "Hell, every other article you read
is about the Mars underground, and how
they're communists or nudists or Rosicrucians --"

---

In <yah65zfu82a.fsf@pc-043.diku.dk> Henning Makholm <henning@makholm.net> writes:

>Scripsit "Morten Larsen" <m-larsen@post6.tele.dk>

>> Hvordan afgør man matematisk hvornår et punkt ligger indenfor eller udenfor
>> for det areal en vilkårlig trekant dækker?

>Jeg går ud fra at du har dine punkter liggende i et koordinatsysstem.
>Så er det mest nærliggende:

> For hver af siderne a, b, og c: tjek at dit punkt ligger på samme
> side af siden (!) som det modstående hjørne.

>Det enkelte tjek kan udføres ved hjælp af følgende regel:

> Hvis en linje går gennem de to forskellige punkter (x1,y1) og
> (x2,y2), har den ligningen

> (y1-y2)*x + (x2-x1)*y + x1*y2-x2*y1 = 0

> Venstresiden er positiv når (x,y) er på den ene side af linjen,
> negativ når (x,y) er på den anden side af linjen.

>--
>Henning Makholm "Hell, every other article you read
> is about the Mars underground, and how
> they're communists or nudists or Rosicrucians --"

Her er en implementering af samme i perl:
http://hjem.get2net.dk/bnielsen/trekant.html

Jeg overvejede på et tidspunkt om det her faktisk gælder:

Hvis trekantens hjørner kaldes A, B og C og det givne punkt P,
så ligger P i eller på ABC hvis og kun hvis arealet af ABP +
arealet af ACP + arealet af BCP tilsammen giver arealet af ABC.

Men jeg kom ikke så langt at jeg havde overbevist mig selv om
at der ikke var modeksempler og man løber også panden mod
noget numerisk usikkerhed, så den med siderne er klart bedre.

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

bnielsen@daimi.au.dk (Kai Birger Nielsen) writes:

> Jeg overvejede på et tidspunkt om det her faktisk gælder:
>
> Hvis trekantens hjørner kaldes A, B og C og det givne punkt P,
> så ligger P i eller på ABC hvis og kun hvis arealet af ABP +
> arealet af ACP + arealet af BCP tilsammen giver arealet af ABC.

'Kun hvis' er trivielt.

For at vise 'hvis' kontraponerer vi udsagent og får:
Hvis P ligger uden for ABC så er A(ABC)<A(ABP)+A(ACP)+A(BCP)
hvor A(X) står for arealet af X.
Hvis vi bruger Hennings metode kan vi slutte at P ligger til højre for
en af sideren i ABC (vi gennemløber naturligvis ABC i positiv
omløbsretning) og vi kan antage at det er BC. Det ses nu let at ABC
\subset ABPC, og føljelig er
A(ABC)<A(ABPC)=A(ABP)+A(APC)<A(ABP)+A(ACP)+A(ABP), hvilket giver det
ønskede.

> at der ikke var modeksempler og man løber også panden mod
> noget numerisk usikkerhed, så den med siderne er klart bedre.

Er den numeriske usikkerhed ikke kun et problem når P ligger tæt på en
af siderne? Indeholder den anden metode ikke en tilsvarende numerisk
usikkerhed?

..Henrik

--
Min signatur er taget på sommerferie.

---

In <7g1ya3visf.fsf@serena.fsr.ku.dk> Henrik Christian Grove <grove@sslug.dk> writes:

>bnielsen@daimi.au.dk (Kai Birger Nielsen) writes:

>> Jeg overvejede på et tidspunkt om det her faktisk gælder:
>>
>> Hvis trekantens hjørner kaldes A, B og C og det givne punkt P,
>> så ligger P i eller på ABC hvis og kun hvis arealet af ABP +
>> arealet af ACP + arealet af BCP tilsammen giver arealet af ABC.

>'Kun hvis' er trivielt.

Ja.

>For at vise 'hvis' kontraponerer vi udsagent og får:
> Hvis P ligger uden for ABC så er A(ABC)<A(ABP)+A(ACP)+A(BCP)
>hvor A(X) står for arealet af X.
>Hvis vi bruger Hennings metode kan vi slutte at P ligger til højre for
>en af sideren i ABC (vi gennemløber naturligvis ABC i positiv
>omløbsretning) og vi kan antage at det er BC. Det ses nu let at ABC
>\subset ABPC, og føljelig er
>A(ABC)<A(ABPC)=A(ABP)+A(APC)<A(ABP)+A(ACP)+A(ABP), hvilket giver det
>ønskede.

Ok. Den argumentation køber jeg.

>> at der ikke var modeksempler og man løber også panden mod
>> noget numerisk usikkerhed, så den med siderne er klart bedre.

>Er den numeriske usikkerhed ikke kun et problem når P ligger tæt på en
>af siderne? Indeholder den anden metode ikke en tilsvarende numerisk
>usikkerhed?

Jo. Jeg tænkte blot på at testen A(ABC) = A(ABP)+A(ACP)+A(BCP)
ikke var så rar. En test på < er mindre giftig.

Gad vide om ikke arealtesten faktisk er ganske effektiv, hvis man
har koordinaterne til punkterne ?

Det dobbelte areal af trekanten kan fås med 6 multiplikationer og
det giver 24 multiplikationer for den samlede test.
Den, der tester for sammesidethed bruger en hel del flere.

Her er arealtesten kodet i perl, hvis nogen er interesseret:

sub darea {
my($ax,$ay,$bx,$by,$cx,$cy) = @_;
return abs ($ax*$by+$bx*$cy+$cx*$ay-$ax*$cy-$bx*$ay-$cx*$by);
}

sub inTriangle {
my($ax,$ay,$bx,$by,$cx,$cy,$px,$py) = @_;
my($ok) = 0;
$ok = 1 if
darea($ax,$ay,$bx,$by,$cx,$cy) >=
darea($ax,$ay,$bx,$by,$px,$py) +
darea($ax,$ay,$px,$py,$cx,$cy) +
darea($px,$py,$bx,$by,$cx,$cy);
return $ok;
}

og lidt testomgivelser, der som output giver en ppm bitmap af
trekanten.

my($x,$y);
print "P1 81 91\n";
for $y (0..90) {
for $x (20..100) {
print inTriangle(20,30,70,90,100,0,$x,90-$y);
}
print "\n";
}

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

Scripsit bnielsen@daimi.au.dk (Kai Birger Nielsen)

> Det dobbelte areal af trekanten kan fås med 6 multiplikationer og
> det giver 24 multiplikationer for den samlede test.
> Den, der tester for sammesidethed bruger en hel del flere.

Hm, hvis vi kun tæller multiplikationer og allerede kender det rigtige
fortegn, koster en side i sammesidethedstesten 4 multiplikationer. Det
giver 12 for testene.

Det "rigtige" fortegn bliver det samme for alle tre sider (hvilket kan
indses intuitivt, eller teoretisk via Karins konvekse metode), så det
behøver vi kun at udregne i første test, hvilket koster 2
multiplikationer ekstra (konstantleddet behøves kun at blive udregnet
en gang).

I alt 14 multiplikationer for sammesidethedstesten. Og nogenlunde
samme antal additioner/subtraktioner som din arealtest. Desuden kan
sammesidethedstesten kortsluttes hurtigt, hvis man er så heldig at
det er første side eller anden side der fejler.

> Her er arealtesten kodet i perl, hvis nogen er interesseret:

Og her er sidethedstesten:

sub rigtigSideEllerPaaLinjen {
my($x,$y,$a,$b,$c) = @_ ;
my $xkoeff = $y[$a]-$y[$b] ;
my $ykoeff = $x[$b]-$x[$a] ;
my $konstant = $x[$a]*$y[$b] - $x[$b]*$y[$a] ;
defined($fortegn) or
$fortegn = ($xkoeff*$x[$c] + $ykoeff*$y[$c] + $konstant) > 0;
my $polyv = $xkoeff*$x + $ykoeff*$y + $konstant ;
return $polyv == 0 || ($polyv > 0) == $fortegn ;
}

sub iTrekanten {
my($x,$y) = @_ ;
undef $fortegn ;
return rigtigSideEllerPaaLinjen($x,$y,1,2,3)
&& rigtigSideEllerPaaLinjen($x,$y,2,3,1)
&& rigtigSideEllerPaaLinjen($x,$y,3,1,2);
}

@x = ("nul er ikke et indeks",20,70,100);
@y = ("nul er ikke et indeks",30,90, 0);
my($x,$y);
print "P1 81 91\n";
for $y (0..90) {
for $x (20..100) {
print iTrekanten($x,90-$y) ? "1" : "0" ;
}
print "\n";
}


--
Henning Makholm "En tapper tinsoldat. En dame i
spagat. Du er en lykkelig mand ..."

---

Tak for de gode svar.

Jeg har benyttet mig af Henning Makholm's metode. Den er dejlig enkel,
i hvert fald set i forhold til, hvad jeg selv var kommet frem til.
Hvilket er :

Punktet P ligger indenfor eller på trekant ABC hvis

vinkel BAP <= vinkel A og vinkel CAP <= vinkel A
vinkel ABP <= vinkel B og vinkel CBP <= vinkel B
vinkel ACP <= vinkel C og vinkel BCP <= vinkel C

Metoden ser ud til at virke.

Jeg har konstrueret et lille windows-program.
I programmet har jeg indtastet koordinaterne til en tilfældig trekant.
(Den er nogenlunde kommet til at ligne den fra mine første forsøg
på papir. A(50,-50), B(150,-20), C(170,-200)).
Når jeg flytter musen rundt, får punktet P sine koordinater fra
musens position i vinduet. Derefter beregner programmet så om P
ligger indenfor/på eller underfor trekanten vha. formlen.
Jeg kan altså med musen søge om der er nogle punkter hvor resultatet
af formlen ikke stemmer overens med hvad der ser rigtigt ud.

Der er dog et eller andet der driller.

Blandt flere er punktet (158, -91). Jeg kan se at musen, og dermed
punktet P ligger på linien BC, men formlen siger "udenfor".

Hvis jeg beregner den linie der går gennem punkterne B og C, for at
undersøge om hvorvidt punktet (158, -91) ligger på linien, så viser
det sig at det gør punktet. Formlen burde altså sige "indefor".

Det første jeg bemærkede ved Henning Makholm's metode var at den kun
benytter heltalsberegninger. Det udelukker jo det mest oplagte, nemlig
afrundingsfejl.

Nu skal jeg lige have pløjet koden for eventuelle fejl, jeg kan dog ikke
lige se nogle oplagte fejkilder.

Anyway, tak for svarene.

Venlig hilsen,
Morten Larsen

---

Morten Larsen wrote:
> Metoden ser ud til at virke.

OK, men kun i 2 dimensioner. Hvordan generaliseres den til n dimensioner
(n \in Z)?

Venligst,
PMD

---

Scripsit Paul Matthias Diderichsen <pmd@fysik.dtu.dk>
> Morten Larsen wrote:

> > Metoden ser ud til at virke.

> OK, men kun i 2 dimensioner. Hvordan generaliseres den til n dimensioner
> (n \in Z)?

Uha, så skal man først generalisere trekanten til enten en simplex
eller ihvertfald en konveks polytop.

Derefter skal man finde en generel måde at lave en ligning for en
hyperflade som udspændes af n kendte punkter. I 3 dimensioner kan
man finde en normalvektor som krydsproduktet af to af sidevektorerne.
Generelt kan jeg ikke finde lige ryste bedre end at løse ligningssystemet

a_1 x_{1,1} + ... + a_n x_{1,n} + b = 0
: : : :
a_1 x_{n,1} + ... + a_n x_{n,n} + b = 0

direkte for a_i, b, ud af ærmet.

--
Henning Makholm "Det er sympatisk du håner dig selv. Fuldt
berettiget. Men det gør dig ikke til en kristen."

---

Scripsit "Morten Larsen" <m-larsen@post6.tele.dk>

> (Den er nogenlunde kommet til at ligne den fra mine første forsøg
> på papir. A(50,-50), B(150,-20), C(170,-200)).

> Blandt flere er punktet (158, -91). Jeg kan se at musen, og dermed
> punktet P ligger på linien BC, men formlen siger "udenfor".

Hm. Så vidt jeg kan regne ud vil det være punktet (158,-92) der ligger
på linjen, hvilket bl.a. kan ses ved at
(158,-92) - (150,-20) = (8,-72) = 2 * (4,-36)
og
(170,-200) - (158,-92) = (12,-108) = 3 * (4,-36)
er parallelle.

(158,-91) er dermed en enkelt enhed for langt oppe og
derfor ganske rigtigt udenfor trekanten.

--
Henning Makholm "Jeg køber intet af Sulla, og selv om uordenen griber
planmæssigt om sig, så er vi endnu ikke nået dertil hvor
ordentlige mennesker kan tillade sig at stjæle slaver fra
hinanden. Så er det ligegyldigt, hvor stærke, politiske modstandere vi er."

---

"Morten Larsen" <m-larsen@post6.tele.dk> wrote in message news:<3d341897$0$46279$edfadb0f@dspool01.news.tele.dk>...
> Hvordan afgør man matematisk hvornår et punkt ligger indenfor eller udenfor
> for det areal en vilkårlig trekant dækker?
>
> Venlig hilsen,
> Morten

Hvad med at bruge konvekse kombinationer? Trekanten er det konvekse
hylster af sine 3 hjørner: Dvs W=(w1,w2) ligger på eller inden for
trekanten præcis hvis

W=aX+bY+cZ, hvor X=(x1,x2),Y=(y1,y2),Z=(z1,z2) er de 3 hjørner og
a+b+c=1 og a,b,c alle ligger i det lukkede interval fra 0 til 1.

Ligningssystemet er

ax1+by1+cz1=w1
ax2+by2+cz2=w2
a+b+c=1

Som matrix

(x1 y1 z1)(a) (w1)
(x2 y2 z2)(b)=(w2)
(1 1 1 )(c) (1)

Jeg håber det kan læses som en matrix/søjle ligning. Kald 3x3 matricen
P og dens inverse Q, så fås (a,b,c) (jeg tillader mig at skrive søjlen
som vektor) som Q(w1,w2,1). Så er (w1,w2) indenfor trekanten præcis
når a,b,c alle er ikke-negative. For en trekant skal du så blot
udregne den inverse Q og indsætte punktets koordinater. Det
generaliseres umiddelbart til konvekse objekter i n-dimensionale rum.

Mvh Karin

---

Scripsit k3emmer@yahoo.dk (karin)
> "Morten Larsen" <m-larsen@post6.tele.dk> wrote

> > Hvordan afgør man matematisk hvornår et punkt ligger indenfor eller udenfor
> > for det areal en vilkårlig trekant dækker?

> Hvad med at bruge konvekse kombinationer? Trekanten er det konvekse
> hylster af sine 3 hjørner: Dvs W=(w1,w2) ligger på eller inden for
> trekanten præcis hvis
....

> (x1 y1 z1)(a) (w1)
> (x2 y2 z2)(b)=(w2)
> (1 1 1 )(c) (1)

Hmm, hvis man løser det ligningssystem med Cramers regel og omordner
tællerne som polynomier i (w1,w2) [1], ender man med præcis samme
formel i tællerne som jeg angav i "side"-metoden.

[1] Løsning + omordning kan gøres i et skridt ved at invertere
matricen ved hjælp af "expansion by minors", men det kan jeg ikke
lige huske hvad hedder på dansk.

Eftersom man kun er interesseret i fortegnene behøver man ikke
foretage divisionen, men i stedet kan man udregne nævneren (=
determinanten af 3×3-matricen) en gang for alle og notere sig hvilket
fortegn den har. Så behøver man ikke, som i min metode, sætte
koordinaterne for hvert hjørne ind i den modstående sides ligning
for at finde fortegnet (som jo også af rent geometriske grunde
vil være det samme for alle tre sider).

> For en trekant skal du så blot udregne den inverse Q og indsætte
> punktets koordinater. Det generaliseres umiddelbart til konvekse
> objekter i n-dimensionale rum.

Ja, ihvertfald hvis du med objekter mener simplekser.

--
Henning Makholm "Guldnålen er hvis man har en *bror* som er *datalog*."