Este problema tiene muchas soluciones válidas. Una de ellas funciona un poco como tu descripción, pero en lugar de cortar los polígonos en lugares "aleatorios" puedes hacerlo a propósito de una manera diseñada para minimizar la cantidad de computación.
Este es el algoritmo básico. Su entrada consiste en cualquier dirección de barrido del plano, un polígono P de área no nula, un área objetivo a entre cero y el área del polígono, y un umbral no negativo t (en unidades de superficie). Su objetivo es dividir P con una línea perpendicular a la dirección de barrido en dos partes, una a la derecha de la línea y otra a la izquierda de la línea, de manera que la diferencia entre el área de la derecha y el área del objetivo a no es mayor que t .
Dejemos que L sea cualquier línea orientada perpendicular a la dirección de barrido. Definir f(L) como el área de P encontrada a la derecha de L, menos a . En estos términos, la tarea consiste en encontrar un cero de f . Porque f es poco probable que sea diferenciable, pero es continua, utilice un método de bisección, el método secante o mi favorito -El método de Brent . Todos son sencillos y garantizan la convergencia. Utilice t para la tolerancia de convergencia del argumento.
Eso es. Consideremos lo que supone codificar esto. El hallazgo de la raíz es rutinario - se puede utilizar un trozo de código genérico para ello - por lo que el trabajo del SIG se reduce a la codificación f . Para ello es necesario
1. Splitting the polygon by a line.
2. Computing the area of the piece(s) to the right of the line.
Ambas operaciones se implementan en casi cualquier SIG basado en vectores. Si no es así, puede sustituir la línea por un rectángulo muy grande que represente el semiplano a la derecha de la línea. El paso 1 se convierte en
1'. Clip the polygon to the rectangle.
Esto es un realmente funcionamiento básico.
Para empezar con la búsqueda de raíces, hay que encontrar un intervalo en el que el cero de f está garantizada la mentira. Esto es fácil: proyectar la envoltura del polígono ("bounding box") en la dirección del barrido de líneas. La proyección es el intervalo que desea.
Esta cuestión tiene una larga historia. Implementé este algoritmo para ArcView 3.x hace mucho tiempo y lo describí muchas veces en los antiguos foros de usuarios de ESRI. Google
huber split polygon site:forums.esri.com
para discusiones, enlaces al código, mejoras y variaciones (como la división de polígonos en partes de tamaños deseados que sean lo más compactos posible) y algoritmos para datos raster.
Este es el aspecto de los estados continentales de EE.UU. (en una proyección de área igual) con el tercio inferior de cada estado sombreado. Evidentemente, la dirección de barrido era vertical.
![alt text]()
