Partage

Comparer deux aires

1 2 >>

Sujet résolu

18 mars 2011 à 15:20:30

Bonjour,

Mon problème est plus algorithmique qu'au niveau du développement.
J'explique rapidement ce que j'essaie de faire. Mon but est d'afficher des mots à des positions aléatoires. Ca j'y arrive. Chaque mot est dans un <span>.
Le problème c'est que comme les positions sont aléatoires, il arrive que certains mots se recouvrent. Pour éviter cela j'effectue un certain nombre de vérifications:
- je compare chaque coin du span (rectangle) pour savoir s'il est dans l'aire d'un autre span
- si c'est le cas je recalcule une nouvelle position
- sinon je garde la position dans un tableau et j'affiche mon mot

Tout cela fonctionne parfaitement. Mais il y a des exceptions, lorsqu'un grand mot recouvre un petit mot, puisque aucun coin n'est présent dans l'aire du petit mot.

Donc je souhaiterais savoir s'il existe un moyen de comparer deux "aires" d'un élément pour savoir s'ils se recouvrent.

J’espère avoir été clair.

Merci

PS= Voici un petit schéma qui sera peut être plus clair.
Chaque rectangle représente un span.
OK = recouvrement détecté avec ma technique
NOK = recouvrement non détecté.
Image utilisateur

Hellish

18 mars 2011 à 17:29:15

Tu peux comparer les coordonnées des span:
Dans le deuxième exemple (nok), tu fais si y1 >= y2 alors c'est bon.

NB: l'abscisse c'est style.left et l'ordonnée c'est style.top

Poste ton code

Anonyme

18 mars 2011 à 18:50:40

Il suffit de refaire la calcul pour toutes les balises italique>spans</italique> précédemment placés... Ce qui devrait être faisable à condition de conserver non seulement la position mais les dimensions de chaque span.

Javascript n'étant pas un langage compilé, il serait opportun d'utiliser pour ce faire des noms courts ou mieux d'incorporer les fonctions correspondantes dans un objet (elles seraient alors pré-installées et non relues à chaque opérration).

xavierm02

18 mars 2011 à 20:12:40

J'ai commencé à faire un truc mais ce n'est pas fonctionnel. Je poste juste pour pouvoir rechopper mon code si je veux continuer.
L'idée, c'est de mettre des arrays qui contiennent tous les objets et qui permettent donc de comparer seulement avec ceux qui sont entre certaines valeurs dans l'array. Enfin je continuerais probablement plus tard ou demain. Reposte quelquechose pour que je vois le sujet dans mes interventions et que je m'en souvienne.

<!doctype html>
<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    <title>text</title>
	<style type="text/css">
		body, html {
			width: 100%;
			height: 100%;
			overflow: hidden;
		}
		body * {
			position: absolute;
		}
	</style>
  </head>
  <body>
	
	<script>
	
var Text = ( function ( ) {
	// Settings
	var globalContainerNode = document.body,
	globalContainerWidth = globalContainerNode.offsetWidth,
	globalContainerHeight = globalContainerNode.offsetHeight;
	// Script
	var xs = [ ],// +++++++++++++++++
	ys = [ ];
	function getRandomBetween( min, max ) {
		return Math.floor(
			Math.random( ) * ( max - min + 1 )
		) + min;
	}
	function isOverOtherText( x, y, width, height ) {
		return false;//+++
	}
	function Text ( text, hide ) {
		// Declare variables
		var containerNode,
		width,
		height,
		x,
		y,
		maxX,
		maxY;
		// Create needed HTML elements
		containerNode = this.containerNode = document.createElement( "div" );
		containerNode.appendChild( this.textNode = document.createTextNode( this.text = text ) );
		// Add a shortcut
		this.style = containerNode.style;
		// Hide the element to be able to append it to get it's offset width
		this.hide( );
		globalContainerNode.appendChild( containerNode );
		width = this.width = containerNode.offsetWidth;
		height = this.height = containerNode.offsetHeight;
		// Get a random x and y
		maxX = globalContainerWidth - width;
		maxY = globalContainerHeight - height;
		do {
			x = getRandomBetween( 0, maxX );
			y = getRandomBetween( 0, maxY );
		} while ( isOverOtherText( x, y, width, height ) );
		// When x and y are good, use the to place container
		this.moveTo( x, y );
		// If not asked to hide, show the text
		if ( !hide ) {
			this.show( );
		}
	}
	Text.prototype = {
		hide: function ( ) {
			this.style.visibility = "hidden";
		},
		moveTo: function ( x, y ) {
			this.style.left = ( this.x = x ) + "px";
			this.style.top = ( this.y = y ) + "px";
		},
		show: function ( ) {
			this.style.visibility = "visible";
		}
	};
	return Text;
} )( );
	
	
	
	
	
window.onload = function ( ) {
	function getRandomBetween( min, max ) {
		return Math.floor(
			Math.random( ) * ( max - min + 1 )
		) + min;
	}
	function addWord( ) {
		var string = "azertyuiopmlkjhgfdsqwxcvbn",
		length = string.length,
		getRandomLetter = function ( ) {
			return string[ getRandomBetween(0,length) ];
		},
		i = getRandomBetween(0,20),
		word = "";
		while (i--) {
			word += getRandomLetter();
		}
		new Text( word );
	}
	var i = 50;
	while (i--) {
		addWord();
	}
};
	
	</script>
  </body>
</html>

Golmote

18 mars 2011 à 20:45:00

Voici un code fonctionnel :

var objects = [];
function genere() {
	var o = {
		d : document.createElement('div'),
		top : Math.floor(Math.random()*300),
		left : Math.floor(Math.random()*300),
		height : (Math.floor(Math.random()*180)+20),
		width : (Math.floor(Math.random()*60)+10)
	},
	s = o.d.style,
	other,
	noConflict = true;

	s.position = 'absolute';
	s.top = o.top+'px';
	s.left = o.left+'px';
	s.height = o.height+'px';
	s.width = o.width+'px';
	s.border = '1px solid black';
	
	
	for(var i=0,l=objects.length;i<l;i++) {
		other = objects[i];
		if(o.left<other.left+other.width &&
			o.left+o.width>other.left &&
			o.top<other.top+other.height &&
			o.top+o.height>other.top) {
				// CONFLIT §
				noConflict = false;
				break;
		}
	}
	if(noConflict) {
		document.body.appendChild(o.d);
		objects.push(o);
	} else {
		genere();
	}
}
document.onclick=genere;

Max235

18 mars 2011 à 20:50:49

Merci pour vos réponses.
La comparaison avec les coordonnées des spans déjà placés, je le fait déjà. Toutes les coordonnées sont conservés dans un tableau.
Mais le problème, pour le NOK, c'est lorsque le petit span est placé en premier. Lorsque les tests du grand span arrivent, ils sont tous bons, puisque je ne compare que les 4 coins du span et ils sont tous en dehors du petit.
Sinon j'ai pensé à rajouter d'autres points de comparaison, genre un point au milieu de chaque coté du "rectangle" (span), mais cette solution est un peu bancale et il peut encore exister des exceptions.
Mais le problème c'est vraiment de l'algo, soit comment savoir qu'un span recouvre un autre span déjà placé sur la page.

Golmote

18 mars 2011 à 20:55:11

As-tu jeté un oeil à la condition de mon code ?

Elle fonctionne...

xavierm02

18 mars 2011 à 23:19:09

Euh Golmote... tes test ont pas l'air au point :
GAUCHE*1<DROITE*2 &&
DROITE*1>GAUCHE*2 &&
HAUT*1<BAS*2 &&
BAS*1>HAUT*2

Imagine 2 rectangle qui vont de (avec un repère en haut à gauche) :
- y=1 à y=3 (*1)
- y=2 à y=4 (*2)
On a :
HAUT*1 = 1
BAS*1 = 3
HAUT*2 = 2
BAS*2 = 4

BAS*1>HAUT*2 est FAUX donc il dit pas de conflit... mais de 2 à 3 les deux rectangles se croisent...

J'aurais plus fait (un peu au pif, j'avoue) :
(
GAUCHE*1<DROITE*2 ||
DROITE*1>GAUCHE*2
) && (
HAUT*1<BAS*2 ||
BAS*1>HAUT*2
)
Parce que pour qu'ils se croise, il faut qu'ils se croisent horizontalement et verticalement. Mais pas forcément que l'un comprenne l'autre.

Golmote

19 mars 2011 à 0:02:36

Citation : xavierm02

On a :
HAUT*1 = 1
BAS*1 = 3
HAUT*2 = 2
BAS*2 = 4

BAS*1>HAUT*2 est FAUX

3>2 est faux ? :waw:

T'as testé mon code ? Personnellement, je n'ai réussi à produire aucun conflit... (en ne tenant pas compte de l'épaisseur des bordures, bien entendu)

EDIT : En fait c'est même très logique...

GAUCHE*1<DROITE*2 <==> o1 n'est pas à droite de o2
DROITE*1>GAUCHE*2 <==> o1 n'est pas à gauche de o2
HAUT*1<BAS*2 <==> o1 n'est pas en-dessous de o2
BAS*1>HAUT*2 <==> o1 n'est pas au-dessus de o2

Donc o1 est au moins partiellement à l'intérieur de o2

xavierm02

19 mars 2011 à 9:10:11

3>2 FAUX

Je devais être fatigué ou je me suis planté de ligne...
C'est vrai que ton truc a l'air logique...
J'ai réfléchi à l'envers >_<

Et quand j'y pense, je me dis que nos mon codes peuvent très bien devenir des boucles infinies s'il n'y a plus de place... (le tien fait une erreur max call stack)
Et dans le tien Golmote, tu recalcules tout alors qu'il suffit de recalculer x et y.

Pour éviter la boule infinie, il faudrait répertorier toutes les positions possibles...
Et pour ça, je ferais bien 2 matrices à deux dimensions, les cases de l'une contenant le nombre de cases vides en dessous d'elle et l'autre le nombre de cases vides à droite d'elle.
Et en considérant les pixels comme des cases.

Golmote

19 mars 2011 à 11:07:56

J'ai pas dit que mon code était optimisé

J'ai juste dit que l'algo fonctionnait

Pour ce qui de tes deux matrices, je reconnais être un peu largué

Je vois pas bien ce que tu veux dire.

xavierm02

19 mars 2011 à 12:03:19

Ça, c'est l'écran (1 digit = 1 pixel) :

On calcule pour chaque case le nombre de cases à sa droite libres (0).

Maintenant, on met un rectangle :

Pour chaque ligne du rectangle, on recalcule les digits à gauche.

Maintenant on imagine que l'on veut placer un autre rectangle.
On veut connaître tous les emplacements où l'on peut placer le rectangle.
Pour cela, on parcours la matrice (façon encore à déterminer) et si l'on tombe sur un digit > la largeur, on regarde le digit en (x,y+n) avec n qui varie de 1 à la hauteur du rectangle et on vérifie qu'il est également plus grand.
Si c'est le case, c'est que sur une certaine partie d'une colonne, on est sûr d'avoir au moins la largeur nécessaire à droite donc on peut positionner le rectangle en (x, y).

Après, tu peux optimiser en faisait que si on a un digit no nul < la largeur, tu incrémente ta variable qui te sert d'index pour parcourir le tableau du digit puisque la valeur des digits à droite sur cette distance sera forcément plus faible.

PS : Tous les trucs que j'ai donnés sont à 1 près. C'est à dire qu'un < peut être un <= et inversement, qu'un 0 peut être un 1 etc.
Pour que ça fonctionne, il faudra réfléchir à si l'on fait plus ou moins 1 mais là c'est juste pour l'idée donc osef.

EDIT : Il n'y a besoin que d'une matrice.

EDIT2 : Suivant la rapport taille de l'écran / taille des spans, il serait peut-être plus efficace de faire une simple matrice avec des 1 et des 0 (1 = OQP, 0 = libre).
Et sinon il faudrait peut-être inverser les x et les y pour optimiser mon truc vu que les écrans sont plus larges que hauts.

Golmote

19 mars 2011 à 12:15:04

Et avec le une double matrice, tu sais directement si t'as la place ou pas.

[9,9][8,9][7,9][6,9][5,9][4,9][3,9][2,9][1,9][0,9]
[9,8][8,8][7,8][6,8][5,8][4,8][3,8][2,8][1,8][0,8]
[9,7][8,7][7,7][6,7][5,7][4,7][3,7][2,7][1,7][0,7]
[9,6][8,6][7,6][6,6][5,6][4,6][3,6][2,6][1,6][0,6]
[9,5][8,5][7,5][6,5][5,5][4,5][3,5][2,5][1,5][0,5]
[9,4][8,4][7,4][6,4][5,4][4,4][3,4][2,4][1,4][0,4]
[9,3][8,3][7,3][6,3][5,3][4,3][3,3][2,3][1,3][0,3]
[9,2][8,2][7,2][6,2][5,2][4,2][3,2][2,2][1,2][0,2]
[9,1][8,1][7,1][6,1][5,1][4,1][3,1][2,1][1,1][0,1]
[9,0][8,0][7,0][6,0][5,0][4,0][3,0][2,0][1,0][0,0]

[9,9][8,9][7,1][6,1][5,1][4,1][3,1][2,1][1,9][0,9]
[9,8][8,8][7,0][6,0][5,0][4,0][3,0][2,0][1,8][0,8]
[1,7][0,7][***][***][***][***][***][***][1,7][0,7]
[1,6][0,6][***][***][***][***][***][***][1,6][0,6]
[1,5][0,5][***][***][***][***][***][***][1,5][0,5]
[9,4][8,4][7,4][6,4][5,4][4,4][3,4][2,4][1,4][0,4]
[9,3][8,3][7,3][6,3][5,3][4,3][3,3][2,3][1,3][0,3]
[9,2][8,2][7,2][6,2][5,2][4,2][3,2][2,2][1,2][0,2]
[9,1][8,1][7,1][6,1][5,1][4,1][3,1][2,1][1,1][0,1]
[9,0][8,0][7,0][6,0][5,0][4,0][3,0][2,0][1,0][0,0]

C'est ça l'idée ? J'aime bien

xavierm02

19 mars 2011 à 12:23:22

C'est ça l'idée

Par contre le problème de la double matrice, c'est si t'as ce cas :

Si tu regardes à partir du point tout en haut à gauche, t'as 4 de place à droite et 3 en bas... mais si tu fout un rectangle de 4*3, tu est sur celui qui y est déjà...
Donc le mieux (enfin je pense) c'est de n'utiliser que la première matrice et de vérifier les 3 premières cases de la première colonne.
Et à la deuxième on tombe sur 0 qui est plus petit que 4 donc on sait que c'est pas bon.

Golmote

19 mars 2011 à 12:49:57

Ouais, faut vérifier la première ligne et la première colonne des rectangles avant de valider, effectivement.

Mais par contre, au final, je vois pas bien en quoi ça résout le problème de stackoverflow...

L'idée consiste toujours à tester des valeurs aléatoires... Donc comment ça peut aider à limiter le choix des valeurs à des solutions possibles ?

xavierm02

19 mars 2011 à 12:57:44

Bah tu récupères toutes les solutions possibles, tu les mets dans un array et tu choppes array[ random( 0, array.length - 1 ) ].
Du coup, t'es sûr que ce que tu vas avoir est bon.
Et si l'array est vite, t'envois une erreur ou tu retourne false ou qqch.

Max235

19 mars 2011 à 12:58:07

Bon faut que je relise ta partie sur les matrices, tout n'est pas clair pour moi :euh:

Sinon je vous donne mon code actuel, ca donnera peut être des idées. Par contre mon code n'est pas très propre...

var board = document.getElementById('board');
var boardWidth = board.offsetWidth;
var boardHeight = board.offsetHeight;
var span = document.getElementsByTagName('span');
var pos = new Array();

//Positionne aléatoirement chaque mot
function position(a){
	var spanWidth = span[a].offsetWidth;
	var spanHeight = span[a].offsetHeight;
	var myLeftMin = Math.ceil((boardWidth - spanWidth)*Math.random()+1);
	var myTopMin = Math.ceil((boardHeight - spanHeight)*Math.random()+1);
	var myLeftMax = spanWidth + myLeftMin;
	var myTopMax = spanHeight + myTopMin;
	var fail = collision(myLeftMin,myTopMin,myLeftMax,myTopMax);
	//S'il y a une collision on recalcule une position
	if ( fail ){
		position(a);
	}
	/*Tout est OK, les positions du mot sont ajoutées au tableau pour les 
        futures vérifications de collisions*/
	pos[a] = new Array(myLeftMin, myLeftMax, myTopMin, myTopMax);
	return(myLeftMin,myTopMin);
}

function collision(myLeftMin,myTopMin,myLeftMax,myTopMax){
	//Vérification de la collision avec un autre mot
	var fail = false;
	for ( var i = 0; i < pos.length; i++ ){
		if ( myLeftMin >= pos[i][0] && myLeftMin <= pos[i][1] ){
			//Coin haut gauche ou coin bas gauche
			if ( (myTopMin >= pos[i][2] && myTopMin <= pos[i][3]) ||
                             (myTopMax >= pos[i][2] && myTopMax <= pos[i][3]) ){
				fail = true;
				break;
			}
		}
		else if ( myLeftMax >= pos[i][0] && myLeftMax <= pos[i][1] ){
			//Coin haut droit ou coin bas droit
			if ( (myTopMin >= pos[i][2] && myTopMin <= pos[i][3]) ||
                             (myTopMax >= pos[i][2] && myTopMax <= pos[i][3]) ){
				fail = true;
				break;
			}
		}
	}
	return fail;
}

for ( var a in span ){
	if ( !isNaN(a) ){
		position(a);
		affichage(a);
	}
}

EDIT: @xavierm02 Je crois avoir compris, tu veux représenter tous les pixels dans un array?!
Donc lorsque que tu veux placer un nouveau rectangle, tu vérifies chaque pixel du nouveau rectangle dans le array, afin de voir si la valeur est différente de null ou 0.

Golmote

19 mars 2011 à 13:33:06

Je persiste à penser que dans ton cas, ma solution serait amplement suffisante. :-°

@xavier : Mais est-ce que ce n'est plus lourd de récupérer toutes les solutions que de tester à l'aveuglette ? Notamment au début, quand peu de rectangles sont affichés...

xavierm02

19 mars 2011 à 15:24:39

Ok pour le premier.
Mais pour les suivants ?
Comment tu sais si il reste assez de place ou si ça va fail ?
Tu peux pas simplement...
Du coup, autant créer la matrice directement et la modifier à chaque ajout...

Enfin il y a peut-être moyen de se passer de matrice et de faire des tests en faisant une boule sur tous les spans...
Mais je sais pas si c'est plus rapide...
Enfin ce sera plus lent mais ça prendra moins de mémoire...
Mais est-ce que c'est plus efficace ? :/

Golmote

19 mars 2011 à 17:50:59

Voilà une implémentation :

<script type="text/javascript">
var matrixX = [],
    matrixY = [],
    matrixO = [],
    w = 20,
    h = 20,
    nb = 0,
    counts = [],
    draw,
    m1,
    m2,
    m3,
    
    // Initialisation
    init = function () {
        var i,
            j;
        draw = document.getElementById('draw');
        draw.style.width = w * 10 + 'px';
        draw.style.height = h * 10 + 'px';
        m1 = document.getElementById('m1');
        m2 = document.getElementById('m2');
        m3 = document.getElementById('m3');
        for (i = 0; i < h; i++) {
            matrixX[i] = [];
            matrixY[i] = [];
            matrixO[i] = [];
            for (j = 0; j < w; j++) {
                matrixX[i][j] = w - j;
                matrixY[i][j] = h - i;
                matrixO[i][j] = 0;
            }
        }
    },
    
    // Détermine si un rectangle peut être placé
    fits = function (largeur, hauteur, x, y) {
        var i;
        if (counts.length <= nb) {
            counts[nb] = 0;
        }
        counts[nb]++;
        for (i = 0; i < hauteur; i++) {
            if (matrixO[y + i][x] === 1 || matrixX[y + i][x] < largeur) {
                return matrixX[y + i][x];
            }
        }
        return true;
    },
    
    // Dessine les matrices
    drawMatrix = function () {
        var s1,
            s2,
            s3,
            m,
            i,
            j;
        s1 = s2 = s3 = '';
        for (i = 0; i < h; i++) {
            for (j = 0; j < w; j++) {
                m = matrixX[i][j];
                s1 += (m < 10 ? ' ' + m : m) + ' ';
                m = matrixY[i][j];
                s2 += (m < 10 ? ' ' + m : m) + ' ';
                m = matrixO[i][j];
                s3 += (m < 10 ? ' ' + m : m) + ' ';
            }
            s1 += '<br />';
            s2 += '<br />';
            s3 += '<br />';
        }
        m1.innerHTML = s1;
        m2.innerHTML = s2;
        m3.innerHTML = s3;
    },
    
    // Met à jour les matrices
    fillMatrix = function (largeur, hauteur, x, y) {
        var i,
            j;
        for (i = y; i < y + hauteur; i++) {
            for (j = 0; j < x + largeur; j++) {
                if (matrixO[i][j] === 0) {
                    matrixX[i][j] = Math.min(matrixX[i][j], j < x ? x - j : x + largeur - j);
                }
            }
        }
        for (i = 0; i < y + hauteur; i++) {
            for (j = x; j < x + largeur; j++) {
                if (matrixO[i][j] === 0) {
                    matrixY[i][j] = Math.min(matrixY[i][j], i < y ? y - i : y + hauteur - i);
                }
            }
        }
        for (i = y; i < y + hauteur; i++) {
            for (j = x; j < x + largeur; j++) {
                matrixO[i][j] = 1;
            }
        }
        drawMatrix();
    },
    
    // Dessine le nouveau rectangle
    drawObject = function (w, h, x, y) {
        var d = document.createElement('div'),
            s = d.style;
        s.position = 'absolute';
		s.fontSize = 0;
        s.left = x * 10 + 'px';
        s.top = y * 10 + 'px';
        s.width = w * 10 + 'px';
        s.height = h * 10 + 'px';
        s.background = '#999';
        draw.appendChild(d);
    },
    
    // Génère un nouveau rectangle (au clic)
    genere = function () {
        var possib = [],
            largeur = 10,
            hauteur,
            fit,
            res,
            i,
            j;
        while (largeur-- > 1) {
            hauteur = 10;
            while (hauteur-- > 1) {
                for (i = 0; i + hauteur - 1 < h; i++) {
                    for (j = 0; j + largeur - 1 < w; j++) {
                        fit = fits(largeur, hauteur, j, i);
                        if (fit === true) {
                            possib.push({
                                w: largeur,
                                h: hauteur,
                                x: j,
                                y: i
                            });
                        } else {
                            j += fit - 1;
                        }
                    }
                }
            }
        }
        if (possib.length) {
            res = possib[Math.floor(Math.random() * possib.length)];
            fits(res.w, res.h, res.x, res.y);
            fillMatrix(res.w, res.h, res.x, res.y);
            drawObject(res.w, res.h, res.x, res.y);
            if (typeof console !== 'undefined') {
                console.log('Object ' + nb + ' : ' + possib.length + ' possibilité(s) : ' + counts[nb] + ' passages dans fits()');
            }
            nb++;
        } else {
            alert('Plus de résultat possible !');
        }
    };
window.onload = function () {
    init();
    drawMatrix();
    document.onclick = genere;
};
</script>

<div>
<pre style="float:left;font-size:9px;margin-right:5px;" id="m1"></pre>
<pre style="float:left;font-size:9px;margin-right:5px;" id="m2"></pre>
<pre style="float:left;font-size:9px;" id="m3"></pre>
</div>
<div style="position:relative;clear:left;" id="draw"></div>

La matrice matrixY est purement décorative pour l'instant, elle n'est pas utilisée dans les calculs.

Au vu du nombre de passage dans la fonction (cf console.log), je suppose qu'il y a encore moyen d'optimiser. (Peut-être en utilisant matrixY justement ?)

xavierm02

19 mars 2011 à 20:30:47

Mais euh c'était mon joujou cet algo

C'est stylé ton "UI"

Par contre, la matrice de droite à tout un 1 (normal) mais dans les deux autres, il reste d'autre nombres o_O

Golmote

19 mars 2011 à 21:16:35

Oups désolé... :euh:

Mais t'as le droit de le faire de ton côté aussi hein.

Oui, en fait dans les autres matrices, j'ai poussé le vice en faisant comme ça :

T'as la matrice de départ :

Tu mets un rectangle

Tu modifies les nombres à gauche du rectangle :

Et en bonus, tu mets dans le rectangle les nombres suivant le même principe (inverse). C'est le nombre de cases non vides à droite.

Associée avec la matrice des 0 et 1, ça permet de sauter directement plusieurs cases occupées.

xavierm02

19 mars 2011 à 22:14:31

Pas mal

Pour éviter d'avoir deux matrices, tu pourrais insérer celle avec que des 0 et des 1 dans l'autre comme ça :
0 <=> nombre négatif
1 <=> nombre positif
Donc en gros : matriceX = (matrice0 - 0.5)* 2 * matriceX;

Max235

20 mars 2011 à 0:58:58

Désolé les gars, mais là je suis un peu largué... Je comprends bien la matrice m3 (0 ou 1), mais les autres... Je ne comprends pas ce changement de nombres et tout

.

Bon sinon avec les différents trucs que j'ai vu sur ce post, j'ai modifié mon algo. Je suis parti sur un tableau représentant chaque pixel de l'écran. Dès qu'une position est prise, je remplie tout l'aire du span dans le tableau avec la valeur 1 (même principe que la matrice m3 de Golmote). Pour les tests d'un nouveau rectangle, je teste tout le contour de celui-ci par rapport au tableau des positions. Si je tombe sur un 1, c'est qu'il y a un recouvrement, donc recalcule de la position. Je ne gère pas encore l'histoire de la boucle infini, mais déjà je n'ai plus aucun conflit.

var board = document.getElementById('board');
var boardWidth = board.offsetWidth;
var boardHeight = board.offsetHeight;
var span = document.getElementsByTagName('span');
var pos = new Array();

function init(){
	var i, j;
	for ( i = 0; i < boardWidth; i++ ){
		pos[i] = new Array();
	}
}

//Positionne aléatoirement chaque mot
function position(a){
	var spanWidth = span[a].offsetWidth;
	var spanHeight = span[a].offsetHeight;
	var myLeftMin = Math.ceil((boardWidth - spanWidth)*Math.random()+1);
	var myTopMin = Math.ceil((boardHeight - spanHeight)*Math.random()+1);
	var myLeftMax = spanWidth + myLeftMin;
	var myTopMax = spanHeight + myTopMin;
	var fail = collision(myLeftMin,myTopMin,myLeftMax,myTopMax,spanHeight);
	//S'il y a une collision on recalcule une position
	if ( fail ){
		position(a);
	}
	/*Tout est OK, les positions du mot sont ajoutées au tableau pour
        les futures vérifications de collisions*/
	for ( i = myLeftMin; i <= myLeftMax; i++ ){
		for ( j = myTopMin; j <= myTopMax; j++){
			pos[i][j] = 1;
		}
	}
}

//Vérification de la collision avec un autre mot
function collision(myLeftMin,myTopMin,myLeftMax,myTopMax,spanHeight){
	var fail = false;
	var i, j;
	//Vérification colonne par colonne
	for ( i = myLeftMin; i <= myLeftMax; i++ ){
		//Vérification des 2 cotés verticaux du rectangle
		if ( i == myLeftMin || i == myLeftMax ){
			//Chaque pixel pour la hauteur du span
			for ( j = myTopMin; j <= myTopMax; j++){
				if ( pos[i][j] == 1 ){
					fail = true;
					break;
				}
			}
		}
		//Vérification des cotés horizontaux du rectangle
		else{
			//Premier et dernier pixel sur l'axe Y du span
			for ( j = myTopMin; j <= myTopMax; j = j + spanHeight){
				if ( pos[i][j] == 1 ){
					fail = true;
					break;
				}
			}
		}
		if ( fail == true ){
			break;
		}
	}
	return fail;
}

init();
//Pour chaque span du div board
for ( var a in span ){
	if ( !isNaN(a) ){
		position(a);
		affichage(a);
	}
}

Golmote

20 mars 2011 à 4:20:10

@Max : Comme je l'ai dit dans ce post, je pense que ton problème peut être résolu avec une simple condition.
(Cf lignes 24 à 27 du code de ce post)

La grande extrapolation avec xavier n'étant qu'un algo plus poussé pour ce genre de calculs...

@xavier : Hm, c'pas bête, je vais voir si j'ai le temps et l'envie de refaire le code demain

(enfin aujourd'hui... mais après avoir dormi, quoi)

Max235

20 mars 2011 à 15:05:38

Je l'avais essayé ton code, en l'adaptant au mien:

function collision(myLeftMin,myTopMin,myLeftMax,myTopMax){
	var fail = false;

	for ( var i = 0; i < pos.length; i++ ){
		if ( myLeftMin <= pos[i][1] &&
			 myLeftMax >= pos[i][0] && 
			 myTopMin <= pos[i][3] && 
			 myTopMax >= pos[i][2] ){
			fail = true;
			break;
		}
	}
	return fail;
}

Mais je me suis retrouvé avec des exceptions inexplicables et c'est pour ca que je suis allé explorer d'autres pistes. Mais c'est vrai que ton algo est logique. Il faut que je regarde avant et après l'appel de la fonction voir s'il n'y a pas un problème. Mais avec mon dernier algo je n'ai absolument aucune exception.

xavierm02

20 mars 2011 à 15:23:09

Quoi comme erreur ?

Max235

20 mars 2011 à 17:57:19

Des collisions qui ne devraient pas être présentes.

Golmote

20 mars 2011 à 18:14:01

Tu peux donner un code complet JS+HTML(+CSS?) qu'on puisse tester ?

Max235

20 mars 2011 à 19:50:35

var board = document.getElementById('board');
var boardWidth = board.offsetWidth;
var boardHeight = board.offsetHeight;
var span = document.getElementsByTagName('span');
var alpha = new Array();
var t = new Array();
var pos = new Array();

//Positionne aléatoirement chaque mot
function position(a){
	var spanWidth = span[a].offsetWidth;
	var spanHeight = span[a].offsetHeight;
	var myLeftMin = Math.ceil((boardWidth - spanWidth)*Math.random()+1);
	var myTopMin = Math.ceil((boardHeight - spanHeight)*Math.random()+1);
	var myLeftMax = spanWidth + myLeftMin;
	var myTopMax = spanHeight + myTopMin;
	var fail = collision(myLeftMin,myTopMin,myLeftMax,myTopMax);
	//S'il y a une collision on recalcule une position
	if ( fail ){
		position(a);
	}
	/*Tout est OK, les positions du mot sont ajoutées au tableau
        pour les futures vérifications de collisions*/
	pos[a] = new Array(myLeftMin, myLeftMax, myTopMin, myTopMax);
}

function collision(myLeftMin,myTopMin,myLeftMax,myTopMax){
	//Vérification de la collision avec un autre mot
	var fail = false;

	for ( var i = 0; i < pos.length; i++ ){
		if ( myLeftMin <= pos[i][1] &&
			 myLeftMax >= pos[i][0] && 
			 myTopMin <= pos[i][3] && 
			 myTopMax >= pos[i][2] ){
			fail = true;
			console.log('collision');
			break;
		}
	}
	return fail;
}

//Affichage du mot suivant sa position
function affichage(a){
	span[a].style.position = 'absolute';
	span[a].style.left = pos[a][0] + 'px';
	span[a].style.top = pos[a][2] + 'px';
	alpha[a] = 0;
	span[a].style.opacity = 0;
	// Test pour notre cher IE
	if (document.body.filters != undefined)
		span[a].style.filter = 'alpha(opacity:0)';
	span[a].style.visibility = 'visible';
	t[a] = setInterval('fondu(' + a + ')', 20);
}

//Création du fondu au moment de l'affichage
function fondu(a){
	alpha[a] += 2;
	if (alpha[a] <= 100){
		span[a].style.opacity = alpha[a]/100;
		if (document.body.filters != undefined)
			span[a].style.filter = 'alpha(opacity:' + alpha[a] + ')';
	}
	else
		clearInterval(t[a]);
}

function run(a){
	position(a);
	affichage(a);
}

//Pour chaque span du div board
for ( var a in span ){
	if ( !isNaN(a) ){
		//Affichage en décalé
		setTimeout('run('+a+')',a*250);
	}
}

Après mon php n'est pas intéressant, il récupère les mots dans une base de données, et les mets dans une balise span, c'est tout.
Mais voici un html bateau:

<html>
	<style>
	span{
	visibility:hidden;
	font-size:30px;
	border:1px solid red;
	}
	#board{
	height:90%;
	lenght:100%;
	border:1px solid black;
	}
	</style>
   <body>
   <div id="board">
     <span>test</span>
     <span>blabla</span>
     <span>unmotunpeupluslong</span>
     <span>tralala</span>
     <span>pouet</span>
     <span>osalagadou</span>
     <span>lamanchicabou</span>
     <span>labibida</span>
     <span>bidibou</span>
	</div>
     <script type="text/javascript" src="script.js">
     </script>
   </body>
</html>

1 2 >>