Fuzzy menos gruesa común algoritmo de partición

Question

Dadas dos particiones diferentes de una forma, por el motivo de la discusión, dos diferentes divisiones administrativas de un país), ¿cómo puedo encontrar una nueva partición en la que ambas particiones de ajuste, que permite (y la optimización de) algún error?

Por ejemplo, omitiendo el error, quiero un algoritmo que hace esto:

Tal vez ayuda a expresar esto en conjunto de términos. Utilizando la siguiente numeración:

De lo que puedo expresar las particiones anterior como:

Un = {{1},{2},{3,4,7,8},{5},{6},{9,10,13,14},{11},{12},{15},{16}}

B = {{1,2,5,6},{3},{4},{7},{8},{9},{10},{13},{14},{11,15},{12,16}}

Un punto B = {{1,2,5,6},{3,4,7,8},{9,10,13,14},{11,15},{12,16}}

y el algoritmo para la producción de Un punto B, parece sencillo (algo así como, si dos elementos se encuentran en una partición juntos en Un (B) combinar las particiones están en B (A) - repetir hasta que a y B son iguales).

Pero ahora imagina que algunas de estas líneas son ligeramente diferentes entre los dos particiones, por lo que esta respuesta perfecta no es posible, y en lugar de ello quiero la respuesta óptima objeto de minimizar algunos de error de criterio.

Tomar un nuevo ejemplo:

Aquí en la columna de la izquierda tenemos dos particiones sin líneas comunes (aparte de que el borde exterior de sí mismo). La única solución posible a la de arriba es la trivial, la columna de la derecha. Pero si permitimos que la "confusión" de las soluciones, a continuación, la columna central puede ser permitido, con un 5% del total de la zona en disputa (es decir, asignados a los diferentes subárea en cada tosco partición). Así podemos describir el medio de la columna como la representación del "menos gruesa de la partición común con <= 5% de error".

Si la respuesta real es entonces la partición en la parte superior de la fila, la columna central o en el medio de la fila, la columna del medio - o algo en el medio, es menos importante.

Answer 1

Usted puede hacer esto mediante la evaluación de la diferencia de un polígono es el límite de la diferencia simétrica entre sus límites, o simbólicamente se expresa como:

Difference(a, SymDifference(a, b))

Tomar las geometrías de un y b, expresado como MultiLinestrings durante los próximos dos líneas y las imágenes:

MULTILINESTRING((0 300,50 300,50 250,0 250,0 300),(50 300,100 300,100 250,50 250,50 300),(0 250,50 250,50 200,0 200,0 250),(50 250,100 250,100 200,50 200,50 250),(100 300,200 300,200 200,100 200,100 300),(0 200,100 200,100 100,0 100,0 200),(100 200,150 200,150 150,100 150,100 200),(150 200,200 200,200 150,150 150,150 200),(100 150,150 150,150 100,100 100,100 150),(150 150,200 150,200 100,150 100,150 150))
MULTILINESTRING((0 300,100 300,100 200,0 200,0 300),(100 300,150 300,150 250,100 250,100 300),(150 300,200 300,200 250,150 250,150 300),(100 250,150 250,150 200,100 200,100 250),(150 250,200 250,200 200,150 200,150 250),(0 200,50 200,50 150,0 150,0 200),(50 200,100 200,100 150,50 150,50 200),(0 150,50 150,50 100,0 100,0 150),(50 150,100 150,100 100,50 100,50 150),(100 200,150 200,150 100,100 100,100 200),(150 200,200 200,200 100,150 100,150 200))

La diferencia simétrica, donde partes de un y b no se cruzan, es:

MULTILINESTRING((50 300,50 250),(50 250,0 250),(100 250,50 250),(50 250,50 200),(150 150,100 150),(200 150,150 150),(150 300,150 250),(150 250,100 250),(200 250,150 250),(150 250,150 200),(50 200,50 150),(50 150,0 150),(100 150,50 150),(50 150,50 100))

Y por último, evaluar la diferencia entre un o b y la diferencia simétrica:

MULTILINESTRING((0 300,50 300),(0 250,0 300),(50 300,100 300),(100 300,100 250),(50 200,0 200),(0 200,0 250),(100 250,100 200),(100 200,50 200),(100 300,150 300),(150 300,200 300,200 250),(200 250,200 200),(200 200,150 200),(150 200,100 200),(100 200,100 150),(100 150,100 100),(100 100,50 100),(50 100,0 100,0 150),(0 150,0 200),(150 200,150 150),(200 200,200 150),(150 150,150 100),(150 100,100 100),(200 150,200 100,150 100))

Puede implementar esta lógica en GEOS (bien formada, PostGIS, etc.), El STC, y otros. Tenga en cuenta que si la entrada de geometrías son polígonos, a continuación, sus límites deben ser extraídos, y el resultado puede ser polygonized. Por ejemplo, se muestra con PostGIS, tomar dos Multipolígonos, y obtener un Multipolígono resultado:

SELECT
  ST_AsText(ST_CollectionHomogenize(ST_Polygonize(
    ST_Difference(ST_Boundary(A), ST_SymDifference(ST_Boundary(A), ST_Boundary(B)))
  ))) AS result
FROM (
  SELECT 'MULTIPOLYGON(((0 300,50 300,50 250,0 250,0 300)),((50 300,100 300,100 250,50 250,50 300)),((0 250,50 250,50 200,0 200,0 250)),((50 250,100 250,100 200,50 200,50 250)),((100 300,200 300,200 200,100 200,100 300)),((0 200,100 200,100 100,0 100,0 200)),((100 200,150 200,150 150,100 150,100 200)),((150 200,200 200,200 150,150 150,150 200)),((100 150,150 150,150 100,100 100,100 150)),((150 150,200 150,200 100,150 100,150 150)))'::geometry AS a,
    'MULTIPOLYGON(((0 300,100 300,100 200,0 200,0 300)),((100 300,150 300,150 250,100 250,100 300)),((150 300,200 300,200 250,150 250,150 300)),((100 250,150 250,150 200,100 200,100 250)),((150 250,200 250,200 200,150 200,150 250)),((0 200,50 200,50 150,0 150,0 200)),((50 200,100 200,100 150,50 150,50 200)),((0 150,50 150,50 100,0 100,0 150)),((50 150,100 150,100 100,50 100,50 150)),((100 200,150 200,150 100,100 100,100 200)),((150 200,200 200,200 100,150 100,150 200)))'::geometry AS b
) AS f;
                               result
--------------------------------------------------------------------------------
MULTIPOLYGON(((0 300,50 300,100 300,100 250,100 200,50 200,0 200,0 250,0 300)),((100 250,100 300,150 300,200 300,200 250,200 200,150 200,100 200,100 250)),((0 200,50 200,100 200,100 150,100 100,50 100,0 100,0 150,0 200)),((150 200,200 200,200 150,200 100,150 100,150 150,150 200)),((100 200,150 200,150 150,150 100,100 100,100 150,100 200)))

Tenga en cuenta que tengo no ampliamente probado este método, a fin de tomar estas ideas como punto de partida.

Answer 2

Los errores de libre algoritmo.

Primer set: Segundo set:

Combinación de 2 juegos y ordenar en orden descendente por la zona. Seleccione las filas de la tabla (arriba => abajo) hasta que el total de áreas = área total (16 en este caso):

Filas seleccionadas hacer que tu respuesta:

Los criterios que va a ser una diferencia entre el acumulado de las áreas y el total real.