Code :
using System; using System.Drawing; namespace Geometry { class Program { static void Main(string[] args) { Pattern [] patternList = new Pattern [10000]; // Initialize patternList for (int i = 0, cpt = patternList.Length; i < cpt; ) { patternList [i++ ] = new Circle (new Point (r. Next(10000), r. Next(10000)), r. Next(50)); Point basePoint = new Point (r. Next(10000), r. Next(10000)); 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))); } // Check overrides for (int i = 0, cpt = patternList.Length; i < cpt - 1; i++) { for (int j = i + 1; j < cpt; j++) { try { if (patternList[i].CheckOverride(patternList[j], true, true, true)) { Console.WriteLine("{0} {1} overrides {2} {3}.", patternList[i].GetType().Name, i, patternList[j].GetType().Name, j); } } catch (NotImplementedException ex) { Console.WriteLine("{0} {1} might override {2} {3}, but not checked (\"{4}\" ).", patternList[i].GetType().Name, i, patternList[j].GetType().Name, j, ex.Message); } } } Console.ReadKey(); } } abstract class MathTools { /// <summary> /// Checks if the point A is inside the retangle defined by P1 and P2 /// </summary> /// <param name="A">Point to check</param> /// <param name="P1">Upper left corner of the rectangle</param> /// <param name="P2">Lower right corner of the rectangle</param> /// <returns>Flag indicating if the point is included in the rectangle</returns> public static bool PointInRectangle(Point A, Point P1, Point P2) { // First, we eliminate basic cases if (A.X < P1.X) return false; // A is at the left of the rectangle if (A.X > P2.X) return false; // A is at the right of the rectangle if (A.Y < P1.Y) return false; // A is at the top of the rectangle if (A.Y > P2.Y) return false; // A is at the bottom of the rectangle if (A.X <= P2.X && A.X >= P1.X && A.Y <= P2.Y && A.Y >= P1.Y) return true; // A is inside the rectangle return false; // A is outside } } abstract class Pattern { public Point BoundingBox1, BoundingBox2; /// <summary> /// Check if a pattern overrides this one. /// </summary> /// <param name="otherPattern">Other pattern that may override this one</param> /// <param name="optim1">Use bounding boxes optimization</param> /// <param name="optim2">Use circles distances optimization</param> /// <param name="optim3">Use point in circle optimization</param> /// <returns></returns> public bool CheckOverride(Pattern otherPattern, bool optim1, bool optim2, bool optim3) { // Step 1 : Check bounding boxes (optim1) if (optim1) { if (!MathTools.PointInRectangle(this.BoundingBox1, otherPattern.BoundingBox1, otherPattern.BoundingBox2) && !MathTools.PointInRectangle(this.BoundingBox2, otherPattern.BoundingBox1, otherPattern.BoundingBox2)) { // Bounding boxes are not overriding return false; } } // Step 2 : If both patterns are circles it's very easy to check they are overriding if (optim2) { if (this. GetType() == typeof(Circle ) && otherPattern. GetType() == typeof(Circle )) { Circle c1, c2; c1 = this as Circle; c2 = otherPattern as Circle; 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; return false; } } // 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 if (optim3) { Circle c; Quadrilateral q; if (this. GetType() == typeof(Circle ) && otherPattern. GetType() == typeof(Quadrilateral )) { c = this as Circle; q = otherPattern as Quadrilateral; } else if (this. GetType() == typeof(Quadrilateral ) && otherPattern. GetType() == typeof(Circle )) { c = otherPattern as Circle; q = this as Quadrilateral; } else { c = null; q = null; } if (c != null && q != null) { double r2 = Math.Pow(c.Radius, 2); if ( r2 >= Math.Pow(c.Center.X - q.PointA.X, 2) + Math.Pow(c.Center.Y - q.PointA.Y, 2) || r2 >= Math.Pow(c.Center.X - q.PointB.X, 2) + Math.Pow(c.Center.Y - q.PointB.Y, 2) || r2 >= Math.Pow(c.Center.X - q.PointC.X, 2) + Math.Pow(c.Center.Y - q.PointC.Y, 2) || r2 >= Math.Pow(c.Center.X - q.PointD.X, 2) + Math.Pow(c.Center.Y - q.PointD.Y, 2) ) return true; } } // 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... throw new NotImplementedException ("I'm bored, don't want to browse the net to find the needed equations..." ); } } class Circle : Pattern { public Point Center; public int Radius; public Circle(Point center, int radius) { this.Center = center; this.Radius = radius; this. BoundingBox1 = new Point (center. X - radius, center. Y - radius ); this. BoundingBox2 = new Point (center. X + radius, center. Y + radius ); } } class Quadrilateral : Pattern { public Point PointA; public Point PointB; public Point PointC; public Point PointD; public Quadrilateral(Point pointA, Point pointB, Point pointC, Point pointD) { this.PointA = pointA; this.PointB = pointB; this.PointC = pointC; this.PointD = pointD; 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))); 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))); } } }
|
) donc j'imagine effectivement à quel point ça peut être lent chez toi 
Je te laisse faire un dessin pour voir les (nombreux) cas qui ne sont pas pris en compte