Discussion :

[Ouaibou]

Bonjour,

Je m'intéresse au problème suivant:

Soit des zones définies par deux coordonnées: une minimum (borne incluse) et une maximum (borne exclue) comme illustré. La figure ci-dessous illustre le cas pour la zone B.



Les zones font parti d'un espace fini. J'essai d'élaborer un algorithme qui permet de savoir si deux zones se touchent sur une dimension donnée: par exemple B touche A et D mais pas C. Mon but est de réaliser un algorithme qui puisse être appliqué pour un espace à N dimensions. C'est-à-dire que j'ai toujours deux coordonnées qui permettent de délimiter les zones et chacune des coordonnées aura N composantes, une pour chaque dimension.
Ainsi par exemple pour un espace à 3 dimensions, une zone sera représentée par un cube et le problème consiste à savoir si pour une dimensions donnée (donc sur un plan) deux cubes sont voisins. Pour cela j'ai réalisé l'algorithme suivant (dans mon cas, les dimensions sont numérotées à partir de 0: 0 pour x, 1 pour y, etc.). Après quelques essais dans un espace à deux dimensions, l'algorithme semble fonctionner.

Mon problème est que je n'ai aucune idée si mon algorithme fonctionne à N dimensions et au dessus de 2 dimensions il est vraiment pas évident de faire des essais. Quelqu'un voit il une erreur dans mon algorithme et/ou connaitrait il un algorithme qui répond au problème sur N dimensions?

Voici mon algorithme écrit en Java, j'ai mis ici uniquement la méthode essentielle de la classe Zone:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public boolean isAbutsWith(Zone zone, int dimension) {
       boolean dimResult = false;
       boolean borderResult = false;
 
       for (int dim = 0; dim < NB_DIMENSIONS; dim++) {
           if (dim == dimension) {
               dimResult =
                   !this.getCoordinateMin(dim).equals(zone.getCoordinateMax(dim))
&& !this.getCoordinateMax(dim).equals(zone.getCoordinateMin(dim));
           } else {
               borderResult |=
                   CoordinateValue.isBetween(
                            this.getCoordinateMin(dim),
                            zone.getCoordinateMin(dim),
                            zone.getCoordinateMax(dim))
                   ||
                    CoordinateValue.isBetween(
                            this.getCoordinateMax(dim),
                            zone.getCoordinateMin(dim),
                            zone.getCoordinateMax(dim)))
                   ||
                   CoordinateValue.isBetween(
                             zone.getCoordinateMin(dim),
                             this.getCoordinateMin(dim),
                             this.getCoordinateMax(dim))
                   ||
                   CoordinateValue.isBetween(
                             zone.getCoordinateMax(dim),
                             this.getCoordinateMin(dim),
                             this.getCoordinateMax(dim));
           }
       }
 
       return dimResult && borderResult;
   }

Je suis ouvert à toutes idées

Merci.

[Invité]

Bonjour,
Moi, j'aurais plutôt une autre approche.
Chaque figure en N dimensions est caractérisée par son centre (moyenne des 2 points) et le demi côté dans les N dimensions.
Deux figures se touchent si la distance entre leurs centres est inférieure à la somme des 1/2 côtés correspondants.
Le carré de la distance entre les centres est la somme des carrés des différences de coordonnées.
D² = somme (dx² + dy² + dz² + ...)
La somme des 1/2 côtés, n'est pas tout à fait claire dans mon esprit, la plus petite somme ? la plus grande somme ? pour l'instant, je ne sais pas.
Il y 2 cas limite à étudier :
1- les figures sont strictement accolées par une "face" c'est à dire que toutes les coordonnées des points sont identiques, sauf une et leur différence est égale à la somme des 1/2 cotés correspondants.
2- l'autre cas c'est quand le point A(min) d'une forme est identique au point B(max) de l'autre forme. Dans ce cas D² = somme (1/2 côtés au carré).

Après réflexion, au lieu de calculer la "distance" euclidienne, il est peut être plus simple pour le test de calculer la distance telle D= somme (dx, dy, dz, ...). Faites une recherche de distance dans Wikipédia, j'ai lu un article. .

[plegat]

+1 avec l'approche de Pierre.

Par contre, au lieu de calculer une distance euclidienne, partir directement sur les distances par composante (ou dimension), et comparer à la somme des demi-longueurs pour chaque composante. Si c'est strictement inférieur, ça s'intersecte, si au moins un test est égal (à un epsilon près, attention aux nombres décimaux en informatique...), ça se touche, si au moins un test est strictement supérieur, pas de contact.

[Invité]

@plegat,
Là j'en rougi de plaisir