Trouver le contour d'une union de carrés alignés sur la grille

Comment obtenir les coordonnées de la forme de contour formée en utilisant des blocs de grille plus petits. Par exemple, Si j'ai utilisé des blocs d'unités de 32x32 pour construire une forme (n'importe quelle forme)Trouver le contour d'une union de carrés alignés sur la grille

Ensuite, comment puis-je obtenir les coordonnées globales de la forme, y compris les espaces négatifs.

Par exemple: On pourrait organiser les blocs comme celui-ci: (chaque bloc est 32x32 et les coordonnées se réfèrent au coin inférieur gauche du bloc)

Block 1 - (0,0) 
BLock 2 - (32,0) 
Block 3 - 64,0) 
Block 4 - (64,32) 
Block 5 - (64, 64) 
BLock 6 - (32, 64) 
BLock 6 - (0 64) 
Block 7 - (0, 32)

Maintenant, vous pouvez voir cela va créer un espace vide au milieu.

Donc ce que je voudrais savoir est, comment obtenir les coordonnées de la forme ci-dessus telle que je reçois:

Main Block = (0,0), (96,0), (0,96) 
Empty space = (32,32), (64,32), (64,64), (32,64)

Y at-il une solution mathématique à cela?

Finalement, je vais faire des formes complexes.

grâce

******** modifier **** Salut,

Comment traiter cette condition?

<------------------^<----^ 
|     || | 
V------------------>| | 
<------^   /^| | 
|  |<------^/|| | 
|  ||  |/ || | 
V------>V------>V-->V---->

je voudrais que le résultat soit comme celui-ci

<-------------------<----^ 
|      | 
V  ^----------->  | 
|  |  / | 
|  <-------^/  | 
|    |/  | 
V------>------->--->----->

Source

2010-08-17 ssdesign

Vous voulez regarder la théorie des ensembles. – leppie

<-----^ 
|  | 
|  | 
V----->

Donc pour tous les carrés de votre forme, prenez l'union de leurs vecteurs de contour. Si deux vecteurs de contour dans l'union sont identiques mais vont dans des directions opposées, ils s'annulent et sont retirés de l'union.

Par exemple, pour deux carrés qui sont côte à côte l'union est de 8 vecteurs

<-----^<-----^ 
|  ||  | 
|  ||  | 
V----->V----->

qui réduit à 6 vecteurs parce que les deux vecteurs verticaux dans le milieu annuler:

<-----<-----^ 
|   | 
|   | 
V----->----->

Pour l'exemple que vous avez donné, le résultat de ceci sera (après les annulations):

<-----<-----<-----^ 
|     | 
|     | 
V  ^-----> ^
|  |  |  | 
|  |  |  | 
V  <-----V ^
|     | 
|     | 
V----->----->----->

Yo Il suffit de connecter les vecteurs dans l'union finale réduite pour lire les chemins de contour. Notez que le contour interne ("le trou") tourne dans le sens des aiguilles d'une montre.

Source

2010-08-17 15:11:54 brainjam

Salut, Cela semble très prometteur. Fondamentalement, j'essaie de le faire avec PHP Arrays. Je n'ai pas encore trouvé de classe Vector pour PHP. btw. Une idée de comment identifier les boucles fermées qui sont dans le sens des aiguilles d'une montre et les séparer des boucles dans le sens inverse des aiguilles d'une montre? – ssdesign

WIll cette logique fonctionne même si les spahes sont de forme étrange? Par exemple. Et si la seconde forme était un rectangle (la moitié de la hauteur du premier carré). – ssdesign

@ssdesign, vous n'avez pas vraiment besoin d'une classe Vector, juste quelque chose qui indique les points de début et de fin, ou point de départ + direction + longueur. Vous pouvez rechercher StackOverflow pour les tests qui distinguent dans le sens horaire ou antihoraire. En ce qui concerne les formes impaires, je suppose que vous pouvez avoir des vecteurs qui s'annulent partiellement - donc 1.0up + 0.5down = 0.5up. – brainjam

Vous auriez probablement besoin de se concentrer sur Boolean Polygon Operations, les syndicats dans votre cas. Il y a beaucoup de papiers couvrant les opérations de polygones booléens 2D et la géométrie planaire constructive, voir Wikipedia: http://en.wikipedia.org/wiki/Boolean_operations_on_polygons. Pensez à chaque carré comme un contour composé de quatre vecteurs allant dans une chaîne dans le sens antihoraire.

Source

2010-08-17 11:15:37 mbaitoff

Trouver le contour d'une union de carrés alignés sur la grille

Répondre

Questions connexes