Créer des polygones Thiessen (Voronoi) en utilisant des lignes (plutôt que des points) comme entités d'entrée?

24

J'ai un ensemble d'entités linéaires à l'intérieur d'une limite polygonale particulière. Pour chaque ligne, je voudrais générer un polygone à l'intérieur duquel chaque point possible est plus proche de la ligne donnée que de toute autre ligne de la couche. J'ai déjà fait cela dans le passé pour des entités ponctuelles en utilisant la triangulation de Delaunay, mais s'il existe un processus similaire pour le faire avec des entités linéaires, je n'ai pas pu le trouver.

ETA: La solution de Geogeek m'est venue à l'esprit, mais dans les sections plus droites où les lignes d'entrée ont moins de sommets, les polygones résultants se rapprochent trop (voire se chevauchent) d'une ligne qu'ils ne devraient pas. Ici, les lignes rouges sont mes entrées, vous pouvez voir les sommets et les polygones Thiessen générés à partir d'eux.

entrez la description de l'image ici

Une solution rapide et (très) sale pourrait être de convertir chaque ligne en un ensemble abondant de points régulièrement espacés (plutôt que les sommets de la ligne uniquement), de générer des polygones Thiessen à partir de ceux-ci, puis de les dissoudre en fonction de l'ID de la ligne d'origine.

Dan C
la source
4
Les diagrammes de Voronoi qui incluent des segments de ligne avec des points ne sont pas composés de "polygones"; leurs cellules ont plutôt des limites qui peuvent inclure des portions de paraboles. Pour cette raison, l'un des moyens les plus efficaces et les plus précis pour créer des pavages Voronoi est d'utiliser une représentation raster. ESRI appelle cette procédure l' allocation euclidienne .
whuber

Réponses:

11

Pour illustrer une solution de traitement d'images / raster, j'ai commencé avec l'image publiée. Il est de bien moindre qualité que les données d'origine, en raison de la superposition de points bleus, de lignes grises, de régions colorées et de texte; et l'épaississement des lignes rouges d'origine. En tant que tel, il présente un défi: néanmoins, nous pouvons toujours obtenir des cellules Voronoi avec une grande précision.

J'ai extrait les parties visibles des traits linéaires rouges en soustrayant le vert du canal rouge, puis en dilatant et en érodant les parties les plus brillantes de trois pixels. Cela a été utilisé comme base pour un calcul de distance euclidienne:

i = Import["http://i.stack.imgur.com/y8xlS.png"];
{r, g, b} = ColorSeparate[i];
string = With[{n = 3}, Erosion[Dilation[Binarize[ImageSubtract[r, g]], n], n]];
ReliefPlot[Reverse@ImageData@DistanceTransform[ColorNegate[string]]]

Terrain en relief

(Tout le code affiché ici est Mathematica 8.)

L'identification des «crêtes» évidentes - qui doivent inclure tous les points qui séparent deux cellules Voronoi adjacentes - et leur nouvelle combinaison avec la couche linéaire fournit la plupart de ce dont nous avons besoin pour procéder:

ridges = Binarize[ColorNegate[
   LaplacianGaussianFilter[DistanceTransform[ColorNegate[string]], 2] // ImageAdjust], .65];
ColorCombine[{ridges, string}]

Images combinées

La bande rouge représente ce que j'ai pu sauver de la ligne et la bande cyan montre les crêtes dans la transformation de distance. (Il y a encore beaucoup d'ordure en raison des ruptures dans la ligne d'origine elle-même.) Ces crêtes doivent être nettoyées et fermées par une nouvelle dilatation - deux pixels suffiront - et ensuite nous pouvons identifier les régions connectées déterminées par les lignes originales et les crêtes entre elles (dont certaines doivent être explicitement recombinées):

Dilation[MorphologicalComponents[
  ColorNegate[ImageAdd[ridges, Dilation[string, 2]]]] /. {2 -> 5, 8 -> 0, 4 -> 3} // Colorize, 2]

Ce que cela a accompli, en fait, est d'identifier cinq caractéristiques linéaires orientées . Nous pouvons voir trois entités linéaires distinctes émanant d'un point de confluence. Chacun a deux côtés. J'ai considéré le côté droit des deux fonctionnalités les plus à droite comme étant les mêmes, mais j'ai par ailleurs distingué tout le reste, en donnant les cinq fonctionnalités. Les zones colorées montrent le diagramme de Voronoi à partir de ces cinq caractéristiques.

Résultat

Une commande d'allocation euclidienne basée sur un calque qui distingue les trois entités linéaires (que je n'avais pas disponible pour cette illustration) ne distinguerait pas les différents côtés de chaque entité linéaire, et combinerait donc les régions verte et orange encadrant la ligne la plus à gauche ; cela diviserait la fonction sarcelle la plus à droite en deux; et il combinerait ces pièces fendues avec les caractéristiques beige et magenta correspondantes de leurs autres côtés.

De toute évidence, cette approche raster a le pouvoir de construire des pavages Voronoï d'entités arbitraires - des points, des pièces linéaires et même des polygones, quelles que soient leurs formes - et elle peut distinguer les côtés des entités linéaires.

whuber
la source
1
Une solution similaire est illustrée sur mathematica.stackexchange.com/questions/20696/… .
whuber
5

Je pense que vous pouvez:

  • Convertissez les sommets des lignes en points (line_points).
  • Créez des polygones voronoi en utilisant les points (line_points).
  • Dissolvez les polygones résultants en utilisant soit un attribut id qui a été enregistré à partir de la couche de ligne, soit par une jointure spatiale avec la couche de ligne.

J'espère avoir vraiment compris votre question, sinon pouvez-vous fournir un dessin pour expliquer davantage vos besoins.

geogeek
la source
2
Je pense que vous l'avez compris, et cette solution m'est venue à l'esprit, mais vous rencontrez des problèmes où les lignes ont moins de sommets. Je mettrai à jour ma question avec une capture d'écran.
Dan C
3
Cela fonctionnerait bien si vous rendiez les points plus denses le long de la ligne. Bien qu'une approche basée sur une trame (comme le mentionne Whuber dans les commentaires sur la question), je suppose que ce serait beaucoup plus efficace que cela.
Andy W