Un algoritmo para inflar/desinflar (compensación, el almacenamiento en búfer) polígonos

https://stackoverflow.com/questions/1109536

12-09-2019
|

Pregunta

Cómo iba yo a "inflar" un polígono?Es decir, yo quiero hacer algo parecido a esto:

alt text

El requisito es que el nuevo (inflado) polígono de bordes/puntos están todos a la misma distancia constante desde la edad (original) polígono (en la imagen de ejemplo no lo son, pues entonces tendría que usar arcos para inflado de los vértices, pero vamos a olvidarnos de que, por ahora ;) ).

El término matemático para lo que estoy buscando es realmente hacia el interior y exterior del polígono offseting.+1 a balint para señalar esto.La alternativa de nomenclatura es polígono de almacenamiento en búfer.

Los resultados de mi búsqueda:

Aquí hay algunos enlaces:

Solución

pensé que podría mencionar brevemente mi propia recorte de polígono y la compensación de la biblioteca - Clipper .

Clipper está diseñado principalmente para operaciones polígono de recorte, lo hace polígono compensando también. La biblioteca es software gratuito de código abierto escrito en Delphi, C ++ y C # . Tiene una Boost licencia que le permite ser utilizado tanto en aplicaciones freeware y comerciales sin cargo.

Polígono compensación puede realizarse utilizando uno de los tres estilos de compensación -. Cuadrado, redondo y inglete

Polígono compensación estilos

Otros consejos

El polígono que está buscando se llama hacia el interior y exterior de desplazamiento polígono en geometría computacional y está estrechamente relacionado con el recta esqueleto.

Estos son varios de desplazamiento polígonos para un complicado polígono:

Y esta es la escalera de esqueleto para otro polígono:

Como se ha señalado en otros comentarios, así, dependiendo de cuán lejos plan para "inflar/desinflar" polígono usted puede terminar para arriba con diferentes conectividad para la salida.

De cálculo de punto de vista:una vez que usted tiene la recta esqueleto de uno debe ser capaz de construir el desplazamiento de los polígonos con relativa facilidad.El código abierto y (gratuito para uso no comercial) CGAL la biblioteca tiene un paquete de implementación de estas estructuras.Ver este ejemplo de código para calcular el offset de polígonos utilizando CGAL.

El paquete de manual debe dar un buen punto de partida sobre cómo construir estas estructuras, incluso si usted no va a utilizar CGAL, y contiene referencias a los documentos con las definiciones matemáticas y propiedades:

CGAL manual:2D Recta Esqueleto y Polígono de Compensación

Me parece que lo que desea es:

Comenzando en un vértice, se enfrentan en sentido antihorario a lo largo de un borde adyacente.
Reemplazar el borde con un nuevo borde, paralelo situado en d distancia a la "izquierda" de la antigua.
Repita este procedimiento para todos los bordes.
Para las intersecciones de las nuevas aristas para obtener los nuevos vértices.
Detectar si te has convertido en un polígono cruzados y decidir qué hacer al respecto. Probablemente añadir un nuevo vértice en el punto de cruce y deshacerse de algunos de los antiguos. No estoy seguro de si hay una mejor manera de detectar esto que acaba de comparar cada par de bordes no adyacentes para ver si su intersección se encuentra entre los dos pares de vértices.

El polígono resultante se encuentra a la distancia requerida desde el antiguo polígono "suficientemente lejos" de los vértices. Cerca de un vértice, el conjunto de puntos en d distancia de la antigua polígono es, como usted dice, no es un polígono, por lo que el requisito como se ha dicho, no se puede cumplir.

No sé si este algoritmo tiene un nombre, código de ejemplo en la web, o una optimización diabólica, pero creo que describe lo que quiere.

Para estos tipos de cosas que suelen utilizar JTS . Para fines de demostración he creado este jsFiddle que los usos jSTS (puerto de JavaScript STC). Sólo se necesita para convertir las coordenadas que tienen que coordina JSTS:

function vectorCoordinates2JTS (polygon) {
  var coordinates = [];
  for (var i = 0; i < polygon.length; i++) {
    coordinates.push(new jsts.geom.Coordinate(polygon[i].x, polygon[i].y));
  }
  return coordinates;
}

El resultado es algo como esto:

Otros detalles : Yo suelo usar este tipo de inflar / desinflar (un poco modificado para mis propósitos) para el establecimiento de límites con el radio de polígonos que se dibujan en un mapa (con mapas folleto o Google) . Usted acaba de convertir (lat, lng) pares de coordenadas JSTS y todo lo demás es igual. Ejemplo:

Cada línea debe dividir el plano de "dentro" y "contorno"; usted puede encontrar esto utilizando el método interno subproducto habitual.

Mover todas las líneas hacia el exterior por una cierta distancia.

Tenga en cuenta todo par de líneas (líneas vecinas, y no de segmentos de línea), encontrar la intersección. Estos son el nuevo vértice.

Cleanup el nuevo vértice mediante la eliminación de las partes de intersección. - Tenemos algunos caso aquí

(a) Caso 1:

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

Si usted expende por uno, tienes esto:

0----a----3
|    |    |
|    |    |
|    b    |
|         |
|         |
1---------2

7 y 4 se superponen .. si usted ve esto, se quita este punto y todos los puntos intermedios.

(b) caso 2

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

Si usted expende por dos, tienes esto:

0----47----3
|    ||    |
|    ||    |
|    ||    |
|    56    |
|          |
|          |
|          |
1----------2

Para resolver esto, para cada segmento de línea, usted tiene que comprobar si se solapa con estos últimos segmentos.

       4--3
 0--X9 |  |
 |  78 |  |
 |  6--5  |
 |        |
 1--------2

gastar por 1. Este es un caso más general para el caso 1.

(d) caso 4

mismo que case3, pero gastar por dos.

En realidad, si usted puede manejar el caso 4. Todos los demás casos son solo caso especial de ella con alguna línea o vértice superposición.

Para el caso 4, se mantiene una pila de vértice .. se presiona cuando se observa que las líneas se superponen con esta última línea, el pop cuando llegue a la última línea. - Al igual que lo que haces en convexa-casco

Esta es una solución alternativa, a ver si te gusta este mejor.

triangulación , que no tiene por qué ser Delaunay -. triangulación haría cualquier
Inflar cada triángulo - esto debe ser trivial. si almacena el triángulo en el orden en sentido antihorario, basta con mover las líneas a mano del lado derecho y hacer intersección.
fusionarlos utilizando un algoritmo de recorte Weiler-Atherton modificado

En el mundo SIG uno utiliza el almacenamiento en búfer negativo para esta tarea: http://www-users.cs.umn.edu/~npramod/enc_pdf .pdf

El biblioteca JTS debe hacer esto para usted. Consulte la documentación de la operación de búfer: http: / /tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/operation/buffer/package-summary.html

Para obtener una visión general véase también la Guía del Desarrollador: http://www.vividsolutions.com/jts/bin/JTS%20Developer % 20Guide.pdf

Muchas gracias a Angus Johnson para su biblioteca podadoras. Hay buenos ejemplos de código para hacer las cosas de recortes en la página podadoras en http: // www .angusj.com / Delphi / clipper.php # código pero no vi un ejemplo para la compensación del polígono. Así que pensé que tal vez sea de utilidad para alguien, si he puesto mi código:

    public static List<Point> GetOffsetPolygon(List<Point> originalPath, double offset)
    {
        List<Point> resultOffsetPath = new List<Point>();

        List<ClipperLib.IntPoint> polygon = new List<ClipperLib.IntPoint>();
        foreach (var point in originalPath)
        {
            polygon.Add(new ClipperLib.IntPoint(point.X, point.Y));
        }

        ClipperLib.ClipperOffset co = new ClipperLib.ClipperOffset();
        co.AddPath(polygon, ClipperLib.JoinType.jtRound, ClipperLib.EndType.etClosedPolygon);

        List<List<ClipperLib.IntPoint>> solution = new List<List<ClipperLib.IntPoint>>();
        co.Execute(ref solution, offset);

        foreach (var offsetPath in solution)
        {
            foreach (var offsetPathPoint in offsetPath)
            {
                resultOffsetPath.Add(new Point(Convert.ToInt32(offsetPathPoint.X), Convert.ToInt32(offsetPathPoint.Y)));
            }
        }

        return resultOffsetPath;
    }

Una opción adicional es usar impulso :: polígono - la documentación es un poco deficiente, pero se debe constatar que los métodos y resize bloat, y también el operador += sobrecargada, que en realidad implementar el almacenamiento en búfer. Así, por ejemplo aumentando el tamaño de un polígono (o un conjunto de polígonos) por algún valor puede ser tan simple como:

poly += 2; // buffer polygon by 2

Con base en el consejo de @ JoshO'Brian, parece que el paquete de rGeos en el idioma R implementa este algoritmo. Ver rGeos::gBuffer.

Hay un par de bibliotecas se pueden usar (también utilizables para conjuntos de datos 3D).

También se puede encontrar publicaciones de estas bibliotecas correspondiente a entender los algoritmos con más detalle.

El último tiene el menor número de dependencias y es autónomo y puede leer en los archivos .obj.

Los mejores deseos, Stephan

utilizo geometría simple: Vectores y / o trigonometría

En cada esquina encontrará el vector medio y mediados ángulo. Mediados vector es la media aritmética de los dos vectores unitarios definidos por los bordes de la esquina. Mediados de ángulo es la mitad del ángulo definido por los bordes.
Si necesita ampliar (o contrato) el polígono por la cantidad de d de cada borde; usted debe salir (en) por la cantidad d / sen (midAngle) para obtener el nuevo punto de esquina.
Repita este procedimiento para todas las esquinas

*** Tenga cuidado con su dirección. Haga la prueba en sentido antihorario utilizando los tres puntos que definen la esquina; para averiguar en qué dirección está fuera o en.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow