Espansione riempimento poligono convesso

Question

Ho un poligono convesso P1 di N punti. Questo poligono potrebbe essere di qualsiasi forma o proporzione (purché sia ​​ancora convesso).

Ho bisogno di calcolare un altro poligono P2 usando la geometria dei poligoni originali, ma "espanso" di un dato numero di unità. Quale potrebbe essere l'algoritmo per espandere un poligono convesso?

Answer 1

Per espandere un poligono convesso, tracciare una linea parallela ad ogni bordo e il dato numero di unità di distanza. Quindi utilizzare i punti di intersezione delle nuove linee come i vertici del poligono espanso. Javascript/tela alla fine segue questa ripartizione funzionale:

Fase 1: Figura quale lato è "fuori"

l'ordine dei vertici (punti) questioni. In un poligono convesso, possono essere elencati in ordine orario (CW) o senso antiorario (CCW). In un poligono CW, ruotare uno dei bordi di 90 gradi CCW per ottenere una normale rivolta verso l'esterno. Su un poligono CCW, trasformalo in CW.

Se la direzione della svolta dei vertici non è noto in anticipo, esamineremo come il secondo bordo risulta dal primo.In un poligono convesso, i bordi rimanenti continuare a ruotare nella stessa direzione:

1. Find the CW normal of the first edge. Non sappiamo ancora se sia rivolto verso l'interno o l'esterno.

2. Calcolare lo dot product del secondo bordo con il normale che abbiamo calcolato. Se il secondo spigolo diventa CW, il prodotto con punti sarà positivo. Sarà negativo altrimenti.

Math:

// in vector terms: 
v01 = p1 - p0      // first edge, as a vector 
v12 = p2 - p1      // second edge, as a vector 
n01 = (v01.y, -v01.x)    // CW normal of first edge 
d = v12 * n01      // dot product 

// and in x,y terms: 
v01 = (p1.x-p0.x, p1.y-p0.y)  // first edge, as a vector 
v12 = (p2.x-p1.x, p2.y-p1.y)  // second edge, as a vector 
n01 = (v01.y, -v01.x)    // CW normal of first edge 
d = v12.x * n01.x + v12.y * n01.y; // dot product: v12 * n01 

if (d > 0) { 
    // the polygon is CW 
} else { 
    // the polygon is CCW 
} 

// and what if d==0 ? 
// -- that means the second edge continues in the same 
// direction as a first. keep looking for an edge that 
// actually turns either CW or CCW. 

Codice:

function vecDot(v1, v2) { 
    return v1.x * v2.x + v1.y * v2.y; 
} 

function vecRot90CW(v) { 
    return { x: v.y, y: -v.x }; 
} 

function vecRot90CCW(v) { 
    return { x: -v.y, y: v.x }; 
} 

function polyIsCw(p) { 
    return vecDot(
     vecRot90CW({ x: p[1].x - p[0].x, y: p[1].y - p[0].y }), 
     { x: p[2].x - p[1].x, y: p[2].y - p[1].y }) >= 0; 
} 

var rot = polyIsCw(p) ? vecRot90CCW : vecRot90CW; 

Fase 2: Trova le linee parallele al poligono bordi

Ora che sappiamo quale lato è fuori, possiamo calcolare linee parallele a ciascun bordo di poligono, esattamente alla distanza richiesta. Ecco la nostra strategia:

1. Per ogni bordo, calcolare la sua rivolta verso l'esterno normale

2. Normalize del normale, in modo tale che la sua lunghezza diventa un'unità

3. Moltiplicare il normale dalla distanza che vogliamo il poligono espanso deve provenire dall'originale

4. Aggiungere la normale moltiplicata a entrambe le estremità del bordo. Questo ci darà due punti sulla linea parallela. Questi due punti sono sufficienti per definire la linea parallela.

Codice:

// given two vertices pt0 and pt1, a desired distance, and a function rot() 
// that turns a vector 90 degrees outward: 

function vecUnit(v) { 
    var len = Math.sqrt(v.x * v.x + v.y * v.y); 
    return { x: v.x/len, y: v.y/len }; 
} 

function vecMul(v, s) { 
    return { x: v.x * s, y: v.y * s }; 
} 

var v01 = { x: pt1.x - pt0.x, y: pt1.y - pt0.y }; // edge vector 
var d01 = vecMul(vecUnit(rot(v01)), distance);  // multiplied unit normal 
var ptx0 = { x: pt0.x + d01.x, y: pt0.y + d01.y }; // two points on the 
var ptx1 = { x: pt1.x + d01.x, y: pt1.y + d01.y }; //  parallel line 

Fase 3: Calcolare intersezioni delle linee parallele

--these saranno i vertici del poligono espanso.

Math:

Una linea passa attraverso due punti P1, P2 può essere descritto come:

P = P1 + t * (P2 - P1) 

due linee possono essere descritti come

P = P1 + t * (P2 - P1) 
P = P3 + u * (P4 - P3) 

E loro intersezione deve essere su entrambe le linee:

P = P1 + t * (P2 - P1) = P3 + u * (P4 - P3) 

Questo può essere massaggiato per assomigliare:

(P2 - P1) * t + (P3 - P4) * u = P3 - P1 

Che in x, termini y è:

(P2.x - P1.x) * t + (P3.x - P4.x) * u = P3.x - P1.x 
(P2.y - P1.y) * t + (P3.y - P4.y) * u = P3.y - P1.y 

Come i punti P1, P2, P3 e P4 sono noti, così sono i seguenti valori:

a1 = P2.x - P1.x a2 = P2.y - P1.y 
b1 = P3.x - P4.x b2 = P3.y - P4.y 
c1 = P3.x - P1.x c2 = P3.y - P1.y 

Questo riduce le nostre equazioni a:

a1*t + b1*u = c1 
a2*t + b2*u = c2  

Risolvendo per t ci fa:

t = (b1*c2 - b2*c1)/(a2*b1 - a1*b2) 

Il che ci permette di trovare l'intersezione a P = P1 + t * (P2 - P1).

Codice:

function intersect(line1, line2) { 
    var a1 = line1[1].x - line1[0].x; 
    var b1 = line2[0].x - line2[1].x; 
    var c1 = line2[0].x - line1[0].x; 

    var a2 = line1[1].y - line1[0].y; 
    var b2 = line2[0].y - line2[1].y; 
    var c2 = line2[0].y - line1[0].y; 

    var t = (b1*c2 - b2*c1)/(a2*b1 - a1*b2); 

    return { 
     x: line1[0].x + t * (line1[1].x - line1[0].x), 
     y: line1[0].y + t * (line1[1].y - line1[0].y) 
    }; 
} 

Fase 4: affrontare i casi particolari

C'è un certo numero di casi particolari che meritano attenzione. Lasciato come esercizio al lettore ...

1. Quando c'è un angolo molto netta tra due bordi, il vertice espanso può essere molto lontano da quello originale. Potresti considerare di tagliare il bordo espanso se supera la soglia. Nel caso estremo, l'angolo è zero, il che suggerisce che il vertice espanso è all'infinito, causando una divisione per zero nell'aritmetica. Attento.

2. Quando i primi due bordi si trovano sulla stessa riga, non è possibile stabilire se si tratta di un poligono in senso orario o antiorario guardando solo loro. Guarda più bordi.

3. I poligoni non convessi sono molto più interessanti ... e non vengono affrontati qui.

campione completa di codice

Goccia questo in un browser di tela-capable. Ho usato Chrome 6 su Windows. Il triangolo e la sua versione espansa dovrebbero animare.

<html> 
    <head> 
      <style type="text/css"> 
       canvas { border: 1px solid #ccc; } 
      </style> 
      <script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js"></script> 
      <script type="text/javascript"> 
       $(function() { 
        var canvas = document.getElementById('canvas'); 
        if (canvas.getContext) { 
         var context = canvas.getContext('2d'); 

         // math for expanding a polygon 

         function vecUnit(v) { 
          var len = Math.sqrt(v.x * v.x + v.y * v.y); 
          return { x: v.x/len, y: v.y/len }; 
         } 

         function vecMul(v, s) { 
          return { x: v.x * s, y: v.y * s }; 
         } 

         function vecDot(v1, v2) { 
          return v1.x * v2.x + v1.y * v2.y; 
         } 

         function vecRot90CW(v) { 
          return { x: v.y, y: -v.x }; 
         } 

         function vecRot90CCW(v) { 
          return { x: -v.y, y: v.x }; 
         } 

         function intersect(line1, line2) { 
          var a1 = line1[1].x - line1[0].x; 
          var b1 = line2[0].x - line2[1].x; 
          var c1 = line2[0].x - line1[0].x; 

          var a2 = line1[1].y - line1[0].y; 
          var b2 = line2[0].y - line2[1].y; 
          var c2 = line2[0].y - line1[0].y; 

          var t = (b1*c2 - b2*c1)/(a2*b1 - a1*b2); 

          return { 
           x: line1[0].x + t * (line1[1].x - line1[0].x), 
           y: line1[0].y + t * (line1[1].y - line1[0].y) 
          }; 
         } 

         function polyIsCw(p) { 
          return vecDot(
           vecRot90CW({ x: p[1].x - p[0].x, y: p[1].y - p[0].y }), 
           { x: p[2].x - p[1].x, y: p[2].y - p[1].y }) >= 0; 
         } 

         function expandPoly(p, distance) { 
          var expanded = []; 
          var rot = polyIsCw(p) ? vecRot90CCW : vecRot90CW; 

          for (var i = 0; i < p.length; ++i) { 

           // get this point (pt1), the point before it 
           // (pt0) and the point that follows it (pt2) 
           var pt0 = p[(i > 0) ? i - 1 : p.length - 1]; 
           var pt1 = p[i]; 
           var pt2 = p[(i < p.length - 1) ? i + 1 : 0]; 

           // find the line vectors of the lines going 
           // into the current point 
           var v01 = { x: pt1.x - pt0.x, y: pt1.y - pt0.y }; 
           var v12 = { x: pt2.x - pt1.x, y: pt2.y - pt1.y }; 

           // find the normals of the two lines, multiplied 
           // to the distance that polygon should inflate 
           var d01 = vecMul(vecUnit(rot(v01)), distance); 
           var d12 = vecMul(vecUnit(rot(v12)), distance); 

           // use the normals to find two points on the 
           // lines parallel to the polygon lines 
           var ptx0 = { x: pt0.x + d01.x, y: pt0.y + d01.y }; 
           var ptx10 = { x: pt1.x + d01.x, y: pt1.y + d01.y }; 
           var ptx12 = { x: pt1.x + d12.x, y: pt1.y + d12.y }; 
           var ptx2 = { x: pt2.x + d12.x, y: pt2.y + d12.y }; 

           // find the intersection of the two lines, and 
           // add it to the expanded polygon 
           expanded.push(intersect([ptx0, ptx10], [ptx12, ptx2])); 
          } 
          return expanded; 
         } 

         // drawing and animating a sample polygon on a canvas 

         function drawPoly(p) { 
          context.beginPath(); 
          context.moveTo(p[0].x, p[0].y); 
          for (var i = 0; i < p.length; ++i) { 
           context.lineTo(p[i].x, p[i].y); 
          } 
          context.closePath(); 
          context.fill(); 
          context.stroke(); 
         } 

         function drawPolyWithMargin(p, margin) { 
          context.fillStyle = "rgb(255,255,255)"; 
          context.strokeStyle = "rgb(200,150,150)"; 
          drawPoly(expandPoly(p, margin)); 

          context.fillStyle = "rgb(150,100,100)"; 
          context.strokeStyle = "rgb(200,150,150)"; 
          drawPoly(p); 
         } 

         var p = [{ x: 100, y: 100 }, { x: 200, y: 120 }, { x: 80, y: 200 }]; 
         setInterval(function() { 
          for (var i in p) { 
           var pt = p[i]; 
           if (pt.vx === undefined) { 
            pt.vx = 5 * (Math.random() - 0.5); 
            pt.vy = 5 * (Math.random() - 0.5); 
           } 

           pt.x += pt.vx; 
           pt.y += pt.vy; 

           if (pt.x < 0 || pt.x > 400) { pt.vx = -pt.vx; } 
           if (pt.y < 0 || pt.y > 400) { pt.vy = -pt.vy; } 
          } 
          context.clearRect(0, 0, 800, 400); 
          drawPolyWithMargin(p, 10); 
         }, 50); 
        } 
       }); 
      </script> 
    </head> 
    <body> 
     <canvas id="canvas" width="400" height="400"></canvas> 
    </body> 
</html> 

disclaimer codice di esempio:

• il campione sacrifica efficienza per motivi di chiarezza. Nel codice, è possibile calcolare il parallelo espanso di ogni spigolo solo una volta e non due volte come qui

• la coordinata y della tela cresce verso il basso, invertendo la logica CW/CCW. Le cose continuano a funzionare anche se abbiamo solo bisogno di trasformare le normali verso l'esterno in una direzione opposta a quella del poligono - ed entrambe vengono capovolte.

Answer 2

Lascia che i punti del poligono siano A1, B1, C1 ... Ora hai linee da A1 a B1, quindi da B1 a C1 ... Vogliamo calcolare i punti A2, B2, C2 del poligono P2 .

Se si disattiva l'angolo, ad esempio A1 B1 C1, si avrà una linea che va nella direzione desiderata. Ora puoi trovare un punto B2 su di esso che è la distanza appropriata da B1 sulla bisettrice. Ripetere l'operazione per tutti i punti del poligono P1.

Answer 3

Se il poligono è centrato sull'origine, basta moltiplicare ciascuno dei punti per un fattore di scala comune.

Se il poligono non è centrato sull'origine, quindi prima tradurre in modo che il centro si trovi sull'origine, ridimensiona e quindi lo traduca dove era.

Dopo il tuo commento

Sembra che si desidera tutti i punti da spostare alla stessa distanza dall'origine. Puoi farlo per ogni punto ottenendo il vettore normalizzato a questo punto. moltiplicando questo valore con la 'costante di espansione' e aggiungendo il vettore risultante sul punto originale.

n.b. Dovrai comunque tradurre-modify-translate se il centro non è anche l'origine di questa soluzione.

Answer 4

Per ciascun segmento di linea dell'originale, individuare il punto medio m e (lunghezza unitaria) normale ue del segmento. Il segmento corrispondente del poligono espanso si troverà quindi sulla linea attraverso m + n * u (dove si desidera espandere l'originale di n) con il normale u. Per trovare i vertici del poligono espanso devi quindi trovare l'intersezione di coppie di linee successive.

Answer 5

Guarda scheletri dritti. Come è stato implicato qui, ci sono una serie di problemi spinosi con i poligoni non convessi che sei stato risparmiato!