[Spanish] Algoritmo como Voronoi, pero para polígonos

[Iván Sánchez Ortega]

A las buenas.

Tengo un problema, pero no sé exactamente cómo solucionarlo. A ver:

Seguro que os es familiar el algoritmo de Voronoi: tú le das un conjunto de 
puntos, y te devuelve un conjunto de polígonos[1], y la propiedad importante 
es que para cada punto de la entrada existe un polígono que contiene todos los 
puntos del plano[2] para los cuales la distancia al punto de la entrada es 
menor que la distancia de ese punto del plano[2] a cualquiera del resto de 
puntos de la entrada.

Hasta aquí bien.



¿Pero qué pasa cuando mi conjunto de datos de entrada no son puntos, sino 
líneas (o multilíneas) y polígonos (o multipolígonos)?



El problema es que si se aplica el algoritmo para puntos, el paso de la 
triangulación se "come" algunas aristas. Por ejemplo, en 
http://postgis.net/docs/ST_DelaunayTriangles.html , desaparece el lado más 
largo del triángulo.

Supongo que si hubiera alguna manera de forzar que el algoritmo de la 
triangulación respete las geometrías existentes (o forzar que se use un 
conjunto de aristas predeterminado), no habría mucho problema. Pero no sé si 
esto se puede hacer, o cómo.



¿Una audita, por el amor del MEV?



[1] Algunas implementaciones devuelven el conjunto de puntos inicial y un 
conjunto de aristas y un conjunto de polígonos y relaciones topológicas entre 
todo ello)

[2] O del geoide



-- 
Iván Sánchez Ortega <ivan en sanchezortega.es> <ivan en geonerd.org> 
<ivan en mazemap.no>