¿Cuál es la forma más rápida de encontrar el centro "visual" de un polígono de forma irregular?

Question

Necesito encontrar un punto que sea un centro visual de un polígono de forma irregular. Por centro visual, me refiero a un punto que parece estar en el centro de una gran área del polígono visualmente. La aplicación es poner una etiqueta dentro del polígono.

Aquí es una solución que utiliza el interior de amortiguación:

https://web.archive.org/web/20150708063910/http://proceedings.esri.com/library/userconf/proc01/professional/papers/pap388/p388.htm

Si esto se va a utilizar, lo que es una manera eficaz y rápida de encontrar el buffer? Si se va a usar cualquier otra forma, ¿cuál es?

Un buen ejemplo de polígonos realmente duros es una U gruesa gigante (escrita en Arial Black o Impact o alguna fuente similar).

Answer 1

Si usted puede convertir el polígono en una imagen binaria, entonces se puede utilizar la base de que existe en el campo del procesamiento de imágenes, por ejemplo .: A Fast Skeleton Algorithm on Block Represented Binary Images.

Pero esto no es realmente razonable en el caso general, debido a errores de discretización y trabajo adicional.

Sin embargo, tal vez a encontrar estos útiles:

• Straight skeleton of a simple polygon
• Determining the Skeleton of a Simple Polygon in (Almost) Linear Time

EDIT: Tal vez usted quiere buscar el punto que es el centro del círculo más grande contenida en el polígono. No necesariamente se encuentra siempre en el centro observado, pero la mayor parte del tiempo probablemente dará el resultado esperado, y solo en casos levemente patológicos algo que está totalmente fuera de control.

Answer 2

Este problema probablemente sería análogo a encontrar el "centro de masa" asumiendo una densidad uniforme.

EDIT: Este método no funcionará si el polígono tiene "agujeros"

Answer 3

Compute la posición central (x, y) de cada borde del polígono. Puede hacer esto al encontrar la diferencia entre las posiciones de los extremos de cada borde. Tome el promedio de cada centro en cada dimensión. Este será el centro del polígono.

Answer 4

Creo que si rompiste el polígono en sus vértices, y luego aplicaste una función para encontrar el casco convexo más grande, y luego encontraste el centro de ese casco convexo, coincidiría estrechamente con el centro "aparente".

Encontrar el mayor casco convexo dados los vértices: Look under the Simple Polygon paragraph.

media de los vértices de la envolvente convexa para encontrar el centro.

Answer 5

Si entiendo el punto del documento con el que vinculó (un problema bastante interesante, por cierto), esta técnica de "amortiguación interna" es similar a modelar la forma en cuestión con un trozo de azúcar que se disuelve con ácido desde los bordes hacia adentro (por ejemplo, a medida que aumenta la distancia del buffer, queda menos de la forma original). El último bit restante es el lugar ideal para colocar una etiqueta.

cómo lograr esto en un algoritmo por desgracia no es muy claro para mí ....

Answer 6

Podría colocar la etiqueta en el centro ingenua (del cuadro delimitador, tal vez), y luego moverlo basan en las intersecciones de los bordes del polígono local y BB de la etiqueta? Muévete a lo largo de las normales de los bordes que se cruzan, y si se cruzan múltiples bordes, suma sus normales para el movimiento.

Simplemente adivinando aquí; en este tipo de problema, probablemente trataría de resolver iterativamente, siempre y cuando el rendimiento no sea demasiado preocupante.

Answer 7

¿Has estudiado el uso de la fórmula del centroide?

http://en.wikipedia.org/wiki/Centroid

http://en.wikipedia.org/wiki/K-means_algorithm

Answer 8

¿Qué le parece encontrar el "incircle" del polígono (el círculo más grande que cabe en su interior), y luego centrar la etiqueta en el centro de eso? Aquí hay un par de enlaces para empezar:

http://www.mathopenref.com/polygonincircle.html
https://nrich.maths.org/discus/messages/145082/144373.html?1219439473

Esto no funcionará perfectamente en cada polígono, lo más probable; un polígono que parecía una C tendría la etiqueta en un lugar algo impredecible. Pero la ventaja sería que la etiqueta siempre se superpondría a una parte sólida del polígono.

Answer 9

No hay mucho tiempo para elaborar o probar esto ahora, pero intentaré hacer más cuando tenga oportunidad.

Use centroids como método principal. Prueba para ver si el centroide está dentro del polígono; si no, dibuje una línea a través de el punto más cercano y del otro lado del polígono. En el punto medio de la sección de esa línea que está dentro del polígono, coloca tu etiqueta.

Porque el punto que está más cerca del centroide es probable que limite un área bastante grande, creo que esto podría dar resultados similares a los incircles de Kyralessa. Por supuesto, esto podría volverse loco si tuvieras un polígono con agujeros. En ese caso, los incircles probablemente serían mucho mejores. Por otro lado, se usa el método centroide (¿rápido?) Para los casos típicos.

Answer 10

No digo que este sea el más rápido, pero le dará un punto dentro del polígono. Calcule el Straight Skeleton. El punto que estás buscando está en este esqueleto. Puede elegir el que tenga la distancia normal más corta al centro del cuadro delimitador, por ejemplo.

Answer 11

El método centroide ya se ha sugerido varias veces. Creo que este es un excelente recurso que describe el proceso (y muchos otros trucos útiles con polígonos) muy intuitiva:

http://paulbourke.net/geometry/polygonmesh/centroid.pdf

Además, para la colocación de una etiqueta de interfaz de usuario sencilla, podría ser suficiente para simplemente calcular el delimitador cuadro del polígono (un rectángulo definido por el x más bajo y el más alto y coordenadas y de cualquier vértice en el polígono), y conseguir su centro en:

{ 
    x = min_x + (max_x - min_x)/2, 
    y = min_y + (max_y - min_y)/2 
} 

Esto es un poco más rápido que el cálculo del centro de gravedad, lo que podría ser significativo para una aplicación integrada o en tiempo real.

También tenga en cuenta que si sus polígonos son estáticos (no cambian de forma), puede optimizar guardando el resultado del cálculo del centro BB/centro de masa (relativo a, por ejemplo, el primer vértice del polígono) la estructura de datos del polígono.

Answer 12

centro de masa (o centro de gravedad) método que se utiliza en ingeniería civil que puede utilizar, aquí hay un enlace útil de Wikipedia:

http://en.wikipedia.org/wiki/Center_of_mass

Answer 13

¿Qué tal:

Si el centroide del polígono está dentro del polígono y úsela, sino:

1) Extienda una línea desde el centroide a través del polígono que divide el polígono en dos mitades del mismo área

2) El "centro visual" es la mitad del camino punto entre el punto más cercano donde la línea toca el perímetro y el siguiente punto de corte del perímetro en la dirección alejándose del centro de gravedad

Aquí hay un par de fotos para ilustrarlo:

Answer 14

he encontrado una muy buena solución para esto desde MapBox llama Polylabel. La fuente completa está disponible en su Github también.

Básicamente trata de encontrar el centro visual del polígono como dijo T Austin.

Ciertos detalles sugieren que esto puede ser una solución práctica:

Por desgracia, el cálculo de [la solución ideal] es complejo y lento . Las soluciones publicadas al problema requieren Triangulación de Delaunay restringida o calcular un esqueleto recto como los pasos de preprocesamiento , ambos lentos y propensos a errores.

Para nuestro caso de uso, no necesitamos una solución exacta - estamos dispuestos a cambiar la precisión para obtener más velocidad. Cuando colocamos una etiqueta en un mapa, es más importante que se compute en milisegundos que para que sea matemáticamente perfecto.

Una breve nota sobre el uso. El código fuente funciona muy bien para Javascript fuera de la caja, sin embargo, si la intención de utilizar esto con un polígono "normal", entonces usted debe envolver en una matriz vacía como las funciones que aquí toman GeoJSONPolygons en lugar de polígonos normales, es decir,

var myPolygon = [[x1, y1], [x2, y2], [x3, y3]]; 
var center = polylabel([myPolygon]);