algorithm - check if two lines intersect
Un algoritmo para inflar/desinflar(compensación, almacenamiento en búfer) polígonos (12)
¿Cómo "inflaría" un polígono? Es decir, quiero hacer algo similar a esto:
El requisito es que los bordes / puntos del polígono nuevo (inflado) estén todos a la misma distancia constante de los polígonos antiguos (originales) (en la imagen de ejemplo que no son, ya que entonces tendría que usar arcos para los 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 compensación de polígono hacia adentro / hacia afuera . +1 a balint para 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:
Aquí hay una solución alternativa, mira si te gusta esto mejor.
Haz una triangulation , no tiene que ser delaunay, cualquier triangulación sería suficiente.
Infla cada triángulo, esto debería ser trivial. si almacena el triángulo en el sentido contrario a las agujas del reloj, simplemente mueva las líneas hacia el lado derecho y haga la intersección.
Combínalos usando un algoritmo de recorte Weiler-Atherton modificado
Cada línea debe dividir el plano en "interior" y "contorno"; Puedes averiguarlo usando el método usual de productos internos.
Mueva todas las líneas hacia afuera por alguna distancia.
Considere todos los pares de líneas vecinas (líneas, no segmento de línea), encuentre la intersección. Estos son el nuevo vértice.
Limpie el nuevo vértice quitando 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, tienes esto:
0----a----3
| | |
| | |
| b |
| |
| |
1---------2
7 y 4 se superponen ... si ves esto, eliminas este punto y todos los puntos intermedios.
(b) caso 2
0--7 4--3
| | | |
| 6--5 |
| |
1--------2
si lo gastas por dos, tienes 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
gastar por 1. este es un caso más general para el caso 1.
(d) caso 4
lo mismo que case3, pero gastar por dos.
En realidad, si puede manejar el caso 4. Todos los demás casos son solo casos especiales con alguna línea o superposición de vértices.
Para el caso 4, mantienes una pila de vértices ... presionas cuando encuentras líneas que se superponen con la última línea, y cuando aparece la última, aparece. - Al igual que lo que haces en casco convexo.
En el mundo SIG, se usa el almacenamiento en búfer negativo para esta tarea: http://www-users.cs.umn.edu/~npramod/enc_pdf.pdf
La biblioteca JTS debe 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
Escribí algunas publicaciones en el blog sobre mis experiencias al tratar de implementar el algoritmo de esqueleto recto para este caso (expansión / reducción de polígonos mediante compensación). En ese momento tenía dos blogs. Puede ser útil leer sobre algunos de los problemas que encontré:
Saludos,
Max
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 la distancia
da la "izquierda" de la 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 polinomio 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 viejo polígono "lo suficientemente lejos" de los vértices. Cerca de un vértice, el conjunto de puntos a la distancia d del polígono antiguo es, como dices, no un polígono, por lo que el requisito establecido 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.
Muchas gracias a Angus Johnson por su biblioteca clipper. Hay buenos ejemplos de código para hacer los recortes 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. Así que 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;
}
Nunca usé Clipper (desarrollado por Angus Johnson), pero para este tipo de cosas usualmente utilizo JTS . Para fines de demostración creé este jsFiddle que usa JSTS (puerto JavaScript de JTS). Solo necesitas convertir las coordenadas que tienes a las 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 usar 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) en coordenadas JSTS y todo lo demás es igual. Ejemplo:
Pensé que podría mencionar brevemente mi propia librería de clipping y compensación de polígonos : Clipper .
Si bien Clipper está diseñado principalmente para operaciones de recorte de polígonos, también compensa polígonos. La biblioteca es un programa gratuito de código abierto escrito en Delphi, C ++ y C # . Tiene una licencia de Boost muy libre de Boost , lo que le permite ser utilizado tanto en freeware como en aplicaciones comerciales sin cargo.
La compensación de polígonos se puede realizar usando uno de los tres estilos de compensación: cuadrado, redondo e ingleteado.
Según el consejo de @ JoshO''Brian, parece que el paquete rGeos en el lenguaje R implementa este algoritmo. Ver rGeos::gBuffer .
Una opción más es usar boost::polygon : falta algo de documentación, pero debería encontrar que los métodos resize y de bloat , y 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) por algún valor puede ser tan simple como:
poly += 2; // buffer polygon by 2
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 de desplazamiento 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 de la computación: una vez que tienes el esqueleto recto uno debe ser capaz de construir los polígonos desplazados con relativa facilidad. La biblioteca CGAL de fuente abierta y (gratuita para fines comerciales) tiene un paquete que implementa estas estructuras. Vea este ejemplo de código para calcular polígonos de compensación usando CGAL.
El manual del paquete debe brindarle 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 de CGAL: Compensación 2D de Esqueletos y Polígonos Rectos