Un algoritmo para inflar / desinflar (compensar, amortiguar) polígonos

202

¿Cómo "inflaría" un polígono? Es decir, quiero hacer algo similar a esto:

texto alternativo

El requisito es que los bordes / puntos del nuevo polígono (inflado) estén a la misma distancia constante de los polígonos (originales) antiguos (en la imagen de ejemplo no lo son, ya que entonces tendría que usar arcos para vértices inflados, pero vamos a olvídate de eso por ahora;)).

El término matemático para lo que estoy buscando es en realidad offseting de polígono interno / externo . +1 a balint por señalar esto. La denominación alternativa es el almacenamiento en búfer de polígonos .

Resultados de mi búsqueda:

Aquí hay algunos enlaces:

Igor Brejc
fuente
17
Esta no es una pregunta trivial: si la deflación / inflación es pequeña, no sucede nada grave, pero en algún momento, los vértices desaparecerán. Probablemente esto se haya hecho antes, así que diría: use el algoritmo de otra persona, no construya el suyo.
Martijn
1
De hecho, si su polígono es cóncavo para comenzar (como en el ejemplo anterior), debe decidir qué debe suceder en el punto donde el algoritmo ingenuo quiere hacer un 'polígono' que se intersecte a sí mismo ...
AakashM
Sí, el principal problema son las partes cóncavas del polígono, aquí es donde radica la complejidad. Todavía creo que no debería ser un problema calcular cuándo se debe eliminar un cierto vértice. La pregunta principal es qué tipo de complejidad asintótica requeriría esto.
Igor Brejc
Hola, este también es mi problema, excepto que necesito hacer esto en 3D. ¿Existe una alternativa al enfoque de esqueletos rectos de poliedros tridimensionales descrito en el documento arxiv.org/pdf/0805.0022.pdf ?
stephanmg

Respuestas:

138

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

Si bien Clipper está diseñado principalmente para operaciones de recorte de polígonos, también compensa el polígono. La biblioteca es un software gratuito de código abierto escrito en Delphi, C ++ y C # . Tiene una licencia de Boost muy libre de gravámenes que le permite ser utilizado en aplicaciones gratuitas y comerciales sin cargo.

La compensación de polígonos se puede realizar utilizando uno de los tres estilos de compensación: cuadrado, redondo y a inglete.

Estilos de compensación de polígonos

Angus Johnson
fuente
2
¡Muy genial! ¿Dónde estabas hace 2 años? :) Al final tuve que implementar mi propia lógica de compensación (y perdí mucho tiempo). ¿Qué algoritmo estás usando para la compensación de polígonos, por cierto? Usé fuego de hierba. ¿Manejas agujeros en polígonos?
Igor Brejc
2
Hace 2 años estaba buscando una solución decente para el recorte de polígonos que no estuviese gravada con problemas difíciles de licencia :). La compensación de bordes se logra generando unidades normales para todos los bordes. Mi podadora de polígonos ordena las uniones de bordes, ya que las orientaciones de estas intersecciones superpuestas son opuestas a la orientación de los polígonos. Los agujeros se manejan con toda seguridad, al igual que los polígonos que se cruzan entre sí, etc. No hay restricciones para su tipo o número. Vea también "Compensación de polígono calculando
Angus Johnson el
Whoa! ¡No pienses por un segundo que esta pregunta está "olvidada"! Miré aquí la semana pasada, ¡no esperaba volver a esto! ¡Gracias un montón!
Chris Burt-Brown el
Los documentos de Clipper sobre el almacenamiento en búfer poli están aquí: angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/…
Drew Noakes
55
Para cualquiera que quiera hacer esto, otra alternativa es usar GEOS, y si usa Python, el envoltorio de GEOS, Shapely. Un ejemplo realmente bonito: toblerity.github.com/shapely/manual.html#object.buffer
pelson
40

El polígono que está buscando se llama polígono de desplazamiento hacia adentro / hacia afuera en geometría computacional y está estrechamente relacionado con el esqueleto recto .

Estos son varios polígonos desplazados para un polígono complicado:

Y este es el esqueleto recto para otro polígono:

Como se señaló en otros comentarios, también, dependiendo de qué tan lejos planee "inflar / desinflar" su polígono, puede terminar con una conectividad diferente para la salida.

Desde el punto de vista del cálculo: una vez que tenga el esqueleto recto, uno debería poder construir los polígonos de desplazamiento con relativa facilidad. La biblioteca CGAL de código abierto y (gratuita para no comerciales) tiene un paquete que implementa estas estructuras. Ver este ejemplo de código para calcular polígonos de compensación usando CGAL.

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

Manual CGAL: esqueleto recto 2D y compensación de polígono

balint.miklos
fuente
12

Para este tipo de cosas, generalmente uso JTS . Para fines de demostración, creé este jsFiddle que usa JSTS (puerto JavaScript de JTS). Solo necesita convertir las coordenadas que tiene en coordenadas 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:

ingrese la descripción de la imagen aquí

Información adicional : generalmente uso este tipo de inflado / desinflado (un poco modificado para mis propósitos) para establecer límites con radio en los polígonos que se dibujan en un mapa (con folletos o mapas de Google). Simplemente convierte pares (lat, lng) a coordenadas JSTS y todo lo demás es igual. Ejemplo:

ingrese la descripción de la imagen aquí

Marko Letic
fuente
9

Me parece que lo que quieres es:

  • Comenzando en un vértice, mire hacia la izquierda a lo largo de un borde adyacente.
  • Reemplace el borde con un nuevo borde paralelo colocado a una distancia da la "izquierda" del anterior.
  • Repita para todos los bordes.
  • Encuentra las intersecciones de los nuevos bordes para obtener los nuevos vértices.
  • Detecta si te has convertido en un polígono cruzado y decide qué hacer al respecto. Probablemente agregue un nuevo vértice en el punto de cruce y elimine algunos viejos. No estoy seguro de si hay una mejor manera de detectar esto que simplemente comparar cada par de bordes no adyacentes para ver si su intersección se encuentra entre ambos pares de vértices.

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

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

Steve Jessop
fuente
6

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

La biblioteca JTS debería hacer esto por usted. Consulte la documentación para la operación del búfer: http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/operation/buffer/package-summary.html

Para obtener una descripción general, consulte también la Guía del desarrollador: http://www.vividsolutions.com/jts/bin/JTS%20Developer%20Guide.pdf

Stryeko
fuente
5

Cada línea debe dividir el plano a "dentro" y "contorno"; Puede averiguarlo utilizando el método habitual de producto interno.

Mueva todas las líneas hacia afuera por cierta distancia.

Considere todos los pares de líneas vecinas (líneas, no segmentos de línea), encuentre la intersección. Estos son el nuevo vértice.

Limpie el nuevo vértice eliminando las partes que se cruzan. - tenemos algunos casos aquí

(a) Caso 1:

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

si lo gastas por uno, obtienes esto:

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

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

(b) caso 2

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

si lo gastas por dos, obtienes esto:

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

Para resolver esto, para cada segmento de línea, debe verificar si se superpone con los últimos segmentos.

(c) caso 3

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

gasto por 1. este es un caso más general para el caso 1.

(d) caso 4

igual que en el caso 3, pero gasto por dos.

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

Para hacer el caso 4, mantienes una pila de vértices ... empujas cuando encuentras líneas superpuestas con la última línea, revísala cuando obtienes la última línea. - Al igual que lo que haces en el casco convexo.

J-16 SDiZ
fuente
¿Conoces algún algoritmo psedo para esto?
EmptyData
5

Aquí hay una solución alternativa, mira si te gusta más.

  1. Haga una triangulación , no tiene que ser delaunay, cualquier triangulación funcionaría.

  2. Infle cada triángulo; esto debería ser trivial. Si almacena el triángulo en el orden antihorario, simplemente mueva las líneas hacia el lado derecho y haga la intersección.

  3. Fusionarlos usando un algoritmo de recorte Weiler-Atherton modificado

J-16 SDiZ
fuente
¿Cómo infla los triángulos exactamente? ¿Su producción depende de la triangulación? Con este enfoque, ¿puede manejar el caso cuando reduce el polígono?
balint.miklos
¿Estás seguro de que este enfoque realmente funciona para la inflación de polígonos? Qué sucede cuando las partes cóncavas del polígono se inflan de tal manera que algunos vértices deben eliminarse. La cosa es: cuando miras lo que sucede con los triángulos después de poli. inflación, los triángulos no están inflados, sino que están distorsionados.
Igor Brejc
1
Igor: el algoritmo de recorte de Weiler-Atherton puede manejar el caso "algunos vértices deben ser eliminados" correctamente;
J-16 SDiZ
@balint: inflar un triángulo es trivial: si almacena el vertrex en orden normal, el lado derecho siempre está "hacia afuera". Simplemente trate esos segmentos de línea como líneas, muévalas hacia afuera y encuentre la interacción: son el nuevo vértice. Para la triangulación en sí, pensándolo bien, la triangulación delaunay puede dar un mejor resultado.
J-16 SDiZ
44
Creo que este enfoque puede dar malos resultados fácilmente. Incluso para un ejemplo simple como quad triangulado usando una diagonal. Para los dos triángulos agrandados que obtienes: img200.imageshack.us/img200/2640/counterm.png y su unión no es lo que estás buscando. No veo cómo este método es útil.
balint.miklos
3

Muchas gracias a Angus Johnson por su biblioteca de podadoras. Hay buenos ejemplos de código para hacer el recorte en la página de inicio de Clipper en http://www.angusj.com/delphi/clipper.php#code pero no vi un ejemplo para la compensación de polígonos. Entonces pensé que tal vez sea útil para alguien si publico 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;
    }
Dolor Elemental
fuente
2

Una opción más es utilizar boost :: polygon : falta algo de documentación, pero debería encontrar los métodos resizey bloat, también, el +=operador sobrecargado , que realmente implementa el almacenamiento en búfer. Entonces, por ejemplo, aumentar el tamaño de un polígono (o un conjunto de polígonos) en algún valor puede ser tan simple como:

poly += 2; // buffer polygon by 2
Paul R
fuente
No entiendo cómo se supone que debes hacer algo con boost :: polygon ya que solo admite coordenadas enteras. Digamos que tengo un polígono general (coordenadas de coma flotante) y quiero expandirlo, ¿qué haría?
David Doria el
@DavidDoria: depende de la resolución / precisión y el rango dinámico que necesita para sus coordenadas, pero puede usar un int de 32 o 64 bits con un factor de escala apropiado. Por cierto, he usado (accidentalmente) boost :: polygon con coordenadas flotantes en el pasado y parece funcionar bien, pero puede que no sea 100% robusto (¡los documentos lo advierten!).
Paul R
Estaría bien con "funcionará funcionará la mayor parte del tiempo" :). Intenté esto: ideone.com/XbZeBf pero no se compila, ¿alguna idea?
David Doria el
No veo nada obviamente malo, pero en mi caso estaba usando las especializaciones rectilíneas (polygon_90), así que no sé si eso hace la diferencia. Sin embargo, han pasado algunos años desde que jugué con esto.
Paul R
OK, ahora vuelvo a mí, solo se puede usar +=con un conjunto de polígonos , no con polígonos individuales. Pruébelo con un std :: vector de polígonos. (Por supuesto, el vector solo necesita contener un polígono).
Paul R
1

Según los consejos de @ JoshO'Brian, parece que el rGeospaquete en el Rlenguaje implementa este algoritmo. Ver rGeos::gBuffer.

Carl Witthoft
fuente
0

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

  1. https://github.com/otherlab/openmesh
  2. https://github.com/alecjacobson/nested_cages
  3. http://homepage.tudelft.nl/h05k3/Projects/MeshThickeningProj.htm

También se pueden encontrar las publicaciones correspondientes para estas bibliotecas para comprender los algoritmos con más detalle.

El último tiene la menor dependencia y es autónomo y puede leer en archivos .obj.

Mis mejores deseos, Stephan

stephanmg
fuente
0

Utilizo geometría simple: vectores y / o trigonometría

  1. En cada esquina, encuentre el vector medio y el ángulo medio. El vector medio es el promedio aritmético de los dos vectores unitarios definidos por los bordes de la esquina. El ángulo medio es la mitad del ángulo definido por los bordes.

  2. Si necesita expandir (o contraer) su polígono por la cantidad de d de cada borde; debe salir (dentro) por la cantidad d / sin (midAngle) para obtener el nuevo punto de esquina.

  3. Repita esto para todas las esquinas

*** Ten cuidado con tu dirección. Haga la prueba CounterClockWise usando los tres puntos que definen la esquina; para averiguar qué camino está afuera o adentro.

usuario2800464
fuente