8
votes

Coupure un rectangle en JavaScript

J'essaie d'écrire une fonction qui prend deux rectangles superposés et renvoie une gamme de rectangles qui couvrent la zone de rectangle A, mais d'exclure la zone de rectangle B. J'ai du mal à déterminer ce que cet algorithme ressemble Comme étant donné que le nombre de collisions possibles est énorme et difficile à rendre compte.

TL; DR J'essaie de couper un rectangle à l'aide d'un autre rectangle entraînant une collection de rectangles couvrant la zone restante. P>

|-------------|                               |-------------|
|A            |                               |R1           |
|     |-------|----|                          |-----|-------|
|     |B      |    |           To             |R2   |
|     |       |    |          ====>           |     |
|     |       |    |                          |     |
|-----|-------|    |                          |-----|
      |            |
      |------------|

POSSIBLE OVERLAP PATTERNS

|-----|          |-----|      |-----|        |-----|
| |---|-|      |-|---| |      | |-| |        | |-| |
|-|---| |      | |---|-|      |-|-|-|        | |-| |
  |-----|      |-----|          |-|          |-----|

  |-|          |-----|          |-----|
|-|-|-|        | |---|-|      |-|---| |
| |-| |        | |---|-|      |-|---| |
|-----|        |-----|          |-----|

javascript math geometry 2d

3 commentaires

Cela pourrait être réalisable d'utiliser les points de sommet pour cela. Vous pouvez calculer les nouveaux coordonnées rectangnés en fonction de la distance entre les points de vertex de A.

Il y a un autre problème, le résultat parfois plus d'un rectangle. entre un et neuf je pense.

Il existe sûrement un algorithme standard? De toute façon; une idée. Il y a 4 coordonnées x et 4 y des coordonnées, vos nouvelles zones seront toujours une combinaison de ceux-ci. Les 4 x coordons divisent la toile en 5 bandes verticales, les coordonnées y dans 5 bandes horizontales, si le pire vient au pire, il y a 25 rectangles non chevauchants appartenant à A, B, ni ni les deux. Vous gardez ceux qui appartiennent à un seul et excluent tous les autres.

3 Réponses :

5
votes

Les deux rectangles divisent l'écran dans 9 zones (pas 14). Réfléchissez à nouveau de vos configurations:

  |-----|-------|----|       
  |A    |A      |none| 
  |-----|-------|----|   
  |A    |Both   |B   |   
  |     |       |    |   
  |     |       |    |   
  |-----|-------|----|   
  |none |B      |B   |
  |-----|-------|----|

1 commentaires

Merci, ceci est très utile. À votre santé!

4
votes

Il n'y aura pas de solution unique pour une configuration particulière, mais vous pouvez facilement trouver l'une des solutions avec cet algorithme:

Recherchez un rectangle dans un rectangle B. Si le sommet d'A est supérieur à B (c'est-à-dire une valeur inférieure à PX), il y a un tel rectangle. Ce rectangle est défini par: (bord gauche d'un bord supérieur d'A) à (bord droit d'un, bord supérieur de B).
Si le bord gauche de B est à droite du bord gauche de A, le rectangle suivant est: (bord gauche d'A, min (bord supérieur d'un, bord supérieur de B)) à (bord gauche de b , max (bord inférieur d'un bord inférieur de b))
Si le bord droit de B est à gauche du bord droit de B, similaire à ci-dessus
... et le rectangle possible ci-dessous B
Au total, vous obtiendrez de 0 à 4 rectangles.
pseudocode avec un peu inhabituel, mais à cet effet clair, définition du rectangle: xxx

5 commentaires

Il y a des cas non couverts - par ex. Si B est plus large que A et coupe un en deux ...

@boivevert, il est couvert. Toutes vos neuf régions sont entièrement couvertes. Pas mathématiquement élégant comme votre explication, mais avec un algorithme très simple.

Oups ... Je n'ai pas fait attention à votre utilisation de min et max. Vous avez raison, ça fonctionne très bien. Ne vois rien d'inélégant à ce sujet non plus.

Ceci est plutôt élégant. Merci d'avoir enfreint ce problème. C'est grandement apprécié.

@ Dan.P, il y a un détail à gauche ... Si les rectangles ne se chevauchent pas, les régions coupées sont trop grandes. Vous devez utiliser min / max d'autres.

1
votes

Travailler du code de Dan.P, en utilisant la suggestion de Boisvert, ma routine ressemble à ceci: xxx

J'ai testé avec 16 cas (pour quatre ifs indépendants). < / p>

0 commentaires