Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1931 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  Algo pour intersection de figures

 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Algo pour intersection de figures

n°1578159
cimourdain
Posté le 22-06-2007 à 17:26:00  profilanswer
 

Salut,
 
J'ai des données décrivant plusieurs figures dans un plan. Ces figures peuvent etre de 2 types: quadrilatères (forme fermée quelconque avec 4 cotés) et cercles. Pour les quadrilatères j'ai 4 couples de coordonnées correspondant aux 4 sommets du quadrilatère; et pour les cercles j'ai un couple correspondant au centre et un entier correspondant à son rayon. Je cherche un algo le plus efficace possible en terme de temps de calcul qui me dise quelles sont les figures qui ont une intersection non vide avec une autre.


Message édité par cimourdain le 22-06-2007 à 17:26:51
mood
Publicité
Posté le 22-06-2007 à 17:26:00  profilanswer
 

n°1578196
MagicBuzz
Posté le 22-06-2007 à 19:43:42  profilanswer
 

Le plus rapide possible = bounding box
=> Tu vas donc inclure chacune de tes formes dans un rectangle "droit" (c'est à dire dont les arrêtes sont parralèles aux axes).
- Pour le cercle, c'est x1,y1 = centre.x - rayon, centre.y - rayon / x2,y2 = centre.x + rayon, centre.y + rayon
- Pour les quadrilatères, c'est x1,y1 = min(x1, x2, x3, x4), min(y1, y2, y3, y4) / x2,y2 = max(x1, x2, x3, x4), max(y1, y2, y3, y4)
 
Ensuite, tu fais les calculs simples sur les bounding box : tu peux t'en tirer donc simplement en faisant des comparaisons < > sur les points 1 et 2 de chaque forme
 
Quand tu détectes une intersection de bounding box, tu fais alors le calcul de l'intersection "classique" de formes comme tu as appris au lycée. (le truc chiant étant de trouver les intersections entre l'arrête d'un quadrilatère et un cercle) => tu peux dégrossir avant en recherchant la présence d'un sommet des quadrilatères dans le cercle.
 
PS : Pour voir si deux cercles se chevauchent, pas la peine de te lancer dans des calculs savants : (x1-x2)² + (y1-y2)² < (r1 + r2)² est suffisant.
PS2 : Pour voir si un sommet d'un quadrilatère est présent dans un cercle, même formule ou presque : (x1-x2)² + (y1-y2)² < (r1)²
 
PS3 : Tu parles d'intersections. Mais dois-tu aussi détecter les inclusions ?


Message édité par MagicBuzz le 22-06-2007 à 19:45:23
n°1578213
MagicBuzz
Posté le 22-06-2007 à 21:15:03  profilanswer
 

Genre, une piste, ici en C#
 

Code :
  1. using System;
  2. using System.Drawing;
  3.  
  4. namespace Geometry
  5. {
  6.    class Program
  7.    {
  8.        static void Main(string[] args)
  9.        {
  10.            Pattern[] patternList = new Pattern[10000];
  11.  
  12.            // Initialize patternList
  13.            Random r = new Random();
  14.            for (int i = 0, cpt = patternList.Length; i < cpt; )
  15.            {
  16.                patternList[i++] = new Circle(new Point(r.Next(10000), r.Next(10000)), r.Next(50));
  17.                Point basePoint = new Point(r.Next(10000), r.Next(10000));
  18.                patternList[i++] = new Quadrilateral(new Point(basePoint.X - r.Next(20), basePoint.Y - r.Next(20)), new Point(basePoint.X + r.Next(20), basePoint.Y - r.Next(20)), new Point(basePoint.X - r.Next(20), basePoint.Y + r.Next(20)), new Point(basePoint.X + r.Next(20), basePoint.Y + r.Next(20)));
  19.            }
  20.  
  21.            // Check overrides
  22.            for (int i = 0, cpt = patternList.Length; i < cpt - 1; i++)
  23.            {
  24.                for (int j = i + 1; j < cpt; j++)
  25.                {
  26.                    try
  27.                    {
  28.                        if (patternList[i].CheckOverride(patternList[j], true, true, true))
  29.                        {
  30.                            Console.WriteLine("{0} {1} overrides {2} {3}.", patternList[i].GetType().Name, i, patternList[j].GetType().Name, j);
  31.                        }
  32.                    }
  33.                    catch (NotImplementedException ex)
  34.                    {
  35.                        Console.WriteLine("{0} {1} might override {2} {3}, but not checked (\"{4}\" ).", patternList[i].GetType().Name, i, patternList[j].GetType().Name, j, ex.Message);
  36.                    }
  37.                }
  38.            }
  39.            Console.ReadKey();
  40.        }
  41.    }
  42.  
  43.    abstract class MathTools
  44.    {
  45.        /// <summary>
  46.        /// Checks if the point A is inside the retangle defined by P1 and P2
  47.        /// </summary>
  48.        /// <param name="A">Point to check</param>
  49.        /// <param name="P1">Upper left corner of the rectangle</param>
  50.        /// <param name="P2">Lower right corner of the rectangle</param>
  51.        /// <returns>Flag indicating if the point is included in the rectangle</returns>
  52.        public static bool PointInRectangle(Point A, Point P1, Point P2)
  53.        {
  54.            // First, we eliminate basic cases
  55.            if (A.X < P1.X) return false; // A is at the left of the rectangle
  56.            if (A.X > P2.X) return false; // A is at the right of the rectangle
  57.            if (A.Y < P1.Y) return false; // A is at the top of the rectangle
  58.            if (A.Y > P2.Y) return false; // A is at the bottom of the rectangle
  59.  
  60.            if (A.X <= P2.X && A.X >= P1.X && A.Y <= P2.Y && A.Y >= P1.Y) return true; // A is inside the rectangle
  61.  
  62.            return false; // A is outside
  63.        }
  64.    }
  65.  
  66.    abstract class Pattern
  67.    {
  68.        public Point BoundingBox1, BoundingBox2;
  69.  
  70.        /// <summary>
  71.        /// Check if a pattern overrides this one.
  72.        /// </summary>
  73.        /// <param name="otherPattern">Other pattern that may override this one</param>
  74.        /// <param name="optim1">Use bounding boxes optimization</param>
  75.        /// <param name="optim2">Use circles distances optimization</param>
  76.        /// <param name="optim3">Use point in circle optimization</param>
  77.        /// <returns></returns>
  78.        public bool CheckOverride(Pattern otherPattern, bool optim1, bool optim2, bool optim3)
  79.        {
  80.            // Step 1 : Check bounding boxes (optim1)
  81.            if (optim1)
  82.            {
  83.                if (!MathTools.PointInRectangle(this.BoundingBox1, otherPattern.BoundingBox1, otherPattern.BoundingBox2) && !MathTools.PointInRectangle(this.BoundingBox2, otherPattern.BoundingBox1, otherPattern.BoundingBox2))
  84.                {
  85.                    // Bounding boxes are not overriding
  86.                    return false;
  87.                }
  88.            }
  89.  
  90.            // Step 2 : If both patterns are circles it's very easy to check they are overriding
  91.            if (optim2)
  92.            {
  93.                if (this.GetType() == typeof(Circle) && otherPattern.GetType() == typeof(Circle))
  94.                {
  95.                    Circle c1, c2;
  96.                    c1 = this as Circle;
  97.                    c2 = otherPattern as Circle;
  98.                    if (Math.Pow(c1.Radius + c2.Radius, 2) >= (Math.Pow(c1.Center.X - c2.Center.X, 2) + Math.Pow(c1.Center.Y - c2.Center.X, 2))) return true;
  99.                    return false;
  100.                }
  101.            }
  102.  
  103.            // Step 3 : If one of the pattern is a circle and the other one is a quadrilateral, it's easy to see if a top is included in the circle
  104.            if (optim3)
  105.            {
  106.                Circle c;
  107.                Quadrilateral q;
  108.                if (this.GetType() == typeof(Circle) && otherPattern.GetType() == typeof(Quadrilateral))
  109.                {
  110.                    c = this as Circle;
  111.                    q = otherPattern as Quadrilateral;
  112.                }
  113.                else if (this.GetType() == typeof(Quadrilateral) && otherPattern.GetType() == typeof(Circle))
  114.                {
  115.                    c = otherPattern as Circle;
  116.                    q = this as Quadrilateral;
  117.                }
  118.                else
  119.                {
  120.                    c = null;
  121.                    q = null;
  122.                }
  123.  
  124.                if (c != null && q != null)
  125.                {
  126.                    double r2 = Math.Pow(c.Radius, 2);
  127.                    if (
  128.                        r2 >= Math.Pow(c.Center.X - q.PointA.X, 2) + Math.Pow(c.Center.Y - q.PointA.Y, 2) ||
  129.                        r2 >= Math.Pow(c.Center.X - q.PointB.X, 2) + Math.Pow(c.Center.Y - q.PointB.Y, 2) ||
  130.                        r2 >= Math.Pow(c.Center.X - q.PointC.X, 2) + Math.Pow(c.Center.Y - q.PointC.Y, 2) ||
  131.                        r2 >= Math.Pow(c.Center.X - q.PointD.X, 2) + Math.Pow(c.Center.Y - q.PointD.Y, 2)
  132.                    ) return true;
  133.                }
  134.            }
  135.  
  136.            // Step 4 : We are sure the patterns are close each other, but we are not sure they are overriding... Let's do the classic job...
  137.            throw new NotImplementedException("I'm bored, don't want to browse the net to find the needed equations..." );
  138.        }
  139.    }
  140.  
  141.    class Circle : Pattern
  142.    {
  143.        public Point Center;
  144.        public int Radius;
  145.  
  146.        public Circle(Point center, int radius)
  147.        {
  148.            this.Center = center;
  149.            this.Radius = radius;
  150.  
  151.            this.BoundingBox1 = new Point(center.X - radius, center.Y - radius);
  152.            this.BoundingBox2 = new Point(center.X + radius, center.Y + radius);
  153.        }
  154.    }
  155.  
  156.    class Quadrilateral : Pattern
  157.    {
  158.        public Point PointA;
  159.        public Point PointB;
  160.        public Point PointC;
  161.        public Point PointD;
  162.  
  163.        public Quadrilateral(Point pointA, Point pointB, Point pointC, Point pointD)
  164.        {
  165.            this.PointA = pointA;
  166.            this.PointB = pointB;
  167.            this.PointC = pointC;
  168.            this.PointD = pointD;
  169.  
  170.            this.BoundingBox1 = new Point(Math.Min(Math.Min(pointA.X, pointB.X), Math.Min(pointC.X, pointD.X)), Math.Min(Math.Min(pointA.Y, pointB.Y), Math.Min(pointC.Y, pointD.Y)));
  171.            this.BoundingBox2 = new Point(Math.Max(Math.Max(pointA.X, pointB.X), Math.Max(pointC.X, pointD.X)), Math.Max(Math.Max(pointA.Y, pointB.Y), Math.Max(pointC.Y, pointD.Y)));
  172.        }
  173.    }
  174. }


Message édité par MagicBuzz le 22-06-2007 à 21:37:29
n°1578214
MagicBuzz
Posté le 22-06-2007 à 21:19:56  profilanswer
 

Extrait des résultats :


Quadrilateral 6805 overrides Circle 6848.
Quadrilateral 6807 overrides Circle 7330.
Quadrilateral 6819 might override Circle 7862, but not checked ("I'm bored, don't want to browse the net to find the needed equations..." ).
Quadrilateral 6845 might override Quadrilateral 8639, but not checked ("I'm bored, don't want to browse the net to find the needed equations..." ).
Quadrilateral 6871 might override Quadrilateral 7157, but not checked ("I'm bored, don't want to browse the net to find the needed equations..." ).
Quadrilateral 6875 might override Circle 9346, but not checked ("I'm bored, don't want to browse the net to find the needed equations..." ).
Quadrilateral 6919 overrides Circle 8614.
Circle 6928 overrides Circle 7902.
Quadrilateral 6937 might override Quadrilateral 8743, but not checked ("I'm bored, don't want to browse the net to find the needed equations..." ).
Circle 6964 might override Quadrilateral 9369, but not checked ("I'm bored, don't want to browse the net to find the needed equations..." ).
Circle 6974 might override Quadrilateral 9965, but not checked ("I'm bored, don't want to browse the net to find the needed equations..." ).
Quadrilateral 6979 overrides Circle 8908.
Quadrilateral 6989 overrides Circle 8898.
Circle 6992 overrides Quadrilateral 9323.
Quadrilateral 7001 overrides Circle 7958.
Quadrilateral 7003 overrides Circle 7584.
Quadrilateral 7003 might override Quadrilateral 9293, but not checked ("I'm bored, don't want to browse the net to find the needed equations..." ).
Quadrilateral 7021 overrides Circle 9450.


 
Comme tu peux le voir :
1/ Tous les tests dont aucun résultat n'est affiché on été giclés dès les deux premières optimisations, donc des calculs très simples et rapides à faire
2/ Les deux secondes optimisations permettent de résoudre la moitié des cas, avec des calculs très simples
 
En résumé, ça vaut carrément le coup d'utiliser au moins ces optimisations, puisqu'elles évident un nombre incalculable de calculs complxes inutiles.
 
PS : Et si t'es pas convaincu par mes optimizations de la mort qui tue, voici ce que donne le script lancé deux fois dans la foulée (même jeu de formes) pour 100 formes. Et je rappelle que moi, je ne fais pas les calculs complexes, chercher si des demi-plans se chevauchent (chais pu comment faire, et j'ai pas envie de m'y remettre :D) donc j'imagine effectivement à quel point ça peut être lent chez toi :D
 


Avec les bounding boxes : 0 ms
Sans les bounding boxes : 8546,875 ms


 
A noter qu'enfin, une dernière optimisation peut consister à regrouper tes objets par "zone" en amont, histoire de ne même pas avoir à faire le test de la bounding box lorsqu'on sait à l'avance que les deux formes sont très éloingnées. Ceci doit par contre être fait vraiment en amont, c'est à dire avant que ton programme ne tourne : au lieu de check 10000 formes par exemple, tu check 100 fois 100 formes, en supposant que tu les a regroupées en 100 zones.


Message édité par MagicBuzz le 22-06-2007 à 21:32:41
n°1578252
deadalnix
Posté le 22-06-2007 à 23:18:43  profilanswer
 

c'est bon ca !
 
Tu aurais des pistes dans le meme delire pour la detection de contour ?

n°1578306
MagicBuzz
Posté le 23-06-2007 à 09:43:23  profilanswer
 

"détection de contour", kézako ?

n°1578323
cimourdain
Posté le 23-06-2007 à 11:53:22  profilanswer
 

oui je dois détecter les inclusions aussi. Pour info je bosse avec la bibrairie OpenCV si certain d'entre vous connaissent. J'essayerai vos solutions lundi et je vous tiens au courrant. Merci pour toutes ces pistes.

 

Pour deadalnix, avec cette lib la détection de contour peut se faire très simplement en quelques lignes si ca t'intéresse je te dirais comment faire.


Message édité par cimourdain le 23-06-2007 à 11:58:51
n°1578371
MagicBuzz
Posté le 23-06-2007 à 17:19:55  profilanswer
 

Tiens au fait, je suis en train de remarquer que les tests sur les bounding sont largement insuffisants :) Je te laisse faire un dessin pour voir les (nombreux) cas qui ne sont pas pris en compte :)

n°1578411
cimourdain
Posté le 23-06-2007 à 20:28:18  profilanswer
 

ah ouais ca marche pas finalement cette méthode ? faut faire quoi alors ?

n°1578496
deadalnix
Posté le 24-06-2007 à 13:57:20  profilanswer
 

Si l'idee de la metgode est bonne mais il manque quelq cas partivuliers dans l'implementation.
 
Pour la detection de contour, ca consiste a creer un polygone (on va negliger le cas des cercles sinon ca en finit jamais) qui represente le contour d'un ensemble de polygone.
 
Imagine un emsemble de formes, et colories les toutes de la meme couleur, disons bleu, tu va obtenir une forme bleue. Quel est le polygone qui en est le contour ?

mood
Publicité
Posté le 24-06-2007 à 13:57:20  profilanswer
 

n°1578626
MagicBuzz
Posté le 25-06-2007 à 00:27:34  profilanswer
 

C'est le cas "optim1" qui est foireux dans mon implémentation.
A priori, cette correction couvre tous les cas :
 

Code :
  1. // Step 1 : Check bounding boxes (optim1)
  2.            if (optim1)
  3.            {
  4.                if (
  5.                    // Case 1 : this pattern hasn't a top of it's bounding box inside the other one's
  6.                    !MathTools.PointInRectangle(this.BoundingBox1, otherPattern.BoundingBox1, otherPattern.BoundingBox2) && !MathTools.PointInRectangle(this.BoundingBox2, otherPattern.BoundingBox1, otherPattern.BoundingBox2) &&
  7.                    // Case 2 : the other pattern hasn't a top of it's bounding box inside this one's
  8.                    !MathTools.PointInRectangle(otherPattern.BoundingBox1, this.BoundingBox1, this.BoundingBox2) && !MathTools.PointInRectangle(otherPattern.BoundingBox2, this.BoundingBox1, this.BoundingBox2) &&
  9.                    // Case 3 : the other pattern bounding box isn't crossing this one's (horizontal)
  10.                    !(otherPattern.BoundingBox1.X <= this.BoundingBox1.X && otherPattern.BoundingBox2.X >= this.BoundingBox2.X && otherPattern.BoundingBox1.Y >= this.BoundingBox1.Y && otherPattern.BoundingBox1.Y <= this.BoundingBox2.Y) &&
  11.                    // Case 4 : the other pattern bounding box isn't crossing the other one's
  12.                    !(otherPattern.BoundingBox1.X >= this.BoundingBox1.X && otherPattern.BoundingBox1.X <= this.BoundingBox2.X && otherPattern.BoundingBox1.Y <= this.BoundingBox1.Y && otherPattern.BoundingBox2.Y >= this.BoundingBox1.Y)
  13.                )
  14.                {
  15.                    // Bounding boxes are not overriding
  16.                    return false;
  17.                }
  18.            }


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  Algo pour intersection de figures

 

Sujets relatifs
[Algo]Combinaison d'une liste d'entier[Algo] kakuro
Challenge algoalgo de matching
Algo pour enveler les yeux rougesAide sur un ALGO
algo[Algo] Combinaisons à taille variable d'élements d'un ensemble
Référencement des différents crossOver pour les algorithmes génétiques[algo] heuristiques de profondeur de récursion
Plus de sujets relatifs à : Algo pour intersection de figures


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR