Algoritmo para encontrar el centroide poligonal irregular (punto de etiqueta)

13

Necesito encontrar un centroide (o punto de etiqueta) para polígonos de forma irregular en Google Maps. Estoy mostrando InfoWindows para parcelas y necesito un lugar para anclar la InfoWindow que se garantiza que estará en la superficie. Ver imágenes a continuación.

texto alternativo texto alternativo

En realidad, no necesito nada específico de Google Maps, solo busco una idea de cómo encontrar automáticamente este punto.

Mi primera idea fue encontrar el centroide "falso" tomando el lat y el lngs promedio y colocando los puntos aleatoriamente desde allí hasta encontrar uno que interseque el polígono. Ya tengo el código de punto en el polígono. Esto me parece terriblemente "hacky".

Debo señalar que no tengo acceso a ninguno de los códigos del lado del servidor que generan la geometría, por lo que no puedo hacer nada como ST_PointOnSurface (the_geom).

Jason
fuente

Respuestas:

6

Rápido y sucio: si el centroide "falso" no está en el polígono, use el vértice más cercano a ese punto.

Dandy
fuente
No había pensado en esto. Idealmente me gustaría este punto en el polígono y no en el borde, pero esto podría ser a lo que recurro.
Jason
Una vez que haya encontrado un punto de borde, puede intersecar un pequeño cuadrado centrado en ese punto con el polígono y luego elegir el centroide de la intersección. Cuando el cuadrado es lo suficientemente pequeño, se garantiza que será un punto interior (aunque, por supuesto, estará muy cerca de un borde).
whuber
@ Jason Si usa el centroide real, es menos probable que encuentre este problema. No debería ser demasiado difícil traducir algo rápidamente a JavaScript: github.com/cartesiananalytics/Pipra/blob/master/src/…
Dandy
Si bien mi solución (rayos del falso centroide) funcionará la mayor parte del tiempo, creo que esta solución probablemente funcionaría mejor debido a su simplicidad y al hecho de que está garantizado que encontrará un punto al menos en el borde, y podría cambiar fácilmente estar dentro del polígono con muy poco esfuerzo.
Jason
3

Es posible que desee ver esto: http://github.com/tparkin/Google-Maps-Point-in-Polygon

Parece utilizar un algoritmo de Casting de rayos que debe coincidir con el caso que presentó.

Hay una publicación de blog al respecto aquí. http://appdelegateinc.com/blog/2010/05/16/point-in-polygon-checking/

DavidF
fuente
Si desea implementar esto en el lado del servidor, tanto JTS (Java) como Geos (C) implementan esta funcionalidad.
DavidF
Sí, probablemente debería haber agregado que ya tengo el código para determinar si mi centroide "calculado" está dentro del polígono o no. Lo que realmente quiero es alguna forma de crear un centroide que esté dentro del polígono.
Jason
3

Un algoritmo ESRI (más antiguo) calcula el centro de masa y, después de probarlo para su inclusión en el polígono, lo mueve horizontalmente si es necesario hasta que se encuentre dentro del polígono. (Esto podría hacerse de muchas maneras dependiendo de qué operaciones fundamentales estén disponibles dentro de su entorno de programación). Esto tiende a producir puntos de etiqueta bastante cerca del centro visual del polígono: pruébelo en la ilustración.

whuber
fuente
1

Resolví mi problema extendiendo el popular código epoly de http://econym.org.uk/gmap . Básicamente lo que terminé haciendo fue:

  • Cree una serie de rayos que comiencen desde el "centroide falso" y se extiendan a cada esquina y lado (8 en total)
  • Incrementalmente cree un punto 10,20,30 ... por ciento por cada rayo y vea si este punto está en nuestro polígono original

Código de epoly extendido a continuación:

google.maps.Polygon.prototype.Centroid = function() {
var p = this;
var b = this.Bounds();
var c = new google.maps.LatLng((b.getSouthWest().lat()+b.getNorthEast().lat())/2,(b.getSouthWest().lng()+b.getNorthEast().lng())/2);
if (!p.Contains(c)){
    var fc = c; //False Centroid
    var percentages = [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9]; //We'll check every 10% down each ray and see if we're inside our polygon
    var rays = [
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getNorthEast().lat(),fc.lng())]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(fc.lat(),b.getNorthEast().lng())]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getSouthWest().lat(),fc.lng())]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(fc.lat(),b.getSouthWest().lng())]}),
        new google.maps.Polyline({path:[fc,b.getNorthEast()]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getSouthWest().lat(),b.getNorthEast().lng())]}),
        new google.maps.Polyline({path:[fc,b.getSouthWest()]}),
        new google.maps.Polyline({path:[fc,new google.maps.LatLng(b.getNorthEast().lat(),b.getSouthWest().lng())]})
    ];
    var lp;
    for (var i=0;i<percentages.length;i++){
        var percent = percentages[i];
        for (var j=0;j<rays.length;j++){
            var ray = rays[j];
            var tp = ray.GetPointAtDistance(percent*ray.Distance()); //Test Point i% down the ray
            if (p.Contains(tp)){
                lp = tp; //It worked, store it
                break;
            }
        }
        if (lp){
            c = lp;
            break;
        }
    }
}
return c;}

Todavía un poco hacky pero parece funcionar.

Jason
fuente
Este método fallará para algunos polígonos tortuosos. Por ejemplo, proteja la polilínea {{0, 9}, {10, 20}, {9, 9}, {20, 10}, {9, 0}, {20, -10}, {9, -9} , {10, -20}, {0, -9}, {-10, -20}, {-9, -9}, {-20, -10}, {-9, 0}, {-20, 10}, {-9, 9}, {-10, 20}, {0,9}} en menos de 1/2. También es ineficiente en comparación con el método QAD de Dandy, por ejemplo.
whuber
1

Otro algoritmo 'sucio' para hacer eso:

  • Toma el cuadro delimitador de la geometría (Xmax, Ymax, Xmin, Ymin)

  • Haga un bucle hasta que se encuentre un punto aleatorio ( Xmin+rand*(Xmax-Xmin), Ymin+rand*(Ymax-Ymin) ) dentro de la geometría (usando Google-Maps-Point-in-Polygon )

julien
fuente
+1 porque esto puede tener una buena posibilidad de un golpe la segunda vez. Siempre y cuando su "aleatorio" sea reproducible cada vez para no molestar al usuario, esta también es una solución válida. Las posibilidades de que no llegue a un punto válido pronto son escasas, especialmente si comienza con un buen punto de suposición.
Dandy
1
@Dandy: En realidad, en algunos casos, este puede ser un algoritmo realmente pobre. Considere una astilla diagonal estrecha por ejemplo. Estos existen en la práctica (p. Ej., Largas parcelas del frente de la carretera) y pueden ocupar fácilmente menos del 0.1% del cuadro delimitador (a veces mucho menos). Para estar razonablemente seguro (95% seguro) de golpear un polígono de este tipo con esta técnica, requeriría aproximadamente 3,000 iteraciones.
whuber
@Whuber: Si eliges una mala ubicación de inicio, sí, eso podría tomar un tiempo para completarse. Si también considera que hipotéticamente el 95% de los clics estarán en geometrías más deseables, esto solo puede ser un problema el 5% del tiempo. Además, como con otra pregunta de GIS.se, si el rendimiento es el objetivo, nunca hay una solución única, lo mejor es cambiar las tácticas en función de la heurística. No hay razón para ejecutar esto para 3000 iteraciones. Siempre puede rescatar a mi QAD después de 10. Creo que valdría la pena probarlo durante algunas iteraciones, ya que la ubicación puede ser más deseable.
Dandy
@Dandy: ¿Pero cuál es el problema con su solución QAD? Incluso podría modificarlo un poco moviéndose del punto de etiqueta de prueba original al vértice más cercano en algún búfer interno del polígono: todavía QAD pero ahora garantizado para aterrizar en una ubicación interna de la característica original. Por cierto, su estrategia de rescate pronto es buena. Cada vez que codifico una sonda aleatoria como esta, calculo previamente la proporción del área de la característica con la de su cuadro delimitador, la uso para encontrar el tiempo esperado para el éxito e inmediatamente le advierto al usuario si puede ser larga.
whuber
@Whuber, la razón heurística de área es una gran idea porque calculas el centroide cuando calculas el área. En cuanto al problema con mi solución QAD: está al límite. Si elijo ese punto y lo amortiguo como usted dice, ese radio "pequeño" puede ser mayor que la longitud a través de esa sección estrecha. Siempre hay un caso de esquina. Hay mucho que considerar, solo para hacer un globo que desordenará la interfaz de usuario y oscurecerá la geometría de todos modos. Probablemente sea mejor elegir el vértice más alto o más bajo.
Dandy
1

A la luz de su reciente aclaración de que preferiría una ubicación estrictamente interior, podría seleccionar cualquier punto en la Transformación del Eje Medial que no esté también en el límite del polígono. (Si no tiene código para un MAT, puede aproximarlo almacenando negativamente el polígono. Una búsqueda binaria o secante producirá rápidamente un pequeño polígono interior que se aproxima a parte de MAT; use cualquier punto en su límite).

whuber
fuente
Entiendo lo que estabas diciendo sobre el uso del borde de una geometría tal que el borde esté dentro del polígono de interés. No entiendo cómo harías para crear este borde / vértice. Lo único que se me ocurre es hacer un triángulo virtual intersectando un rayo perpendicular desde el punto de interés al segmento opuesto al segmento del punto seleccionado. El punto medio entre esos dos puntos podría ser la parte superior de ese triángulo virtual.
Dandy
@Dandy: Eso llega al corazón de todo. Hay muchas formas de hacerlo dependiendo de lo que haga su SIG de forma nativa. Por ejemplo, una vez que haya encontrado un rayo que interseca la entidad original en un conjunto de longitud positiva, esa intersección será una unión disjunta de segmentos de línea. Use el centro de cualquiera de esos segmentos. Otra forma es comenzar con cualquier punto de la entidad (preferiblemente cerca de su centro, que es lo que logró su método QED), crear un pequeño polígono simple (por ejemplo, cuadrado) centrado allí, intersecarlo con la entidad original, elegir el único conectado componente ...
whuber
(continuación) ... que contiene el punto de partida, y recursivamente elige un centro para ese componente. Habrá muchos métodos disponibles cuando su SIG le permita recorrer las secuencias de vértices que describen el límite de la entidad. Si se admiten memorias intermedias negativas, puede encontrar iterativamente un conjunto de puntos interiores de distancia máxima (el "esqueleto", que es un subconjunto de la MAT). Esto es un poco caro, pero es bastante fácil de programar y produce excelentes puntos de etiqueta.
whuber
0

¿Por qué no usar el centroide solo para la posición vertical (latitud)? Luego, puede colocar la etiqueta horizontalmente seleccionando la longitud promedio en esa latitud . (Para esto, deberías encontrar el valor de longitud para un borde de polígono en una latitud específica, lo que no debería darte ningún problema).

Además, tenga cuidado con las formas en U y las más complejas. :) Posiblemente para aquellos, elija el promedio del par de longitudes más a la derecha (cada par correspondería a una porción del polígono), ya que la ventana de información está orientada de esa manera?

Esto también le da un poco más de control sobre el posicionamiento; por ejemplo, podría ser bueno colocar la ventana de información en 66 o 75% verticalmente, para dejar más polígono visible. (¡O puede que no! Pero tienes la perilla para ajustar).

Dan S.
fuente
0

¿Qué tal si usas el punto en el que el usuario hizo clic para seleccionarlo, si es seleccionado por el usuario que lo es?

Dandy
fuente
Se puede seleccionar con un clic del mouse o una consulta no espacial, por lo que esto no siempre funcionaría.
Jason
0

Estoy tratando de resolver esto también. He impuesto una condición a mis polígonos de que no pueden tener líneas de cruce que entren en lo que describiré.

Entonces, mi enfoque usa triangulación. Tome un vértice aleatorio (posiblemente tomar un vértice en el extremo N, E, W o S puede simplificar las cosas).

Desde este vértice, dibuje líneas al vértice a un vértice de distancia, es decir, si su vértice es el vértice 3, mire el vértice 3 + 2.

Construya una línea desde su vértice original hasta este vértice. Si la línea construida:

  1. no cruza otra línea y
  2. su punto medio no está fuera del polígono

Entonces has construido un triángulo que está dentro del polígono. Si el vértice exitoso fue n + 2, entonces su triángulo es {n, n + 1, n + 2}, al que nos referiremos como {v, v1, v2}. De lo contrario, intente con el siguiente vértice y continúe hasta que se hayan probado todos los vértices.

Cuando encuentre un triángulo, encuentre el centro de ese punto tomando una línea desde el vértice v hasta el punto medio de v1 y v2. Se garantiza que el punto medio de esa línea estará dentro del triángulo y dentro del polígono.

Todavía no he codificado esto, pero puedo ver, al pensarlo, que un polígono con líneas cruzadas de hecho causará algunas condiciones exóticas donde esto no funciona. Si ese es el tipo de polígonos que tiene, necesitaría probar cada segmento de línea en el polígono y asegurarse de que no se haya cruzado. Omita los segmentos de línea que se cruzan, y creo que funcionará.


fuente