Remplir un triangle avec un minimum d'éléments - Page 1

Je pose ma question ici, parce qu'elle a plus de chance d'être lu que dans le forum Javascript, et parce que le langage ne change rien dans ce cas.
Je recherche la facon de remplir un triangle (n'importe quel triangle)en utilisant le moins d'éléments < div> possible.
Ces éléments etant des < div> je peux utiliser des lignes et rectangles (et donc carrés) de n'importe quelle taille mais seulement à l'horizontale ou à la verticale.
Je ne sais pas par ou commencer alors si vous avez des idées, un algos qui y ressemble ou des formules geometriques utiles à me rappeller.

Allez je me lance :

function fill_triangle (p1.x,p1y , p2.x,p2.y , p3.x p3.y)
{
heu....nan je me rappelle plus, la formule de pythales machin * hypothalamus+b GGRRRrr
}

La façon la plus simple que je vois c'est remplir pixel par pixel.

Je ne comprends pas bien la question
Tu veux remplir un triangle entièrement (tous les pixels) avec des rectangles de différentes tailles, et tu cherches à utiliser le moins de rectangles possible, c'est ça ?
En n'ayant aucune contrainte sur le triangle de départ ?

Nan, il peut aussi utiliser des lignes ...

Euh oui, mais une ligne c'est un rectangle de largeur 1

Mauvais joueur nah !

Les rectangles (ou lignes, pour faire plaisir à nEUrOO) ont le droit de se recouvrir les uns les autres ?

beuh oui

Ben ça m'a pas l'air d'un problème simple tout ça... :-\

utilise que des lignes horizontale .. sera plus rapide et pê plus simple

oui, ou que des lignes verticales (suivant les cas), c'est aussi ce à quoi je pensais...
je ne sais pas si c'est la meilleure solution dans tous les cas, ça ne me semble pas évident, mais le contraire ne l'est pas non plus...
En tous cas, si pour certains cas il existe une meilleure solution elle n'est vraisemblablement pas facile à déterminer, donc tout dépend ce que tu veux (tiens-tu absolument à avoir une solution vraiment minimale quitte à utiliser beaucoup de temps de calcul, ou préfères-tu avoir une solution toute simple qui n'est peut-être pas toujours la meilleure ?)

J'ai essayé avec des lignes horizontales et je gagne deja bcp de temps, mais ce que je cherche c'est remplir avec un minimum de lignes/rectangles.
Ils peuvent se recouvrir, mais par contre l'algo ne doit pas utiliser de buffer (d'apres mes essais, une boucle sur tt les pixels d'un ecran prend bien 5 sec en js).
J'ai penser à une fct recursive : si on enleve le + gros rectangle contenu dans un triangle, il reste 3 triangles plus petits...et ainsi de suite.

je pense qu'il veut qqch de rapide ... deja que le rste n'y est pas

GUNNM: ma proposition tiens toujours, la routine de XLib est adaptable {si tu viens sur irc, je te la file}

Pour l'instant c'est la concatenation de tout les < div> prend tout le temps, les calculs sont effectués en 15ms et la concatenantion de < div> en 2s !! (suivant le nb de ligne du triangle().
Sur de plus gros objets j'ai 50ms de calcul pour 60 secondes de concatenation.!!
Si l'algo est compliqué il me fera quand même gagner du temps. (un carré de 100 px remplace 100 lignes de < div> )

Merci nEUrOO c'est sympas, mais j'ai essayé avec des hlines, ce qu'il me faut maintenant, c'est une idée de départ pour commender mon algo.

Comment determiner le + gros rectangle contenu ds un triangle?

J'ai penser à une fct recursive : si on enleve le + gros rectangle contenu dans un triangle, il reste 3 triangles plus petits...et ainsi de suite.

Euh, c'est pas vrai ça puisque ton rectangle a forcément les côtés parallèles aux axes...
et de toute façon un algorithme de ce type ne donnerait pas en général un meilleur résultat que le balayage tout bête...

Je pose ma question ici, parce qu'elle a plus de chance d'être lu que dans le forum Javascript, et parce que le langage ne change rien dans ce cas.

GUNNM: ma proposition tiens toujours, la routine de XLib est adaptable {si tu viens sur irc, je te la file}

Tu peux mélanger rectangle et lignes, au centre de ton triangle tu met un rectangle, puis tu complète les trous avec des lignes???

Oui, la question est : est-ce mieux que de tout remplir avec seulement des lignes ?
Personnellement j'en doute (enfin je suis sûre que ce n'est pas mieux en général, mais ça l'est peut-être dans certains cas particuliers (?))

Non, la question est: comment avoir moins de < div> ?
J'ai bien essayé de remplir avec des lignes, mais ca rame car y'a trop de < div>, donc je cherche à reduire le nb de < div> pas forcement le temps de calcul.

Si l'algo est compliqué il me fera quand même gagner du temps. (un carré de 100 px remplace 100 lignes de < div> )

Ben en fait, non, parce que comme ton triangle est « pointu » il restera forcément des trous, qu'il te faudra boucher... je doute sérieusement que tu réussisses à gagner beaucoup, voire à gagner quoi que ce soit. :\

Tu peux gagner en utilisant des rectangles de plus d'un pixel de hauteur si tes triangles sont presque verticaux/horizontaux, mais à part ça c'est difficile de trouver une méthode qui ne soit pas dépendante du navigateur, de l'OS ou de la carte graphique (parce que je pense que tu ne connais pas la forme qu'aura une ligne donnée au pixel près - cela dit toutes les versions d'IE se comportent probablement pareil). Si tu connais exactement la méthode de tracé de ligne utilisée par ton système, alors tu devrais pouvoir gagner en vitesse un facteur 4 sans trop de problème : tu peux tracer ton triangle comme si la résolution était moindre (disons 5x plus petite), puis tu peux 'adoucir' les bords en dessinant une série de lignes sur le côté (un peu plus de 5 par côté). Evidemment, il faut tracer un paquet de lignes pour qu'il n'y ait pas des pixels qui restent, mais ça dépend bcp de la routine de tracé de ligne...

Mais d'après ce que je comprend, c'est qu'il faut utiliser un minimum de fonction, ... donc, trouver l'algo qui utiliserait le moins d'appel et le moins de boucle

je pense que le but est de réduire le nombre de < div > générés, tout en ayant un temps de calcul raisonnable.

Vu que c executé sur PC ... le temps de calcul sera raisonnable
Une fonction récurisvei qui remplirait avec le plus gros rectangle inclus dans le triangle (et on fais de mm avec les "coins")

Ca ne change rien... si on se limite à des rectangles à bords horizontaux et verticaux, un triangle avec une arête à 45° ne peut pas être rempli de manière plus efficace qu'avec des lignes horizontales...

Oui, mais au bout d'un moment, ca ne se verra pas.
Et ca permet d'utiliser un minimum d'élément <div>

OK, alors ce que tu dis revient tout simplement à diminuer la résolution du rendu... Pas besoin d'algo récursif pour ça.

Pollux
: Ca ne change rien... si on se limite à des rectangles à bords horizontaux et verticaux, un triangle avec une arête à 45° ne peut pas être rempli de manière plus efficace qu'avec des lignes horizontales...

J'ai fait beaucoup de schemas et je vois pas pourquoi tu dis ça? On peux trouver un gros rectangle dans la majorité des triangles, enfin il me semble.

hmm... à moins que je n'ai pas bien compris la question, je pense que tu veux remplir un triangle au pixel près (ou à 2 pixels près si tu veux accélérer)

Donc, par exemple, comment ferais-tu avec la méthode du gros rectangle pour le rectangle (0,0)-(8,8)-(16,0) ? Parce que je crois que tu es obligé d'avoir au moins 9 < div > si tu veux remplir au pixel près...

on peut dessiner avec javascript ???