Vous cherchez un algorithme pour placer le nombre maximum de points dans la zone contrainte à un espacement minimum?

17

J'ai une couche polygonale qui décrit une contrainte; Je souhaite ajouter des points dans ce domaine. Je veux ajouter autant de points que possible, mais ils doivent avoir un espacement minimum entre eux. Est-il possible de le faire avec le SIG?

Pour clarifier, il serait préférable de générer une grille ordonnée, car cela garantirait le plus de points. Cependant, la contrainte le permet rarement, et il peut être préférable de supprimer des points pour permettre à un décalage de mieux s'adapter à la contrainte.

algorithm point Matthew Snape
la source
1. Oui. 2. Voulez-vous aléatoire ou ordonné (grille)?
Brad Nesom
Semble être deux questions. Voulez-vous qu'un algorithme le fasse en dehors du logiciel? Ou voulez-vous savoir quel système SIG peut faire cela?
Brad Nesom
1
Les points sont-ils contraints de sorte qu'ils doivent être> = la distance minimale de la limite du polygone? Si c'est le cas, la question pourrait être formulée plus clairement: comment puis-je regrouper le nombre maximum de cercles dans un polygone?
Kirk Kuykendall
D'une manière ou d'une autre: gis.stackexchange.com/q/4927/162
julien
1
@qva Non, car les solutions exactes qui peuvent être trouvées sont asymétriques et difficiles à obtenir même pour des formes simples comme les rectangles. Les meilleures méthodes de calcul que j'ai trouvées sont basées sur le recuit simulé spatial (et elles fonctionnent très bien, même si elles nécessitent beaucoup de calculs). En les utilisant, j'ai cherché des solutions pour de nombreux polygones de formes variées. Il est clair que les limites des polygones contrôlent les solutions proches des limites; profondément à l'intérieur, ils ont tendance à se rapprocher des emballages hexagonaux de disques.
whuber

Réponses:

5

Je pense que cela pourrait être considéré comme un problème "d'emballage".

Si c'est le cas, vous voudrez peut-être essayer un algorithme génétique, peut-être similaire à celui de On Genetic Algorithms for the Packing of Polygons .

Kirk Kuykendall
la source
Référence intéressante, merci. Un rapide coup d'œil suggère que l'algorithme du papier a besoin que les polygones soient des rectangles. Savez-vous s'il peut être généralisé à des polygones arbitraires?
whuber
9

Je ne connais aucun outil SIG pour le faire, mais j'ai une idée sur l'algorithme.

Tout d'abord, une approximation du nombre maximal de points peut être obtenue avec cette formule:

Nb = 4.A / Pi.d^2

(où Aest la zone du polygone et dla distance d'espacement minimale).

Ensuite, pour essayer de localiser ces points dans le polygone, le meilleur motif n'est pas la grille carrée mais la grille hexagonale. Voir:

carré vs grille hexagonale

Enfin, certaines techniques d'optimisation utilisant des modèles de force pourraient être utilisées pour affiner le positionnement relatif des points.

NB: C'est un problème bien connu en cristallographie .

julien
la source
outil gis pour le faire ... ian-ko.com géo-assistant point aléatoire dans le polygone.
Brad Nesom
1
Merci! Mais la question ne concerne pas exactement les points aléatoires du polygone, non?
julien
Comme approximation initiale rapide et sale, l'emballage hexagonal fonctionne bien. Mais ce n'est presque jamais optimal. Je m'attendrais à ce que l'amélioration potentielle soit proportionnelle à la longueur du périmètre du polygone, donc pour les polygones non tortueux avec de nombreux points, ce n'est pas une mauvaise approche.
whuber
6

Voir le fil à /math/15624/distribute-a-fixed-number-of-points-uniformly-inside-a-polygon . Noter en particulier la référence (dans un commentaire) au "processus de disque de Poisson" et faire quelques recherches sur le Web. Le lien avec la question actuelle est que lorsque vous pouvez répartir uniformément un nombre donné de points, vous pouvez systématiquement augmenter ce nombre jusqu'à ce qu'il ne soit plus possible de placer de points dans le polygone, ce qui résout le problème de la maximisation du nombre de points soumis à un exigence de distance minimale. (Techniquement, les deux problèmes sont des problèmes de double optimisation où les objectifs et les contraintes sont échangés.)

whuber
la source
0

La solution doit être des triangles équilatéraux, http://en.wikipedia.org/wiki/Equilateral_triangle . La seule question est la longueur des côtés et le "décalage xy" par rapport à votre polygone.

(identique à la grille hexagonale mentionnée ci-dessous)

Uffe Kousgaard
la source
1
Cela n'est vrai que dans un plan infini. La limite d'un polygone fini contraint sévèrement la configuration. Lorsqu'il y a beaucoup de points, ils forment approximativement des triangles équilatéraux.
whuber