===============================================================================
     Date: 07-24-95    Time: 01:34a     Number: 18     
     From: Bjorn-Tore Dale               Refer:         
       To: Morten Vold                Board ID: SKRIBENT        Reply: 
  Subject: "Derivering"?!??                173: Ice/Programm   Status: Public 
-------------------------------------------------------------------------------
 On 06-27-95 Morten Vold wrote to All...

 MV> Hei der!  Jeg lurte på om det er noen mattegenier her som kan hjelpe
 MV> meg med
 MV> noe jeg kanskje skal programmere. Han som skal ha det kaller det
 MV> 'derivering',
 MV> ikke vet jeg :)
 MV>
 MV> I allefall, dette er situasjonen;  Du har en polygon, og har x og
 MV> y-koordinatene til alle hjørnene i polygonen.  Så får du gitt et annet
 MV> punkt i
 MV> det samme koordinat-systemet, og skal regne ut om det er inni eller
 MV> utenfor
 MV> polygonen.
 MV>
 MV> Er det noen som har peiling?

Er litt sent ute med svar, men jeg har vært på ferie...

Har ikke programmert akkurat denne algoritmen, men jeg har vært borti en slik
situasjon i et kurs.  Jeg tror følgende metode er brukbar, vel og merke bare
for *konvekse* polygon. Et polygon er konvekst bare dersom alle vinklene er
mindre enn 180 grader.

Eksempelvis definerer følgende punkt P1..P4 et konvekst polygon:
   P2
  P1
 P3
P4

Dette er ikke konvekst:

   P2  P3

     P1 P5

   P4

Metode:

Pr. linje i polygonet sjekker en om punktet er over eller under denne. Hvis
punktet er over en av linjene som er på "oppsiden" av polygonet, vet vi helt
sikkert at punktet er utenfor polygonet. Tilsvarende, dersom punktet er under
en av linjene som er på "undersiden" av polygonet, vet vi helt sikkert at
punktet er utenfor polygonet. Dersom ikke dette kan vises for noen av linjene,
må punktet være innenfor polygonet.
Vertikale linjer må behandles spesielt.


1. Først må vi ha en metode for å finne ut om et punkt er
   over, på, eller under en gitt linje i polygonet.


   Likningen for en linje er:
        y = a*x + b

   La oss si at hver linje i polygonet er definert av punktet (x0,y0)
   og punktet (x1,y1).

   a er lik                     (antar ikke-vertikal linje)
        a = (y1-y0)/(x1-x0)

   Dette er stigningstallet for linjen, og er lik den deriverte
   av samme linjen.

   b er lik
        b = y0 - a*x0

   Likningen kan omskrives slik:
        a*x - y + b = 0

   Fra denne lager vi så en funksjon f(x,y) slik:
        f(x,y) = a*x - y + b

   Dersom punktet (x,y) ligger *på*    linjen er f(x,y) = 0.
   Dersom punktet (x,y) ligger *under* linjen er f(x,y) > 0.
   Dersom punktet (x,y) ligger *over*  linjen er f(x,y) < 0.


2. Sørg for å definere alle n punktene i polygonet slik
   at rekkefølgen punktene P1..Pn er gitt er *med* klokken.
   Eks. med n=5:

       P5 o       o   P1


P4 o   o  P2

               o P3

3. La oss si at punktet som vi skal sjekke om er inni eller
   utenfor polygonet er definert som (g,h).

   Da blir algoritmen noe slikt (ha meg unnskyldt miks norsk-engelsk!):

   (Laget som en funksjon som returnerer true dersom punktet
    er innenfor).


   int   i;
   float a,b,f;

   for i = 1 til n         (hvert punkt i polygonet)

     punkt (x0,y0) = P(i)      (fra-punkt)

     hvis ix0 så
             return (false)
             (punktet er over en linje som er på oversiden av polygonet)
       ellers hvis f > 0 så
          hvis x1y0 så
          hvis gx0 så
             return (false)
             (punktet er til høyre for linje som er på høyre
              side av polygonet)

   next i

   (punktet er innenfor siden vi ikke kan bevise det motsatte!)

   return (true)




Puh! Håper detta er rektig, da!!


_BT_


... OFFLINE 1.42

--- BBBS/2 v3.14.95 RämiWörk-6
 * Origin: Errors HQ: Programming & emulators, +47-56350198 (47:55/103)
===============================================================================