---

En form, som ligger i et plan, er givet ved et punkter og en liste af
vektorer i R3, og skal undersøges for om den er konveks.
Er en simpel og fuldgyldig metode ikke at for hver vektor og dens
efterfølger at beregne krydsproduktet. Skifter resultatvektoren retning
(drejer mere end 90 grader), så er formen ikke konveks. Ellers er den?

Ligger formen eksempelvis i XZ-planet, så vil krydsproduktet gå langs
y-aksen, eller modsat y-aksen, alt efter hvilken retning man kører rundt.
Produktets retning vil dog ikke skifte. Hvis formen er konkav, så vil
produktet undervejs både gå med og mod y-aksen.

Jeg overser ikke noget her, vel? En anden metode kunne være at for hver
vektor at teste om alle hjørne-punkter ligger på samme side af vektoren. Det
er dog lidt langsommere. Hvad er den "gængse" metode?

---

Jakob Nielsen wrote:
> En form, som ligger i et plan, er givet ved et punkter og en liste af
> vektorer i R3, og skal undersøges for om den er konveks.

Du vil altså undersøge, om en polygon (mangekant) er konveks, men du ved
ikke på forhånd i hvilket plan i R³ den ligger?

> Er en simpel og fuldgyldig metode ikke at for hver vektor og dens
> efterfølger at beregne krydsproduktet. Skifter resultatvektoren retning
> (drejer mere end 90 grader), så er formen ikke konveks.

Jo, den metode skulle virke. Den er endda beskrevet her:
http://mathworld.wolfram.com/ConvexPolygon.html (det "vinkelrette
prikprodukt" = "perp dot product" er netop lig den vinkelrette komposant
af krydsproduktet, så det er den samme metode).

For at undersøge, om krydsprodukterne skifter retning, kan du beregne
prikproduktet mellem to på hinanden følgende krydsprodukter. Dette skal
altid være positivt, for at krydsprodukterne har samme retning.

> En anden metode kunne være at for hver vektor at teste om alle
> hjørne-punkter ligger på samme side af vektoren. Det
> er dog lidt langsommere.

Ja. Det giver en udførelsestid, som er kvadratisk i antallet af kanter.
Du kunne evt. nøjes med for hver kantvektor at tjekke, at bare de to
nærmeste hjørner ligger på samme side af kantvektoren. Så bliver
udførelsestiden lineær i antallet af kanter (ligesom den første metode).

> Hvad er den "gængse" metode?

Aner det ikke.

--
Jonas Møller Larsen

---

> Jo, den metode skulle virke. Den er endda beskrevet her:
> http://mathworld.wolfram.com/ConvexPolygon.html (det "vinkelrette
> prikprodukt" = "perp dot product" er netop lig den vinkelrette komposant
> af krydsproduktet, så det er den samme metode).

Det var da rart. Kunne faktisk ikke finde noget om det, hvilket overraskede
en del. Det må være almindeligt at skulle sikre sig at en form er konveks.

> For at undersøge, om krydsprodukterne skifter retning, kan du beregne
> prikproduktet mellem to på hinanden følgende krydsprodukter. Dette skal
> altid være positivt, for at krydsprodukterne har samme retning.

Ja, for en form i et vilkårligt plan vil det dække det ind.
Takker for svaret. Ville bare gerne sikre mig at jeg ikke overså noget
banalt i denne sammenhæng. Det ville ikke være første gang.

---

Jonas Møller Larsen <nospam@nospam.invalid> writes:

> Jakob Nielsen wrote:
> > En form, som ligger i et plan, er givet ved et punkter og en liste af
> > vektorer i R3, og skal undersøges for om den er konveks.
>
> Du vil altså undersøge, om en polygon (mangekant) er konveks, men du ved
> ikke på forhånd i hvilket plan i R³ den ligger?
>
> > Er en simpel og fuldgyldig metode ikke at for hver vektor og dens
> > efterfølger at beregne krydsproduktet. Skifter resultatvektoren retning
> > (drejer mere end 90 grader), så er formen ikke konveks.
>
> Jo, den metode skulle virke. Den er endda beskrevet her:
> http://mathworld.wolfram.com/ConvexPolygon.html (det "vinkelrette
> prikprodukt" = "perp dot product" er netop lig den vinkelrette komposant
> af krydsproduktet, så det er den samme metode).

Det forudsætter dog, at kanterne ikke skærer hinanden. En femtakket
stjerne er f.eks. ikke konveks, men vil passere den beskrevne test.

   Torben

---

> Det forudsætter dog, at kanterne ikke skærer hinanden. En femtakket
> stjerne er f.eks. ikke konveks, men vil passere den beskrevne test.

Ja, det kan jeg godt se. Havde nu overset den i første omgang. Til mit brug
er det en form der er _så_ugyldig at jeg fristes til at lade brugeren lave
den alligevel, bare for at han kan blive klogere .-)
Ellers må man jo vende tilbage til metoden med at sikre at alle hjørner er
på eller under enhver af kanterne. Den kan jeg ikke se hvordan skulle fejle

---

"Jakob Nielsen" <a@b.c> writes:

> > Det forudsætter dog, at kanterne ikke skærer hinanden. En femtakket
> > stjerne er f.eks. ikke konveks, men vil passere den beskrevne test.
>
> Ja, det kan jeg godt se. Havde nu overset den i første omgang. Til mit brug
> er det en form der er _så_ugyldig at jeg fristes til at lade brugeren lave
> den alligevel, bare for at han kan blive klogere .-)
> Ellers må man jo vende tilbage til metoden med at sikre at alle hjørner er
> på eller under enhver af kanterne. Den kan jeg ikke se hvordan skulle fejle

Det kræver kvadratisk tid at sammenligne hver kant med hver af de
andre. Det er nok hurtigere og nemmere at regne på vinklerne mellem
vektorerne: Summen af vinklerne mellem vektorerne skal være 360 grader
(eller 2pi), og de skal allesammen have samme fortegn (ellers er
figuren ikke konveks). Til forskel for den tidligere beskrevne
metode, er det ikken nok at se på fortegnet af prikproduktet, man skal
også beregne selve vinklen. Det er noget dyrere, da man skal dele
prikproduktet med længderne af vektorerne og derefter tage invers
cosinus.

   Torben

---

"Torben Ægidius Mogensen" wrote:
>
> Det kræver kvadratisk tid at sammenligne hver kant med hver af de
> andre. Det er nok hurtigere og nemmere at regne på vinklerne mellem
> vektorerne: Summen af vinklerne mellem vektorerne skal være 360 grader
> (eller 2pi), og de skal allesammen have samme fortegn (ellers er
> figuren ikke konveks). Til forskel for den tidligere beskrevne
> metode, er det ikken nok at se på fortegnet af prikproduktet, man skal
> også beregne selve vinklen. Det er noget dyrere, da man skal dele
> prikproduktet med længderne af vektorerne og derefter tage invers
> cosinus.

Prikproduktet og længderne kan jo ikke »se« om den orienterede vinkel
er +v eller -v. I det hele taget giver orienteret vinkel vel kun mening
hvis man befinder sig i en på forhånd fastlagt plan med valgt orien-
tering?

Hvis vi er i R², kan man vel bare udregne determinanten for parret af
vektorer og tjekke dens fortegn?

Invers cosinus eller andre arcusfunktioner bør da ikke komme på tale?

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Jeppe Stig Nielsen <mail@jeppesn.dk> writes:

> "Torben Ægidius Mogensen" wrote:
> >
> > Det kræver kvadratisk tid at sammenligne hver kant med hver af de
> > andre. Det er nok hurtigere og nemmere at regne på vinklerne mellem
> > vektorerne: Summen af vinklerne mellem vektorerne skal være 360 grader
> > (eller 2pi), og de skal allesammen have samme fortegn (ellers er
> > figuren ikke konveks). Til forskel for den tidligere beskrevne
> > metode, er det ikken nok at se på fortegnet af prikproduktet, man skal
> > også beregne selve vinklen. Det er noget dyrere, da man skal dele
> > prikproduktet med længderne af vektorerne og derefter tage invers
> > cosinus.
>
> Prikproduktet og længderne kan jo ikke »se« om den orienterede vinkel
> er +v eller -v.

Du har ret. Hertil skal man bruge determinanten eller krydsproduktet.

> I det hele taget giver orienteret vinkel vel kun mening
> hvis man befinder sig i en på forhånd fastlagt plan med valgt orien-
> tering?

Det gør man vel som regel også, når man snakker om plane polygoner?

> Hvis vi er i R², kan man vel bare udregne determinanten for parret af
> vektorer og tjekke dens fortegn?

Check.

> Invers cosinus eller andre arcusfunktioner bør da ikke komme på tale?

Hvsi man vil udregne vinkelsummen for at se om man kommer mere end en
gang rundt (f.eks. for at se forskel på en femkant of en femtakket
stjerne), så skal man vel?

   Torben

---

Torben Ægidius Mogensen wrote:
> Jeppe Stig Nielsen <mail@jeppesn.dk> writes:
>>Invers cosinus eller andre arcusfunktioner bør da ikke komme på tale?
>
> Hvsi man vil udregne vinkelsummen for at se om man kommer mere end en
> gang rundt (f.eks. for at se forskel på en femkant of en femtakket
> stjerne), så skal man vel?

Ikke nødvendigvis, for man kunne -- i stedet for at beregne selve den
akkumulerede vinkel -- bruge additionsformler til at holde rede på
cosinus og sinus til den akkumulerede vinkel.

Dvs. for hvert par af nabokanter (v, w) opdatere cosinus (c) og sinus
(s) til den løbende vinkel:
c' := c (v·w)/|v||w| - s |v×w|/|v||w|
s' := c |v×w|/|v||w| + s (v·w)/|v||w|

Dette gør det selvfølgelig sværere at skelne mellem, om den totale
akkumulerede vinkel bliver ±2pi eller ±4pi eller ±6pi eller..., fordi
sinus og cosinus ikke "tæller omgange". Men. Vi ved på forhånd, at de
enkelte vinkler har samme fortegn og ligger mellem 0 og ±pi (for det har
vi allerede tjekket ved at se på fortegn af determinanter). Derfor må
den totale vinkelsum være ±2pi, hvis og kun hvis cosinus til den
akkumulerede vinkel skifter fortegn netop to gange (nemlig fra plus til
minus til plus).

Det er nok sværere at slippe af med de "dyre" kvadratrødder, når
vektornorm skal beregnes.

--
Jonas Møller Larsen

---

"Torben Ægidius Mogensen" wrote:
>
> > Invers cosinus eller andre arcusfunktioner bør da ikke komme på tale?
>
> Hvsi man vil udregne vinkelsummen for at se om man kommer mere end en
> gang rundt (f.eks. for at se forskel på en femkant of en femtakket
> stjerne), så skal man vel?

Det kan der være noget om. Jeg havde vist (implicit) antaget at den
polygon man skulle tjekke, med sikkerhed var en simpel polygon, altså
en stykkevis retlinjet Jordan-kurve.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)