¿Cómo submuestrear un polígono 2D?

Question

Tengo polígonos que definen el contorno de los condados del Reino Unido.Estas formas son muy detalladas (de 10k a 20k puntos cada una), lo que hace que los cálculos relacionados (¿está el punto X en el polígono P?) sean bastante costosos desde el punto de vista computacional.

Por lo tanto, me gustaría "submuestrear" mis polígonos para obtener una forma similar pero con menos puntos.¿Cuáles son las diferentes técnicas para hacerlo?

Lo trivial sería tomar uno cada N puntos (por lo tanto, submuestreo por un factor N), pero esto parece demasiado "crudo".Preferiría hacer un promedio de puntos, o algo por el estilo.¿Algún consejo?

Answer 1

Me vienen a la mente dos soluciones:

1) dado que el mapa del Reino Unido es razonablemente cuadrado, puede optar por representar un mapa de bits con los condados.Asigne a cada uno un color específico y luego renderice los bordes con una línea negra de 1 o 2 píxeles de grosor.Esto significa que sólo tendrá que realizar el costoso cálculo interior/exterior si una muestra se encuentra en el borde.Cuanto mayor sea el mapa de bits, menos frecuente será que esto suceda.

2) simplificar los esquemas del condado.Puedes usar un recursivo. Ramer-Douglas-Peucker algoritmo para simplificar recursivamente los límites.Solo asegúrate de almacenar en caché los resultados.Tú puede También tenemos que resolver esto no para los límites completos del condado sino solo para los límites compartidos, para garantizar que no haya brechas.Esto podría resultar bastante complicado.

Answer 2

Aquí Puede encontrar un proyecto que se ocupe exactamente de sus problemas.Aunque funciona principalmente con un área "rellena" por puntos, puedes configurarlo para que funcione con una definición de tipo "perímetro" como la tuya.

Utiliza un enfoque de k vecinos más cercanos para calcular la región.

Muestras:

Aquí puede solicitar una copia del trabajo.

aparentemente ellos planea ofrecer un servicio en línea para solicitar cálculos, pero no lo probé y probablemente no se esté ejecutando.

¡HH!

Answer 3

Triangulación de polígonos debería ayudar aquí.Aún tendrás que verificar muchos polígonos, pero ahora son triángulos, por lo que son más fáciles de verificar y puedes usar algunas optimizaciones para determinar solo un pequeño subconjunto de polígonos para verificar una región o punto determinado.

Como parece que tienes todos los algoritmos que necesitas para polígonos, no sólo para triángulos, también puedes fusionar varios triángulos que sean demasiado pequeños después de la triangulación o si el número de triángulos aumenta demasiado.