Gitt en punktsverm uten noen bestemt rekkefølge. Vi ønsker å finne et polygon som omslutter svermen. Det vil si at polygonet, som vi kaller Hull, skal bestå av utvalgte punkter slik at når vi trekker linjer mellom alle punktene i Hull så skal ingen punkter i svermen falle utenfor. Hull vi være et konvekst polygon.

Vi kan starte med å slå fast at det er 4 punkter som helt sikkert skal være med i polygonet: Det lavest punktet (minst y-verdi), det øverste punktet(største y-verdi), punktet lengst til venstre(minst x-verdi) og punktet lengst til høyre( størst x-verdi). Vi velger et av disse og plasserer det i Hull. Jeg velger det laveste. Så vil jeg steg for steg, mot klokka, gå gjennom alle de andre punktene og finne det punktet som har minst vinkel.

Dette må jeg gjenta helt til jeg komme rundt til startpunktet, altså det laveste punktet.

Dataene våre er ordnet slik:

// en array med alle punktene i svermen
var Pts;
// en array med omgivende polygon
var Hull;
// et punkt
function Punkt(x,y){
  this.x=x; this.y=y;
}

function makeHull(){
  if(Pts.length < 3)
    return;
  n=Pts.length;
  Hull=new Array();
  // Finn det laveste punktet (altid med i Hull) 
  var lavest = 0; 
  for (var i = 1; i < n; i++) 
    if (Pts[i].y < Pts[lavest].y) 
      lavest = i; 
  // Start med det laveste punktet og gå mot klokka
  var p = lavest;    
  do
  { 
    // legg til et nytt punkt 
    Hull.push(Pts[p]); 		
    // finn det punktet, q, i svermen der linja p-q har minst vinkel
    // ****  dette er vårt uløste problem ****
    // Det beste vi fant
    p = q; 
  } while (p != lavest); 
  // helt til startpunktet er det beste vi fant 		
}

Vårt uløste problem kan enkelt illustreres slik:

Vi må finne ut om A eller B er det neste punktet, altså om vB eller vA er den minste vinkelen. Hvis vB er minst skal vi velge punktet B. Tilsynelatende trivielt, men vi må huske at de to vinklene kan ha verdier fra 0 til 360 grader. Vi kan bruke (inverse) trigonometriske funksjoner, justere for vilken kvadrat vi er i og regne ut vinkelen. Det er en del detaljer som skal passes på.

Jeg har valgt å lete på nettet etter en løsning på noe som burde være et kjent problem. Det viser seg at det er lansert flere løsninger som er enklere og ikke minst raskere.

En løsning er å lage en slags surrogat-vinkel som ikke er presis, men som har en kontinuerlig økning fra 0 til 360 grader.

En annen løsning er å betrakte trekanten PBA (eller PAB) og finne ut om rekkefølgen på punktene beskriver en vandring med eller mot klokka. Hvis vi f.eks. ser på PBA og finner ut at vi går mot klokka er B det punktet vi vil velge. Jeg går for den siste løsningen og introduserer funksjonen retning.

function retning(a,b,c){ 
  val = (b.y - a.y) * (c.x - b.x) - 
        (b.x - a.x) * (c.y - b.y); 

  if (val == 0) return 0; // ingen trekant
  if(val >0)return 1;	  // med klokka
  return 2;               // mot klokka 
}

function makeHull(){
  if(Pts.length < 3) return;
  n=Pts.length;
  Hull=new Array();
  // Finn det laveste punktet (altid med i hull) 
  var lavest = 0; 
  for (var i = 1; i < n; i++) 
    if (Pts[i].y < Pts[lavest].y) 
      lavest = i; 
  // Start med det laveste punktet og gå med mot klokka
  // Let alltid etter det punktet som har minst vinkel 
  var p = lavest; 
  do
  { 
    // legg til et nytt punkt 
    Hull.push(Pts[p]); 		
    // kandidat for nytt punkt er neste punkt
    var q = (p + 1) % n; 
    // noen bedre ?			
    for (var i = 0; i < n; i++) 
    { 
        // er det i eller q som er best, minst vinkel mot klokka
        if (retning(Pts[p], Pts[i], Pts[q]) == 2) 
            q = i; 
    } 
    // det beste vi fant i løkka 
    p = q;	
  } while (p != lavest); 
  // helt til startpunktet er vårt beste valg 		
}

Med denne koden får vi følgende løsning:

Vi ser litt nærmere på den siste funksjonen vi introduserte:

function retning(a,b,c){ 
  val = (b.y - a.y) * (c.x - b.x) - 
        (b.x - a.x) * (c.y - b.y); 

  if (val == 0) return 0; // ingen trekant
  if(val >0)return 1;	  // med klokka
  return 2;               // mot klokka 
}

Dette er en kortform for det som kalles et kryssprodukt mellom to vektorer. Dette er en metode som blandt annet brukes når vi programmerer 3D figurer og har behov for å finne normalen på et punkt på en flate. Her opererer vi i planet og normalen kan ha bare to retninger.

Du kan teste her. Hvis du flytter på sirklene vil trekanten bli gul dersom Rød-Grønn-Blå er rekkefølgen mot klokka.

Du finner mer om dette hvis du søker på nettet etter "kryssprodukt" eller "vektorprodukt".