Algorithme pour calculer la couverture + les chevauchements à partir d'un ensemble d'arcs

10

J'ai un fichier de formes contenant des arcs représentant le chemin parcouru par un camion d'épandage d'engrais sur une ferme.

Disons que je sais que la largeur d'épandage est de 30 m, c'est-à-dire que le camion peut épandre de l'engrais sur 15 m de chaque côté du véhicule.

Je veux générer un ensemble de polygones, qui montrent:
1) La superficie totale qui a reçu de l'engrais
2) Les zones de chevauchement, c'est-à-dire où deux passes distinctes étaient trop rapprochées, de sorte que certaines parties de la ferme ont reçu deux fois la «dose correcte» "d'engrais.

Une approche naïve consiste simplement à créer les polygones de couverture sous forme de tampons autour des arcs. Cela fonctionne dans le cas particulier où les lignes de propagation sont distinctes les unes des autres. Cependant, le camion pourrait éventuellement voyager autour de la ferme dans une spirale toujours décroissante, et un simple tampon ne montrerait pas les chevauchements où deux passages de la spirale étaient trop proches l'un de l'autre (si la spirale est un seul arc, je finirais avec un seul polygone sans parties superposées).

Si c'est pertinent, j'utilise le TatukGIS VCL DK, mais je recherche vraiment un algorithme plutôt qu'une solution spécifique.

Quelques clarifications en réponse à la discussion jusqu'à présent:

1) Je ne peux pas compter sur les données vectorielles ayant des métadonnées particulières (par exemple, les journaux GPS ou le taux de propagation). J'autorise l'utilisateur à choisir une couche et à spécifier une largeur de diffusion, puis le rapport s'exécute.

2) Le rapport a vraiment pour but de montrer à l'utilisateur à quel point le conducteur du véhicule était "qualifié", où "qualifié" signifie "atteint la couverture la plus élevée avec le plus faible chevauchement".

3) Je suis plus à l'aise dans les terrains vectoriels que dans les terrains matriciels, je préférerai donc les solutions vectorielles.

Merci,

Darren.

algorithm polygon-creation dbruning
la source
1
Je me demande si cela serait similaire aux méthodes qui prédisent les précipitations cumulées en fonction des trajectoires de tempête prévues.
Kirk Kuykendall,

Réponses:

3

La solution la plus simple est peut-être de diviser la géométrie unique en segments et de tamponner ces segments individuels: dans votre cas en spirale, vous tamponneriez chaque arc, puis couperiez les arcs individuels pour obtenir un compte. Veillez à éviter les faux chevauchements en ne tamponnant pas les extrémités des segments, uniquement à gauche et à droite des segments eux-mêmes.

Une autre approche consiste à superposer une grille polygonale sur les données, puis à l'intérieur de chaque cellule de la grille, tamponner séparément chaque segment de ligne se croisant. Pour être précis, vous voudriez prendre la cellule de la grille en cours d'analyse, la tamponner, puis collecter les segments qui se croisent et les tamponner, en effectuant votre analyse dans la fenêtre de cellule d'origine.

L'une ou l'autre de ces options devrait vous donner une estimation raisonnable du chevauchement, je peux penser à quelques approches plus précises, mais elles nécessiteraient de savoir quelque chose sur les données.

scw
la source
Merci. Je pensais dans le sens de votre première suggestion - diviser la géométrie en segments et les mettre en mémoire tampon. Je pense que je devrai également tamponner les extrémités des segments, afin d'obtenir des bords arrondis dans les coins. En pensant au cas où je commence par une ligne à angle droit - si je ne tamponne pas les extrémités, je finirai avec deux rectangles qui se chevauchent avec un carré manquant à l'extérieur du coin (difficile à exprimer sous forme de texte!)
dbruning le
Je pense que je devrai également tamponner les extrémités des segments, afin d'obtenir des bords arrondis dans les coins. Je pensais en outre à couper le tampon de chaque segment avec le tampon du segment précédent, puis à accumuler uniquement les "nouvelles" parties de chaque tampon dans un tampon maître. L'idée étant d'ignorer les chevauchements avec le segment précédent mais le ramassage chevauche avec des segments plus anciens.
dbruning le
2

Pas de solution, mais quelques entrées:

Ce problème semble similaire au problème de détection de coalescence de ligne dans la généralisation de cartes . Cela se produit lorsqu'un grand style est appliqué sur une ligne sinueuse (le symbole se chevauche automatiquement):

entrez la description de l'image ici

Ce document pp. 176 à 180 (en français ... désolé) donne des algorithmes pour détecter de telles parties auto-entrecroisées. Le principe est, comme proposé par scw , d'utiliser un seul tampon latéral de chaque segment composé d'un segment plus 0, 1 ou 2 arcs de cercle. JTS contient une implémentation de ce tampon simple côté qui peut être utile.

julien
la source
Pourquoi êtes-vous préoccupé par la détection des auto-intersections? Et pourquoi proposez-vous des tampons "simple face"? Aucun des deux ne semble pertinent au problème.
whuber
Le but est de détecter où le camion répand plusieurs fois de l'engrais, c'est-à-dire là où la zone d'épandage s'auto-intersecte.
julien
2

Une solution vectorielle va manquer une variable potentiellement critique : le temps et, à travers elle, le taux de propagation. Lorsque le tracteur se déplace plus rapidement, moins d'engrais est répandu par unité de surface et lorsqu'il se déplace plus lentement (décélérant dans un virage et accélérant hors d'un), il épandra plus d'engrais par unité de surface. De plus, si le tracteur épand du matériau pendant le virage, le matériau sera plus concentré vers l'intérieur du virage et moins concentré vers l'extérieur.

Les données de temps seraient disponibles dans un enregistrement GPS de la progression du tracteur. Les pentes (distance parcourue divisée par le temps écoulé) estimeront les vitesses en chaque point. Alternativement, on pourrait (en tant qu'approximation) supposer une vitesse constante à l'intérieur d'un champ et une vitesse plus lente dans un tampon interne raisonnable de la limite du champ.

Une représentation raster peut gérer ces problèmes. Rastérisez la trajectoire du tracteur. Cela définit toutes les cellules non traversées par le tracteur sur des valeurs NoData (ou sur zéro). Si le tracteur devait se déplacer à une vitesse standard et constante, il suffirait de mettre une valeur constante dans chacune des cellules de données. Maintenant, par exemple, si le tracteur se déplaçait à deux fois cette vitesse, (vraisemblablement) son taux d'application serait divisé par deux, et cela peut être représenté en divisant par deux la valeur dans les cellules.

En général, la valeur à mettre dans n'importe quelle cellule est le taux d'application par unité de surface . Si le tracteur distribue uniformément x Kg d'engrais par seconde sur 15 m de chaque côté tout en se déplaçant à une vitesse de y m / sec, il épand de x / y Kg / sec / [m / sec] / (2 * 15 m) = x / (30 y ) Kg / m ^ 2 d'engrais. Ainsi, x / (30 y ) est la valeur à mettre dans chaque cellule. x est donné et y est calculé à partir des données GPS.

Les auto-intersections ne posent en principe aucun problème . Si le chemin du tracteur se croise, ajoutez les contributions chaque fois qu'il recroise une cellule. Cela peut nécessiter un traitement spécial pour ce faire, selon la façon dont la grille est créée et les capacités du logiciel SIG.

Après avoir fait cette préparation, le reste est rapide et facile: une somme focale de cette grille, en utilisant un voisinage circulaire avec un rayon de 15 m, trouve la quantité cumulée répartie par unité de surface dans chaque cellule.

whuber
la source
1
+1 il semble que si vous aviez un outil qui permettait à un noyau (représentant le tracteur) de se déplacer le long d'un chemin (au lieu de le long de chaque rangée), ce problème serait plus gérable.
Kirk Kuykendall
@Kirk Il n'est pas nécessaire de suivre un chemin ou des lignes ou autre avec un noyau. Il est important d'apprécier le changement de point de vue qui accompagne une somme focale: au lieu de considérer le problème comme un problème de diffusion de matière à partir d'un chemin de points, regardez-le comme un calcul de la quantité de matière qui s'accumule à chaque point du champ . Évidemment, c'est le même problème avec la même solution. L'approche par noyau mobile (et les approches de mise en mémoire tampon proposées) adopte le premier point de vue; la somme focale, la seconde. Mais l'outil de somme focale est disponible; un calcul de noyau mobile ne l'est pas.
whuber
Je pense que l'approche tramée que vous décrivez serait la meilleure méthode si nous connaissions la vitesse et le taux de propagation. Malheureusement, dans ce scénario particulier, nous ne savons pas non plus. Notre utilisateur final peut choisir n'importe quelle couche comme entrée dans ce rapport de couverture, et nous ne pouvons pas compter sur la géométrie ayant des métadonnées particulières.
dbruning le
@dbruning Cette approche ne semble pas nécessiter de vitesse / taux de propagation connus; il permet juste pour eux (+ le modèle de réalité plus précis) si vous les avez. Cependant, cela nécessitera également un certain seuil + comptage des cellules pour obtenir les mesures que vous souhaitez (couverture totale de la zone; zone de chevauchement) du système, et des compromis de précision sont également mélangés.
Dan
@dbruning Si vous ne connaissez pas le taux de spread, vous obtiendrez un taux de spread relatif. Si vous ne connaissez pas la vitesse, vous savez (ou devriez savoir) comment les gens conduisent des tracteurs et vous devriez pouvoir obtenir des estimations raisonnables des vitesses relatives. Si vous supposez des vitesses et des taux de propagation constants, vous obtiendrez toujours des réponses raisonnables; ils seront d'accord avec les réponses basées sur les tampons sur des portions droites des itinéraires des tracteurs; et ils sont susceptibles d'être plus réalistes dans les parties courbes.
whuber
2

Je ne suis pas sûr à 100% du protocole StackExchange, donc je poste ceci comme une réponse à ma question. C'est la réponse que j'ai finalement utilisée de toute façon.

L'algorithme de base est le suivant:
1. Décomposer toute géométrie du calque en segments ne dépassant pas la moitié de la largeur de propagation.
2. Pour chaque segment:
- Créez un "tampon de défilement" en regardant en arrière le long de la forme et en tamponnant tous les segments précédents où la longueur cumulée de ces segments est inférieure à la largeur d'étalement (rayon du tampon = 1/2 largeur d'étalement)
- Créez un "tampon de segment suivant" uniquement du segment suivant (rayon du tampon = 1/2 largeur de propagation)
- Soustrayez le "tampon de roulement" du "tampon de segment suivant" pour obtenir le "nouveau tampon"
- joignez tous les "nouveau tampon" polygones ensemble pour obtenir un seul polygone par forme.

Essentiellement, cela permet au conducteur du véhicule épandeur de faire des virages à angle droit (ou plus larges) sans pénalité de chevauchement, mais s'ils reviennent trop brusquement pour se propager sur "l'ancien terrain", nous commençons à obtenir des chevauchements.

Chevauche en bleu

La spirale ressemble à ce que je veux:

spirale

dbruning
la source