Supongo que mi problema está relacionado con "casco convexo", pero no es lo mismo. Todas las formas en el dibujo son rectángulos con el mismo ancho y alto. Muchos son adyacentes el uno al otro. Quiero combinar esos rectángulos adyacentes en polígonos. A diferencia del "casco convexo", los polígonos rediseñados podrían ser "huecos" en el interior.Algoritmo para unir rectángulos adyacentes en el polígono
¿Hay algún algoritmo de código abierto disponible?
Me gustaría buscar algo como General Polygon Clipper. Básicamente estás haciendo operaciones de polígono de unión (OR). El hecho de que sean todos rectángulos solo hace que las matemáticas sean un poco más fáciles, pero podría hacerse fácilmente con algo como GPC.
También hay contenedores de idiomas para muchos idiomas.
lo usé y funcionó: http://eggie5.com/43-merging-adjacent-polygons – eggie5
basta con probar si los rectángulos están tocando y luego corren casco convexo en la unión de sus puntos.
O también se puede probar manualmente para ver de qué lado de los rectángulos están tocando y añadir el punto en el orden correcto para un objeto polígono.
Suponen que los polígonos cerrados serán suficientes (no pueden tener agujeros).
Eso no funcionará si quiere preservar los agujeros.Imagine tener un bloque de rectángulos de 3x3, pero falta el rectángulo central: el casco convexo lo rellenará. –
Buen punto, respuesta editada. –
Si está utilizando una biblioteca de procesamiento espacial (como JTS [java], NTS [.net] o GEOS [C++], que son todas de código abierto y utilizables para aplicaciones comerciales, a diferencia de GPC) puede unir rectángulos.
La forma general de hacerlo es construir un gráfico de los bordes de las entradas (rectángulos), realizar intersecciones, etiquetar los bordes como adentro o afuera del resultado, y solo mantener los bordes externos. No sé de un algoritmo específico para tratar rectángulos, pero probablemente sería similar, excepto que, como se señaló, la matemática sería más simple.
si sus límites son el uso razonable de una matriz 2D de los recuentos de borde, de lo contrario tendría que utilizar diccionarios anidados.
porque todas las anchuras y alturas son los mismos que puede identificar de manera única un borde por una combinación de x, y, y la orientación (vertical u horizontal)
muestra pseudocódigo: list_of_edges = nueva lista arr_count = new int [] [] []
fill_with_zeroes(arr_count)
foreach rect
foreach edge
arr_count [edge.x][edge.y][edge.orientation] += 1
foreach edge in arr_count
if count[edge] = 1
list_of_edges.add(edge]
por supuesto, si usted quiere ordenar los bordes, entonces usted tendría que pasar a través de la matriz en otro momento
foreach edge in arr_count
if count[edge] = 1
add_recursive(edge)
add_recursive(x,y):
for both horizontal and vertical orientations of edge starting at x, y:
count[edge] = 0
if (edge.orientation is horizontal)
return add_recursive(x+1, y)
else
return add_recursive(x, y+1)
lo siento, este pseudocódigo es bastante descuidado, pero debería obtener la idea general
Tuve que escribir un algoritmo para fusionar polígonos adyacentes como parte de un proyecto de experimento con lienzo HTML5 (nada glorioso, un rompecabezas :-) Los agujeros en el polígono resultante son naturalmente compatibles. La rutina Javascript se encuentra en la función llamada Polygon.prototype.merge() en www punto raymondhill punto net/rompecabezas-rhill/jigsawpuzzle-rhill-3 punto js
La clave es eliminar los segmentos que están duplicados, pero de direccion opuesta. Explicación aproximada: un punto es {x:?, Y :?}, un segmento es {ptA:?, PtB :?}, un contorno es {pts: []} (una colección de objetos Point conectados), un polígono es {contornos: []} (una colección de objetos Contour.)
El algoritmo de combinación recopila todos los segmentos en un gran grupo de Objetos de segmento, donde se eliminan los duplicados. Primero, todos los segmentos de todos los contornos que definen el Polígono A se agregan al grupo. Luego, todos los segmentos de todos los contornos que definen el Polígono B se agregan al grupo, pero lo probamos y eliminamos por duplicado (lo hacemos fácilmente usando un objeto Punto como una clave hash).
Luego tomamos un segmento del grupo (al azar está bien), y lo "caminamos" hasta que llegamos a un "callejón sin salida", es decir, no se puede conectar más segmentos. Esto forma un objeto Contour. Repetimos hasta que se haya utilizado toda la colección de segmentos. A medida que se utilizan segmentos, se eliminan del grupo. "Caminar" un segmento significa que tomamos su punto final, y buscamos un segmento cuyo punto de inicio coincida con él.
Como dije, como resultado tenemos una colección de objetos Contour que definen el Polígono. Algunos contornos se llenarán, algunos pueden ser huecos. Determinar si un contorno está lleno o hueco es solo una cuestión de probar si el contorno es en sentido horario o antihorario, o si su área es positiva o negativa. Es una convención, en mi caso los contornos en el sentido de las agujas del reloj están llenos, en sentido antihorario son huecos.
Aquí está mi implementación, menos los detalles y el manejo de errores menos. Con suerte he copiado/pegado suficiente para que pueda hacer que funcione de inmediato, de lo contrario se refiere a mi archivo JS encima de contexto:
// Point object
function Point(a,b) {
// a=x,b=y
if (b) {
this.x=a;
this.y=b;
}
// a=Point or {x:?,y:?}
else if (a) {
this.x=a.x;
this.y=a.y;
}
// empty
else {
this.x=this.y=0;
}
}
Point.prototype.toHashkey = function() {
return this.x+"_"+this.y;
};
Point.prototype.clone = function() {
return new Point(this);
};
// Segment object
function Segment(a,b) {
this.ptA = new Point(a);
this.ptB = new Point(b);
}
// Contour object
function Contour(a) {
this.pts = []; // no points
if (a) {
if (a instanceof Array) { // assume array of Point objects
var nPts = a.length;
for (var iPt=0; iPt<nPts; iPt++) {
this.pts.push(a[iPt].clone());
}
}
}
}
Contour.prototype.clone = function() {
return new Contour(this);
};
Contour.prototype.addPoint = function(p) {
this.pts.push(p);
};
// Polygon object
function Polygon(a) {
this.contours = []; // no contour
if (a) {
if (a instanceof Polygon) {
var contours = a.contours;
var nContours = contours.length;
for (var iContour=0; iContour<nContours; iContour++) {
this.contours.push(new Contour(contours[iContour]));
}
}
else if (a instanceof Array) {
this.contours.push(new Contour(a));
}
}
}
Polygon.prototype.merge = function(other) {
// A Javascript object can be used as an associative array, but
// they are not real associative array, as there is no way
// to query the number of entries in the object. For this
// reason, we maintain an element counter ourself.
var segments={};
var contours=this.contours;
var nContours=contours.length;
var pts; var nPts;
var iPtA; var iPtB;
var idA; var idB;
for (var iContour=0; iContour<nContours; iContour++) {
pts = contours[iContour].pts;
nPts = pts.length;
iPtA = nPts-1;
for (iPtB=0; iPtB<nPts; iPtA=iPtB++) {
idA = pts[iPtA].toHashkey();
idB = pts[iPtB].toHashkey();
if (!segments[idA]) {
segments[idA]={n:0,pts:{}};
}
segments[idA].pts[idB] = new Segment(pts[iPtA],pts[iPtB]);
segments[idA].n++;
}
}
// enumerate segments in other's contours, eliminate duplicate
contours = other.contours;
nContours = contours.length;
for (iContour=0; iContour<nContours; iContour++) {
pts = contours[iContour].pts;
nPts = pts.length;
iPtA=nPts-1;
for (iPtB=0; iPtB<nPts; iPtA=iPtB++) {
idA = pts[iPtA].toHashkey();
idB = pts[iPtB].toHashkey();
// duplicate (we eliminate same segment in reverse direction)
if (segments[idB] && segments[idB].pts[idA]) {
delete segments[idB].pts[idA];
if (!--segments[idB].n) {
delete segments[idB];
}
}
// not a duplicate
else {
if (!segments[idA]) {
segments[idA]={n:0,pts:{}};
}
segments[idA].pts[idB] = new Segment(pts[iPtA],pts[iPtB]);
segments[idA].n++;
}
}
}
// recreate and store new contours by jumping from one point to the next,
// using the second point of the segment as hash key for next segment
this.contours=[]; // regenerate new contours
var contour;
for (idA in segments) { // we need this to get a starting point for a new contour
contour = new Contour();
this.contours.push(contour);
for (idB in segments[idA].pts) {break;}
segment = segments[idA].pts[idB];
while (segment) {
contour.addPoint(new Point(segment.ptA));
// remove from collection since it has now been used
delete segments[idA].pts[idB];
if (!--segments[idA].n) {
delete segments[idA];
}
idA = segment.ptB.toHashkey();
if (segments[idA]) {
for (idB in segments[idA].pts) {break;} // any end point will do
segment = segments[idA].pts[idB];
}
else {
segment = null;
}
}
}
};
Cuando "caminar" el segmento para crear un contorno, hay un caso en que una segmento puede conectarse a más de un segmento:
+------+-------+
| Poly A | two segments sharing same start point Z
| |
+ +---<---Z---->---+
| | | Poly B |
| | | |
+ +-------+--------+
| |
| |
+------+-------+--------+
que puede conducir a dos resultados válidos (el algoritmo anterior dará lugar al azar a uno o el otro):
resultado 1, un contorno llenado:
+------+--->---+
| Poly A |
| |
+ +---<---+---->---+
| | | |
| | | |
+ +--->---+ +
| |
| |
+------+---<---+--------+
Resultado 2, un contorno de llenado, un contorno hueco:
+------+--->---+
| Poly A |
| |
+ +---<---+---->---+
| | Hole A| |
| | | |
+ +--->---+ +
| |
| |
+------+---<---+--------+
Esto no debería ser un problema, aunque, como su código ya debería estar listo para manejar agujeros.
Otro detalle importante: El algoritmo anterior no se deshace de puntos ('+') intermedios, de hecho, se espera o de lo contrario el algoritmo no funcionarán, como en el siguiente caso:
+------>-------+
| Poly A |
| |
| | +---->---+
| | | Poly B |
| | | |
| | +----<---+
| |
| |
+------<-------+
Según tengo entendido, esto es lo que tienes. Me imagino que el algoritmo puede ser extendida para soportar este caso mediante la búsqueda y la adición de los puntos de intersección de antemano (no era necesario en mi caso):
+------>-------+
| Poly A |
| |
| + +---->---+
| | | Poly B |
| | | |
| + +----<---+
| |
| |
+------<-------+
Esperanza esta ayuda.
P.S .: Usted puede 'probar' el algoritmo con el rompecabezas, encajando piezas juntas para generar agujeros, etc .: http://www.raymondhill.net/puzzle-rhill/puzzle-rhill.php?puzzlePieces=16&puzzleComplexity=1&puzzleURL=http://www.public-domain-photos.com/free-stock-photos-4/travel/los-angeles/los-angeles-skyline.jpg&puzzleRotate=0&puzzleVersion=3
Gracias por esta respuesta, pude usar el algoritmo en un contexto cartográfico con la lib de OpenLayers. –
¿Qué tal intentar lo siguiente. Creo que esto funcionará si está diseñado correctamente.
Encuentra el rectángulo más pequeño emclosing, básicamente max-x, x-min y max-min y y-y.Este será nuestro lienzo para dibujar. Inicialice una matriz 2D de bits dx X dy donde dx, dy son el ancho de este rectángulo externo, a todos los 0.
Nuestro objetivo es encontrar el contorno, básicamente algunas esquinas de los rectángulos para que podamos reducir este problema a un nivel donde podamos manejarlo computacionalmente, una vez que tengamos los puntos podemos escalar para obtener las coordenadas reales .
Escanee a través de la matriz 2D anterior y marque un punto 1 si está contenido en uno de los rectángulos dados.
Ahora escanee la matriz 2D y busque puntos cuya vecindad tenga una división 3: 1, lo que significa que en 3 lados tiene 1s y en un lado 0s o viceversa. Estos puntos son los que definirán el contorno.
Creo que la complejidad será manejable si podemos reducir el problema sabiamente.
he encontrado una manera mucho más simple:
Eso es todo!
Tuve un problema similar anteriormente. No sé exactamente cómo están alineados sus puntos, pero el mío siempre estuvo espaciado a 5 metros el uno del otro.
Mi solución fue obtener el punto ordenado por la coordenada x.
Tenía dos listas, una llamada anterior y otra llamada actual.
Si la corriente estaba vacía, agregue el punto a la corriente. Si la corriente no está vacía, compruebe si el punto es adyacente a uno de los puntos en la corriente (ejecute la lista hacia atrás ya que hay una mayor probabilidad de que un punto reciente sea adyacente)
Si el punto no está adyacente a ningún punto en la corriente, luego verifique si alguno de los puntos en la corriente es adyacente a cualquier punto en la lista anterior. En caso afirmativo, fusione (concat) ellos, si no, mueva los puntos de la lista anterior a otra que contenga los polígonos completos, luego configure previo = actual, vacíe la corriente y agregue el punto procesado a la actual.
Dependiendo de cómo se procesen los puntos (el orden), es posible que deba ejecutar nuevamente todos los polígonos para comprobar si están adyacentes a cualquiera de los otros polígonos.
Lo siento por el largo muro de texto, avíseme si quiere codificar, está en C# y no está muy limpio.
¿Lenguaje de programación? –
El perímetro de cualquier mancha de rectángulos adyacentes forma un polígono. ¿Tu pregunta es "¿Cómo hago una lista de los segmentos de línea que definen el perímetro de un conjunto de rectángulos conectados?" ¿o algo mas? – mbeckish
Cuando dices "muchos son adyacentes entre sí", ¿qué significa eso? ¿Simplemente tocan en los bordes o pueden superponerse los rectángulos? ¿Están los rectángulos en una cuadrícula de algún tipo, o pueden sus vértices estar en alguna parte? –