Remplissage d'espace entre des lignes 2D aléatoires

23

Considérons une région (2D) remplie de lignes au hasard (suivant la figure). Nous sommes intéressés à remplir les espaces vides entre les lignes, y compris quatre bords de limite d'une manière:

0- maximiser la taille des colis;
1- la forme des colis de remplissage est alignée en carré horizontalement ou verticalement;
2- la forme du remplissage des colis est carrée, c'est-à-dire un alignement détendu ;
3- La forme de remplissage des colis est un quadrilatère. notre question d'origine

Donc, pour l'instant, il existe trois scénarios différents.
Notez que les lignes sont du [x1,y1,x2,y2]jeu de points de formulaire , des nombres réels.

[* * *] Les idées de solutions / algorithmes / extraits de code / etc possibles sont les bienvenues.

entrez la description de l'image ici


Mise à jour 1: Nous pourrions gérer une solution pour le premier cas: Les
entrez la description de l'image ici
étapes sont:
1- lignes
2- rastériser les lignes dans un bitmap
3- rechercher des cellules voisines pour chaque cellule de la couleur désirée (c'est-à-dire la même couleur) avec une fonction objective pour maximiser la zone, c'est-à-dire le nombre de cellules.

Cela fonctionne bien mais il ne couvre que le premier scénario et il est également lent.


Mise à jour 2:
Nous avons supposé que le lecteur connaissait le concept de remplissage d'espace-carrelage. Vous pouvez suivre le lien pour l'inspiration. Notez cependant que notre problème est différent. Comme nous ne remplissons pas l'espace vide au hasard et nous ne choisissons pas la taille au hasard. La solution doit être itérative. Dans tous les cas, il n'y a pas de limite au nombre de colis à monter. En effet, il appartient à l'utilisateur de limiter le nombre d'itérations, en choisissant par exemple une zone minimale pour les parcelles. Cela est évident dans l'exemple donné ci-dessus dans lequel nous avons discrétisé des lignes en pixels avec une taille spécifiée. Autrement dit, la procédure doit être exécutée jusqu'à ce que toute la zone vide soit remplie en respectant le critère, par exemple, la superficie maximale des parcelles.


Mise à jour 3:
résumé:
Une application consiste à découvrir la distribution de blocs de «roche» intacts extractibles dans une «mine» fortement fracturée. Cela pourrait être très utile pour de nombreux aspects , y compris la conception de forage, évaluation financière , etc.
Description:
Pour une mine de roche décorative (pierre) les produits qui sont les blocs de roches intactes coupées en cubes rectangulaires le prix dépend étroitement de la taille de la bloc. L'extraction d'un bloc à partir d'une zone appropriée, c'est-à-dire sans fracture majeure, sera souhaitée si la quantité de pièces restantes est aussi petite que possible. Habituellement, les petits morceaux de roches n'ont relativement aucune valeur économique et sont considérés comme des déchets.
La question dans ce post étudie les solutions à ce type de problème.

Une vue mathématique du problème peut être formulée comme suit:
2D: Trouvez tous les rectangles qui pourraient être extraits d'une région 2D donnée avec quelques lignes optimisées pour une plus grande taille de rectangle possible.
3D: trouvez tous les cubes rectangulaires qui pourraient être extraits d'une région 3D donnée avec certains sous-plans (mieux: polygones) optimisés pour une plus grande taille de bloc possible.


Comme cela fait partie d'une recherche en cours, certaines des questions posées dans les commentaires ci-dessous n'ont pas certaines réponses que nous pouvons apporter. Nous pensons que les informations fournies jusqu'ici sont en effet suffisantes pour obtenir une image globale du problème. Néanmoins, nous fournissons certains détails que nous pouvons pour les avantages pour la communauté.
Vous pouvez imposer certaines restrictions à la solution de la question ultime, bien que nous pensons qu'il soit toujours possible d'en ajouter d'autres plus tard. Par exemple, suivez ces instructions: {Cas 2D}
La meilleure taille d'un bloc (rectangle économiquement optimal) à extraire dans les conditions mentionnées ci-dessus, est 1x1 mdonnée 10x10 mpour la région dans l'exemple. Il s'agit d'une contrainte définie en fonction de la valeur économique. La taille minimale réalisable pour la coupe, etc., soit0.15x0.15 m; c'est donc la deuxième limite de taille.
entrez la description de l'image ici
La figure ci-dessus montre la fonction de valeur économique en fonction de la taille du bloc. Donc, pour ce cas particulier, chaque morceau de roche est plus petit que les 0.15x0.15 mdéchets. Il n'y aura pas de taille de bloc plus grande qu'en 1.7x1.7 mraison des limites de fonctionnement.

Développeur
la source
3
@RK - Je ne suis pas d'accord. Il / elle a déjà indiqué très clairement ce qu'ils recherchent. Bien sûr, il existe plusieurs solutions possibles, mais rien ne les empêche toutes d'être utiles et votées.
GIS-Jonathan
1
Comme il s'agit d'une question d'algorithme qui peut être assez lourde en mathématiques, vous voudrez peut-être essayer - math.stackexchange.com
GIS-Jonathan
1
Étroitement liés: gis.stackexchange.com/questions/27303 . La question actuelle, comme le note @RK, n'a pas de réponse définitive car elle n'est pas suffisamment bien posée. Combien de rectangles sont autorisés? Que signifie "maximiser la taille"? Notez également qu'il ne s'agit pas d'un problème de "pavage aléatoire": les lignes déterminent simplement, via leur complément, les zones pouvant être occupées; les solutions ne seront certainement pas aléatoires. Notez également qu'une simplification simple est immédiatement disponible: le problème peut être résolu séparément dans chaque composant du complément.
whuber
1
@whuber: Eh bien, une application qui nous intéresse est de découvrir la distribution de blocs de «roche» intacts extractibles dans une «mine» fortement fracturée. Eh bien, nous pensons que le SIG semble prometteur pour ce problème. Nous l'avons également ajouté à la question. Nous supposons que la communauté SIG peut bénéficier de l'idée de leurs autres problèmes particuliers connexes. Quoi qu'il en soit, c'est à vous de le migrer;)
Développeur
4
Comme @whuber le suggère, ce n'est pas vraiment une question SIG (bien que je ne sois pas offensé qu'elle soit posée ici.) Vous aurez beaucoup plus de chance d'obtenir une réponse dans un forum pour la géométrie ou l'optimisation informatique.
Llaves

Réponses:

2

J'ai une idée de la façon dont vous travaillez itérativement des gros blocs aux blocs plus petits en utilisant FME (par Safe Software.) Pour mémoire, je ne travaille pas pour eux mais semble féliciter suffisamment leur outil ...

  1. Utilisez "BoundingBoxReplacer" sur la zone d'intérêt.
  2. Reprojetez-le dans un système de coordonnées local (pour plus tard, lorsque vous aurez besoin de "carreler" en pieds / mètres.)
  3. Mettez les lignes en mémoire tampon avec le transformateur "Tampon". Vous avez seulement besoin d'une taille arbitraire, disons 0,01 ft / mètres. Ce que nous recherchons ici est un polygone de la ligne pour la prochaine étape.
  4. Ajoutez un transformateur "Tiler". Spécifiez une grande taille (estimée ou non) de tuile en pieds ou en mètres. Ce que nous faisons ici est de paver la zone d'intérêt en blocs carrés. En fonction de l'ensemble de données, commencez par grand pour vraiment obtenir les grandes valeurs aberrantes.
  5. Ajoutez un transformateur "Clipper". Ce que nous faisons ici est essentiellement de découper l'ensemble de données pour voir quelles tuiles sont bonnes / mauvaises. En sortie, les tuiles "Inside" sont trop grandes. Cependant, les carreaux "extérieurs" sont suffisamment grands et prêts à être coupés ...
  6. Voici où cela devient complexe, mais pas difficile ... Nous allons boucler le transformateur pour réutiliser la BoundingBox d'origine, mais couper les zones qui sont déjà prêtes pour la découpe. Donc, ajoutez un tondeuse et acheminez la tondeuse comme tuiles "Sortie" sur la sortie de tondeuse précédente. Nous avons maintenant un seul polygone prêt à fonctionner à nouveau.
  7. Utilisez à nouveau le carreleur, cette fois en spécifiant une tuile plus petite. Par exemple, si vous avez utilisé des tuiles de 100 mètres plus tôt, essayez de 90 mètres.
  8. Ajoutez un autre clipper, le clipper d'entrée étant les lignes tamponnées et le clippee d'entrée étant les plus petites tuiles en entrée.

Rincez et répétez autant de fois que nécessaire en utilisant des carreaux plus petits à chaque fois. J'ai attaché le début d'un établi que j'utiliserais comme une approche.

Sur la base de votre description (bien détaillée), cela ne fonctionnera qu'avec votre option 1 pour l'instant. Sans consacrer trop de temps pour l'instant.

Quoi qu'il en soit, ce n'est qu'une approche que je commencerais par au moins filtrer le blé de l'ivraie.

Exemple de tuile FME

Matthew Brucker
la source