Bonjour la communauté,

Je suis confronté à un problème algorithmique assez complexe, et mes compétences en mathématiques me font un peu défaut pour arriver à déterminer quelle pourrait être la meilleure solution à mon problème.

Je vous expose tout d'abord l'énoncé. Il s'agit d'un programme que je dois développer en C#. Je n'expose pas mon problème dans la partie C# car mon souci ne se pose pas ai niveau de la programmation, mais purement au niveau de l'algorithme.

J'ai un polygone donné, je dois remplir ce polygone afin que la surface remplie atteigne une certaine surface. Sachant que le polygone peut avoir une forme assez complexe. Ce remplissage doit se faire selon un axe donné (par exemple axe horizontal de la gauche vers la droite). Je dois réaliser cette opération sur plusieurs milliers de polygones. Il me faut donc un algorithme optimisé afin que l'opération soit la plus efficace possible.

J'ai à disposition les fonctions qui me permettent de faire le calcul d'intersection, calcul d'aire, ... Toutefois, ces opérations sont assez couteuses, et il faudrait donc les utiliser le moins possible.

Pour illustrer mon exemple, on va considérer un polygone dont la surface est égale à 20ha. Je dois remplir 2ha de ce polygone. Voici le résultat final que je dois obtenir (le dessin ne respectant pas forcément les proportions) :

En noir, mon polygone de 20ha, en bleu la surface de 2ha, en rouge, le rectangle englobant mon polygone (h=400m, l=625m, a=25ha).

Mon idée serait de déterminer dans un premier temps de calculer la proportion que représente la surface à remplir par rapport à la surface de mon polygone (=10%). Je rajoute à cela une marge d'erreur qui sera calculée en fonction de la différence de surface réelle de mon polygone par rapport à celle de mon rectangle (+25%).

Je vais donc prendre comme largeur de base 62,5m auxquels je rajoute 25%, soit 78.125m.

Ici, je vais donc dire que je fais une première itération en prenant l'intersection d'un rectangle de 400*62,5). Cela va me donner un premier remplissage, qui sera très certainement incorrect (à moins d'un gros coup de chance).

Puis je vais faire plusieurs itérations en reprenant à chaque fois le même principe (calcul de la surface obtenue par rapport à la surface voulue, pour déterminer une marge d'erreur, afin de savoir combien de mètres je vais devoir ajouter/enlever à mon rectangle). Je vais répéter cela jusqu'à obtenir une surface de remplissage proche de celle voulue à une marge d'erreur près (par exemple 1m²).

Ma principale crainte par rapport à cela, est d'arriver à un point où la marge d'erreur se trouve tellement réduite que l'on ne fasse une infinité de petits pas jusqu'à obtenir le résultat voulu.

Que pensez-vous de mon algo ? Avez-vous une meilleure proposition à me faire ? Peut-être un calcul avec intégrales peut me sauver ?

A savoir également que le remplissage peut également être réparti sur plusieurs polygones.

Merci d'avance.

Salut, étant donné que tes polygones peuvent avoir une forme complètement aléatoire, je dirais que le plus simple serait de faire une recherche de la solution à une marge d'erreur près par dichotomie.

C'est un peu l'idée que j'ai présentée, sauf que je ne pars pas arbitrairement en prenant la moitié de ma forme pour ensuite atteindre le remplissage voulu en découpant toujours par moitié, mais j'essaye dès le départ de m'approcher le plus possible du remplissage souhaité.

Mais là où j'ai le plus de mal par rapport à cela, c'est déterminer la règle de calcul qui va déterminer le pas que je vais utiliser pour ajouter ou enlever de la surface à chaque itération.

Justement, ce que je suis en train de te dire, c'est que la dichotomie sera bien plus simple à mettre en place. Parce que le risque avec ta méthode, c'est de perdre plus de temps à évaluer ce qu'il faut rajouter en se basant sur des calculs qui seront nécessairement un peu compliqués et où il faudra vérifier que tu ne vas pas tourner indéfiniment autour de ta solution en ne t'en approchant statistiquement pas plus (ce qui n'est pas très simple).

Avec la dichotomie, tu es sur de converger, et de le faire dans un temps raisonnable. Donc pourquoi s'en priver ?

Bonsoir,

Il faut que tu partes d'un algorithme standard comme celui-ci :

http://fr.wikipedia.org/wiki/Algorithme_de_remplissage_par_diffusion

Tu n'as plus qu'à le modifier pour qu'il remplisse effectivement de gauche à droite.

Pourquoi ne pas partir du point le plus à gauche de ta forme et de remplir petit à petit chaque ligne verticale en allant vers la droite. Une fois la surface désirée atteinte tu t'arrêtes et le job est fait.

Mathieu

-
Edité par Mat 3910 25 juillet 2014 à 10:52:22

Mat 3910 a écrit:

Bonsoir,

Il faut que tu partes d'un algorithme standard comme celui-ci :

http://fr.wikipedia.org/wiki/Algorithme_de_remplissage_par_diffusion

Tu n'as plus qu'à le modifier pour qu'il remplisse effectivement de gauche à droite.

Pourquoi ne pas partir du point le plus à gauche de ta forme et de remplir petit à petit chaque ligne verticales en allant vers la droite. Une fois la surface désirée atteinte tu t'arrêtes et le job est fait.

Mathieu

Ca marche s'il a une représentation matricielle des images. S'il travaille avec des polygones formels (des points et des équations) , c'est mort.

-
Edité par Anonyme 25 juillet 2014 à 9:42:04

Quelque chose qui me surprend, c'est que tu dis que le calcul d'intersection est très coûteux. Je ne comprends pas comment c'est possible, c'est du linéaire en fonction du nombre de sommets, et il n'y a qu'un seul calcul à faire pour calculer l'intersection entre deux droites. Autre chose, pour limiter le calcul d'aire, plutôt que de recalculer à chaque fois l'aire totale que tu obtiens à chaque itération de la dichotomie, calcule juste l'aire que tu ajoutes/enlèves. (Bon j'imagine que tu y avais déjà pensé, mais ça ne mange pas de pain de le dire.)

Mat 3910 a écrit:

Bonsoir,

Il faut que tu partes d'un algorithme standard comme celui-ci :

http://fr.wikipedia.org/wiki/Algorithme_de_remplissage_par_diffusion

Tu n'as plus qu'à le modifier pour qu'il remplisse effectivement de gauche à droite.

Pourquoi ne pas partir du point le plus à gauche de ta forme et de remplir petit à petit chaque ligne verticale en allant vers la droite. Une fois la surface désirée atteinte tu t'arrêtes et le job est fait.

Mathieu

-
Edité par Mat 3910 le 25 juillet 2014 à 10:52:22

Effectivement j'ai cherché des algos qui pourraient me faire ça. Mais ce n'est pas ce que je cherche, ce n'est pas le remplissage à proprement parler qui m'importe, mais plutot la forme que je vais devoir créer pour avoir la surface désirée. Du côté du dessin, j'ai déjà tous les outils nécessaires (calcul de surface, création d'un polygone a partir de l'intersection de deux polygones, ...).

Mon problème est vraiment d'un point de vue de l'algo, je dois arriver à trouver la forme le plus rapidement possible.

melepe a écrit:

Quelque chose qui me surprend, c'est que tu dis que le calcul d'intersection est très coûteux. Je ne comprends pas comment c'est possible, c'est du linéaire en fonction du nombre de sommets, et il n'y a qu'un seul calcul à faire pour calculer l'intersection entre deux droites.
Autre chose, pour limiter le calcul d'aire, plutôt que de recalculer à chaque fois l'aire totale que tu obtiens à chaque itération de la dichotomie, calcule juste l'aire que tu ajoutes/enlèves. (Bon j'imagine que tu y avais déjà pensé, mais ça ne mange pas de pain de le dire.)

Quand je parle de calcul d'intersection, je parle de l'intersection de deux polygones et non pas de l'intersection de deux droites. Ce calcul est très coûteux, car il est long à réaliser par la machine. Pour un polygone, ce n'est pas énorme, mais multiplié par plusieurs milliers, puis multiplié par le nombre d'itérations que je vais devoir effectuer pour trouver la bonne valeur, on peut facilement arriver à plusieurs heures de calcul, si l'algo n'est pas optimisé (voire plusieurs jours).

Sinon, pour le calcul d'aire, effectivement j'y ai pensé, mais il faut que j'évalue s'il y a un réel gain de perf en ne calculant que la surface ajoutée. Difficile à dire sans essayer. Mais un autre problème se présente alors, c'est que il y a un problème de précision du résultat a chaque ajout/retrait de surface (qui est du à la techno utilisée). Je risque donc d'avoir des erreurs de calculs si j'ajoute mes surfaces successivement de la sorte.

Mais c'est quand même une idée intéressante, je peux toujours faire ça pour m'approcher du résultat final, puis recalculer la surface entière pour affiner lorsque je tombe sur la valeur voulue.

Je dois commencer à plancher la-dessus début de semaine prochaine. Je vous tiendrai au courant de comment cela avance et reviendrai donner la solution que j'aurai employé.

Bonjour,

Juste une petite idée en passant. Tu parles de plusieurs milliers de polygones. Si ceux ci se touchent alors il peut être intéressant de les fusionner pour limiter le nombre d'arêtes à tester.

Mathieu

Bonjour Mat,

OK. Maintenant quel est l'algo de fusion de polygones dont on connait les points séquentiels ?

C'est un problème de Computational Geometry. La librarie CGAL (The Computational Geometry Algorithms Library) implémente un algorithme pour le faire. Je pense que c'est un bon début pour se documenter. La page de documentation en question: 2D Regularized Boolean Set-Operations. Regarder la section 3: Boolean Set-Operations on Linear Polygons