Arealet av et polygon

Vi tar utgangspunkt i følgende definisjon:
"En polygon eller en mangekant er en lukket kurve i planet, bestående av rette linjestykker. Kurven skjærer ikke seg selv."

Polygoner kan være konvekse
eller konkave

.

I resonnementet nedenfor antar vi at polygonet ligger i 1.kvadrant. Dette er ikke en begrensing på selve algoritmen. Vi kan, hvis nødvendig, parallellforskyve polygonet til 1. kvadrat før vi starter beregningen. Vi tar utgangspunkt at punktene som beskriver polygonet er lagret i følgende datastruktur:

// punktene
var Poly=new Array();
// et punkt
function Punkt(x,y){
	this.x=x;
	this.y=y;
};
/*vi legger punkter inn i Poly,systematisk og passer på 
at ingen linjer mellom punkter krysser hverandre.*/
Poly.push(new Punkt(12,6));
Poly.push(new Punkt(23,17));
// ... osv

Vi ender opp med et polygon som ikke nødvendigvis er en kjent geometrisk figur (rektangel, kvadrat, trekant, femkant e.l.). Vi må finne arealet kun basert på de hjørnene som er beskrevet i Poly. Et viktig poeng i resonnementet nedenfor er altså at ingen linjer skal krysse hverandre. Det innebærer at hjørnene i polygonet er ordnet slik at vi kan gå systematisk rundt polygonet ved å gå fra det ene punktet til det andre i den rekkefølgen de ligger i Poly.

Anta at pila på figuren angir retningen vi beveger oss i rundt polygonet. Dersom vi betrakter et slikt polygon ser vi at alle linjer har et rektangel og en trekant under seg.

Hvis vi summerer alle rektangler og trekanter under linjer som går mot venstre får vi et areal, A1, som er begrenset av den øvre delen av polygonet og x-aksen.

Dersom vi gjør det samme med de linjene som går mot høyre får vi et areal, A2, som er avgrenset av den nedre delen av polygonet og x-aksen. Arealet av polygonet bør da bli A1-A2.

Loddrette linjer vil ikke bidra i regnskapet.

Eksempel1 og eksempel2 innholder de samme punktene, men de er angitt i motsatt rekkefølge for å teste at arealet blir det samme.

Eksempel3 setter ytterpunktene i tegneområdet som punkter i polygonet, altså et rektangel.

Koden kan være slik:

function Area(Pol)
{
  // beregner arealet av et polygon, Pol 
  if(Pol.length < 3)
    return 0.0;
  // lukk polygonet
  Pol.push(new Punkt(Pol[0].x,Pol[0].y));
  var A=0;
  // adder eller trekk fra et rektangel og en trekant
  for(var pix=0; pix < Pol.length-1; pix++){
    // pluss eller minus avhenger av dx
    var dx=Pol[pix+1].x-Pol[pix].x;
    var dy=Math.abs(Pol[pix+1].y-Pol[pix].y);
    var miny=Math.min(Pol[pix+1].y,Pol[pix].y);
    // rektangelet
    A+=miny*dx;
    // trekanten
    A+=(dx*dy)/2;
  }
  // summen skal være positiv
  // vi viser det som prosent av tegneflaten(W*H)
  Areal=Math.abs(A*100.0/(W*H));
  // fjern lukke punktet
  Pol.pop();
  return Areal;
}