Un algoritmo para inflar/desinflar (compensar, amortiguar) polígonos
¿Cómo "inflaría" un polígono? Es decir, quiero hacer algo similar a esto:
El requisito es que los bordes/puntos del nuevo polígono (inflado) estén todos a la misma distancia constante de los del polígono antiguo (original) (en la imagen de ejemplo no lo están, ya que entonces tendría que usar arcos para los vértices inflados, pero olvídate de eso por ahora ;) ).
El término matemático para lo que estoy buscando es en realidad desplazamiento de polígono hacia adentro/hacia afuera . +1 a balint por señalar esto. El nombre alternativo es almacenamiento en búfer poligonal .
Resultados de mi búsqueda:
Aquí hay algunos enlaces:
- Un estudio de las estrategias de compensación de polígonos
- Desplazamiento de polígono, PROBLEMA
- Almacenamiento en búfer de datos de polígonos
Agosto de 2022:
Clipper2 se lanzó formalmente y reemplaza a Clipper (también conocido como Clipper1).
Pensé que podría mencionar brevemente mi propia biblioteca de compensación y recorte de polígonos : Clipper .
Si bien Clipper está diseñado principalmente para operaciones de recorte de polígonos, también realiza desplazamientos de polígonos. La biblioteca es un software gratuito de código abierto escrito en Delphi, C++ y C# . Tiene una licencia Boost sin trabas que permite su uso tanto en aplicaciones gratuitas como comerciales sin cargo.
El desplazamiento de polígonos se puede realizar utilizando uno de los cuatro estilos (o tipos de unión ): inglete, cuadrado, biselado y redondo.
Nota: En JoinType.Miter, el ángulo interno en el vértice A es más agudo que el de B y el desplazamiento en inglete en A excedería el límite de inglete especificado de 2.
El polígono que está buscando se llama polígono desplazado 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 de otro polígono:
Como se señaló en otros comentarios, además, 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, debería poder construir los polígonos desplazados con relativa facilidad. La biblioteca CGAL de código abierto y (gratuita para no comerciales) tiene un paquete que implementa estas estructuras. Vea este ejemplo de código para calcular polígonos desplazados usando CGAL.
El manual del paquete debería brindarle un buen punto de partida sobre cómo construir estas estructuras incluso si no va a utilizar CGAL, y contiene referencias a los artículos con definiciones y propiedades matemáticas:
Manual de CGAL: Desplazamiento de polígonos y esqueletos rectos 2D
Para este tipo de cosas suelo utilizar JTS . Para fines de demostración, creé este jsFiddle que usa JSTS (puerto JavaScript de JTS). Sólo necesitas convertir las coordenadas que tienes a 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:
Información adicional : suelo utilizar este tipo de inflado/desinflado (un poco modificado para mis propósitos) para establecer límites con radio en polígonos que se dibujan en un mapa (con Leaflet o Google Maps). Simplemente convierte pares (lat, lng) a coordenadas JSTS y todo lo demás sigue igual. Ejemplo:
Me parece que lo que quieres es:
- Comenzando en un vértice, mire en el sentido contrario a las agujas del reloj a lo largo de un borde adyacente.
- Reemplace el borde con un borde nuevo y paralelo colocado a una distancia
da la "izquierda" del anterior. - Repita para todos los bordes.
- Encuentra las intersecciones de las nuevas aristas 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 antiguos. No estoy seguro de si existe una mejor manera de detectar esto que simplemente comparar cada par de aristas 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 polígono antiguo "lo suficientemente lejos" de los vértices. Cerca de un vértice, el conjunto de puntos a distancia ddel polígono antiguo no es, como usted dice, un polígono, por lo que no se puede cumplir el requisito establecido.
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.
En el mundo SIG se utiliza 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 para desarrolladores: http://www.vividsolutions.com/jts/bin/JTS%20Developer%20Guide.pdf
