Expandir relleno del polígono convexo

Question

Tengo un polígono convexo P1 de N puntos. Este polígono puede tener cualquier forma o proporción (siempre que sea convexo).

Necesito calcular otro polígono P2 usando la geometría original de los polígonos, pero "expandido" por un número dado de unidades. ¿Cuál podría ser el algoritmo para expandir un polígono convexo?

Answer 1

para expandir un polígono convexo, dibuja una línea paralela a cada borde y el número dado de unidades de distancia. Luego use los puntos de intersección de las nuevas líneas como los vértices del polígono expandido. El javascript/lona al final sigue este desglose funcional:

Paso 1: Averiguar qué lado está "fuera"

El orden de los vértices (puntos) que importa. En un polígono convexo, se pueden enumerar en sentido horario (CW) o en sentido antihorario (CCW). En un polígono CW, gire uno de los bordes 90 grados CCW para obtener una normal hacia afuera. En un polígono CCW, conviértalo CW en su lugar.

Si el sentido de giro de los vértices no se conoce de antemano, a examinar cómo el segundo borde de la primera gira.En un polígono convexo, los bordes restantes seguir girando en la misma dirección:

1. Find the CW normal of the first edge. Todavía no sabemos si está mirando hacia adentro o hacia afuera.

2. Calcule el dot product del segundo borde con la normalidad que calculamos. Si el segundo borde gira en CW, el producto escalar será positivo. Será negativo de lo contrario.

matemática:

// 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. 

Código:

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; 

Paso 2: encontrar líneas paralelas al polígono bordes

Ahora que sabemos qué lado está afuera, podemos calcular líneas paralelas a cada borde del polígono, exactamente a la distancia requerida. Aquí está nuestra estrategia:

1. Para cada borde, calcular su exterior que mira hacia la normalidad

2. Normalize la normal, de tal forma que su longitud se convierte en una unidad

3. Multiplicar la normalidad por la distancia que queremos el polígono expandido para ser del original

4. Agregue la normal multiplicada a ambos extremos del borde. Eso nos dará dos puntos en la línea paralela. Esos dos puntos son suficientes para definir la línea paralela.

Código:

// 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 

Paso 3: Calcular las intersecciones de las líneas paralelas

--Estas serán los vértices del polígono expandido.

matemática:

una línea que va a través de dos puntos P1, P2 se puede describir como:

P = P1 + t * (P2 - P1) 

Dos líneas pueden ser descritos como

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

Y su intersección tiene que ser en ambas líneas:

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

Esto se puede dar masajes a parecerse a:

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

Lo que en x, términos Y es:

(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 

Como los puntos P1, P2, P3 y P4 son conocidos, por lo que son los siguientes valores:

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 

Esto acorta nuestras ecuaciones para:

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

Despejando t nos obtiene:

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

que nos permite encontrar la intersección en P = P1 + t * (P2 - P1).

Código:

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) 
    }; 
} 

Paso 4: Hacer frente a casos especiales

Hay un número de casos especiales que merecen atención. Deja como ejercicio para el lector ...

1. Cuando hay un ángulo muy agudo entre dos bordes, el vértice expandido puede ser muy lejos de la original. Es posible que desee considerar recortar el borde expandido si supera el umbral. En el caso extremo, el ángulo es cero, lo que sugiere que el vértice expandido está en el infinito, causando la división por cero en la aritmética. Cuidado.

2. Cuando los primeros dos bordes están en la misma línea, no se puede decir si se trata de un polígono CW o CCW simplemente observándolos. Mira más bordes.

3. Los polígonos no convexos son mucho más interesantes ... y no se abordan aquí.

muestra completa código

gota esto en un navegador capaz de lona. Usé Chrome 6 en Windows. El triángulo y su versión expandida deberían animarse.

<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> 

renuncias código de ejemplo:

• los sacrificios de muestra cierta eficiencia en aras de la claridad. En su código, es posible que desee calcular el paralelo expandido de cada borde una sola vez, y no dos veces como aquí

• la coordenada y del lienzo crece hacia abajo, lo que invierte la lógica CW/CCW. Sin embargo, las cosas siguen funcionando ya que solo tenemos que girar las normales hacia afuera en una dirección opuesta a la del polígono, y ambas se voltean.

Answer 2

Deje que los puntos del polígono sean A1, B1, C1 ... Ahora tiene líneas de A1 a B1, luego de B1 a C1 ... Queremos calcular los puntos A2, B2, C2 del polígono P2 .

Si biseca el ángulo, por ejemplo A1 B1 C1, tendrá una línea que irá en la dirección que desee. Ahora puede encontrar un punto B2 que es la distancia apropiada desde B1 en la línea bisectriz. Repita esto para todos los puntos del polígono P1.

Answer 3

Si el polígono está centrado en el origen, simplemente multiplique cada uno de los puntos por un factor de escala común.

Si el polígono no está centrado en el origen, primero traduzca para que el centro esté en el origen, escale y luego vuélvalo a traducir a su lugar original.

Después de su comentario

Parece desea que todos los puntos sean movidos a la misma distancia desde el origen. Puede hacer esto para cada punto obteniendo el vector normalizado en este punto. multiplique esto por su 'constante de expansión' y agregue el vector resultante de nuevo en el punto original.

n.b. Aún tendrá que traducir, modificar, traducir si el centro no es también el origen de esta solución.

Answer 4

Para cada segmento de línea del original, encuentre el punto medio m y (longitud de la unidad) hacia afuera u normal del segmento. El segmento correspondiente del polígono expandido se ubicará en la línea a través de m + n * u (donde desea expandir el original en n) con u normal. Para encontrar los vértices del polígono expandido, necesita encontrar la intersección de pares de líneas sucesivas.

Answer 5

Mirar los esqueletos rectos. Como se ha implicado aquí, hay una serie de problemas complicados con polígonos no convexos que le han ahorrado muchísimo.