rectangulation: transformer amas points 2d en rectangles

Bonjour,

comment avoir la meillleure "rectangulation" à partir d'un amas de points 2d (et le plus rapidement possible)

j'ai besoin d'implémenter cet algo pour un petit jeu en 2d:
transformer un amas de pixels (peu éparpillés) en union de rectangles pleins, les plus grands possibles (idée proche de la triangulation, mais l'objectif est d'avoir des rectangles)

en fait il faut convertir la map (fichier image) presque entièrement dessinée dans un logiciel de dessin
en union de plusieurs rectangles de taille différente: car ils sont utilisés dans un moteur physique qui ne se nourrit que de rectangles

donc j'ai trouvé une solution (la plus simple):

on prend un point au hasard de l'amas de pixels, on créé un rectangle de 1 sur 1 et on l'élargit tant qu'on peu (super l'algo!!!)

je ne sais pas s'il y en a une mielleure, voilà je vous pose la question:
comment avoir la meillleure "rectangulation" à partir d'un amas de points (et le plus rapidement possible)

merci

J'ai bein peur qu'il n'existe pas de "meilleure rectangulation", mais bien plusieurs "meilleures rectangulations" toutes équivalentes.

Encore faut-il savoir ce que tu appelles de "meilleur rectangulation" !
Je penses que tu doit vouloir dire un agencement de rectangles tels que la surface gaspillée à cause d'un point trop éloignée dans un carré soit minimale.

Maintenant reste à l'expliciter sous forme mathématique.

En attendant tu as pensé à un algorithme qui par du rectangle le plus grand encadrant tout tes points, et tu affine récursivement pour diminuer la surface gaspillée ? (L'inverse de ta solution qui fait grandir les rectangles).

oui mchk0123 a donné le bon indice sur la méthode à suivre.... :mrgreen:

Tu procèdes par découpage itératif descendant :

D'abord point xmin, xmax, ymin, ymax

Puis tu divises en 4 : au moins 1 point dans un des 1/4, tu continues la division dans ce quart, etc....