¿Cuál es la forma más rápida de encontrar el centro "visual" de un polígono de forma irregular?
https://stackoverflow.com/questions/1203135
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Necesito encontrar un punto que sea el 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í hay una solución que utiliza el búfer interno:
Si se va a utilizar, ¿cuál es una forma efectiva y rápida de encontrar el búfer? Si se va a utilizar alguna otra forma, ¿cuál es esa manera?
Un buen ejemplo de polígonos realmente difíciles es una U gruesa gigante (escrita en Arial Black o Impact o alguna de esas fuentes).
Solución
Si puede convertir el polígono en una imagen binaria, puede usar la base que existe en el campo del procesamiento de imágenes, por ejemplo: Un algoritmo de esqueleto rápido en imágenes binarias representadas en bloque .
Pero esto no es realmente razonable en el caso general, debido a errores de discretización y trabajo adicional.
Sin embargo, tal vez te parezcan útiles:
- Esqueleto recto de un polígono simple
- Determinar el Esqueleto de un polígono simple en (casi) tiempo lineal
EDITAR: Tal vez desee buscar el punto que es el centro del círculo más grande contenido en el polígono. No necesariamente está siempre en el centro observado, pero la mayoría de las veces probablemente daría el resultado esperado, y solo en casos levemente patológicos, algo que está totalmente apagado.
Otros consejos
Encontré una solución muy buena para esto en MapBox llamada 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 esta puede ser una solución práctica:
Desafortunadamente, calcular [la solución ideal] es a la vez complejo y lento Las soluciones publicadas al problema requieren ya sea Triangulación de Delaunay restringida o cálculo de un esqueleto recto como pasos de preprocesamiento, los cuales son lentos y propensos a errores.
Para nuestro caso de uso, no necesitamos una solución exacta, estamos dispuestos a Cambia algo de precisión para conseguir más velocidad. Cuando estamos colocando una etiqueta en un mapa, es más importante que se calcule en milisegundos que para ser matemáticamente perfecto.
Sin embargo, una nota rápida sobre el uso. Sin embargo, el código fuente funciona muy bien para Javascript fuera de la caja si pretende usar esto con un " normal " polígono, entonces deberías envolverlo en una matriz vacía, ya que las funciones aquí toman GeoJSONPolygons en lugar de normal polígonos es decir
var myPolygon = [[x1, y1], [x2, y2], [x3, y3]];
var center = polylabel([myPolygon]);
¿Has examinado el uso de la fórmula centroide?
Cómo sobre: ??
Si el centroide del polígono está dentro del polígono, utilícelo, de lo contrario:
1) Extienda una línea desde el centroide a través del polígono dividiendo el polígono en dos mitades de área igual
2) El " centro visual " es el punto a medio camino entre el punto más cercano donde la línea toca el perímetro y el siguiente punto que corta el perímetro en la dirección que se aleja del centroide
Aquí hay un par de imágenes para ilustrarlo:
Calcule la posición central (x, y) de cada borde del polígono. Puede hacer esto encontrando 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.
El método de Centroid ya ha sido sugerido varias veces. Creo que este es un excelente recurso que describe el proceso (y muchos otros trucos útiles con polígonos) de manera muy intuitiva:
http://paulbourke.net/geometry/polygonmesh/centroid.pdf
También, para colocar una etiqueta de UI simple, podría ser suficiente simplemente calcular el cuadro delimitador del polígono (un rectángulo definido por las coordenadas xey más altas y bajas de cualquier vértice en el polígono), y obtener 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 calcular el centroide, lo que puede ser significativo para una aplicación incrustada 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 centro de BB / cálculo de cálculo de masa (relativo, por ejemplo, al primer vértice del polígono) al Estructura de datos del polígono.
No estoy diciendo que esto sea lo más rápido, pero te dará un punto dentro del polígono. Calcule el esqueleto recto . 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.
¿Qué hay de encontrar el " incircle " del polígono (el círculo más grande que cabe dentro de él), y luego centrar la etiqueta en el centro de eso? Aquí hay un par de enlaces para comenzar:
http://www.mathopenref.com/polygonincircle.html
https://nrich.maths.org/discus/messages/145082/ 144373.html? 1219439473
Lo más probable es que esto no funcione perfectamente en todos los polígonos; un polígono que parecía una C tendría la etiqueta en un lugar impredecible. Pero la ventaja sería que la etiqueta siempre se superpondría a una parte sólida del polígono.
Si entiendo el punto del artículo al que está vinculado (un problema bastante interesante, por cierto), este " dentro del búfer " La técnica es algo similar a modelar la forma en cuestión a partir de una porción de azúcar que se disuelve con el ácido desde los bordes hacia adentro. (Por ejemplo, a medida que aumenta la distancia del amortiguador, 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 desafortunadamente no me queda muy claro ...
Creo que si rompes el polígono de nuevo en sus vértices, y luego aplicas una función para encontrar el casco convexo más grande, y luego encuentras el centro de ese casco convexo, coincidirá estrechamente con el " aparente " centro.
Encontrar el casco convexo más grande dados los vértices: Busque en el párrafo Polígono simple.
Promedio de los vértices del casco convexo para encontrar el centro.
¿Podría colocar la etiqueta en el centro ingenuo (del cuadro delimitador, quizás), y luego moverla en función de las intersecciones de los bordes del polígono local y el BB de la etiqueta? Mueva a lo largo de las normales de los bordes que se cruzan, y si se intersecan varios bordes, ¿sume sus normales para el movimiento?
Sólo adivinando aquí; en este tipo de problema, probablemente trataría de resolverlo de manera iterativa siempre que el rendimiento no sea demasiado preocupante.
No hay mucho tiempo para elaborar o probar esto ahora mismo, pero intentaré hacer más cuando tenga la oportunidad.
Usa los centroides como tu método primario. 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 al otro lado del polígono. En el punto medio de la sección de esa línea que está dentro del polígono, coloque su etiqueta.
Debido a que es probable que el punto más cercano al centroide se limite a 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, utiliza de forma predeterminada el método de centroide (¿rápido?) Para los casos típicos.
Este problema probablemente sería análogo a encontrar el " centro de masa " asumiendo una densidad uniforme.
EDITAR: este método no funcionará si el polígono tiene " agujeros "
puede usar el método del Centro de masa (o Centro de gravedad) que se usa en ingeniería civil, aquí hay un enlace útil de wikipedia:
