mcs/class/Mono.C5/current/UserGuideExamples/PointLocation.cs

   1 /*\r
   2  Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft\r
   3  Permission is hereby granted, free of charge, to any person obtaining a copy\r
   4  of this software and associated documentation files (the "Software"), to deal\r
   5  in the Software without restriction, including without limitation the rights\r
   6  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
   7  copies of the Software, and to permit persons to whom the Software is\r
   8  furnished to do so, subject to the following conditions:\r
   9  \r
  10  The above copyright notice and this permission notice shall be included in\r
  11  all copies or substantial portions of the Software.\r
  12  \r
  13  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
  14  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
  15  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
  16  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
  17  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
  18  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
  19  SOFTWARE.\r
  20 */\r
  21 \r
  22 using System;\r
  23 using System.Diagnostics;\r
  24 using C5;\r
  25 using SCG = System.Collections.Generic;\r
  26 \r
  27 namespace PointLocation\r
  28 {\r
  29   //public enum Site { Cell,Edge,Outside}\r
  30   /// <summary>\r
  31   /// A line segment with associated data of type T for the cell \r
  32   /// to its right respectively left.\r
  33   /// </summary>\r
  34   public struct Edge<T>\r
  35     {\r
  36       public double xs, ys, xe, ye;\r
  37       \r
  38       public T right, left;\r
  39       \r
  40       public Edge(double xs, double ys, double xe, double ye, T right, T left)\r
  41         {\r
  42           this.xs = xs;\r
  43           this.ys = ys;\r
  44           this.xe = xe;\r
  45           this.ye = ye;\r
  46           this.right = right;\r
  47           this.left = left;\r
  48         }\r
  49       \r
  50       \r
  51       public T Cell(bool upper)\r
  52         {\r
  53           return (DoubleComparer.StaticCompare(xs, xe) < 0) == upper ? left : right;\r
  54         }\r
  55       \r
  56       \r
  57       public override string ToString()\r
  58         {\r
  59           return String.Format("[({0:G5};{1:G5})->({2:G5};{3:G5})/R:{4} L:{5}]", xs, ys, xe, ye, right, left);\r
  60         }\r
  61     }\r
  62   \r
  63   \r
  64   \r
  65   /// <summary>\r
  66   /// A data structure for point location in a plane divided into\r
  67   /// cells by edges. This is the classical use of persistent trees\r
  68   /// by Sarnak and Tarjan [?]. See de Berg et al for alternatives.\r
  69   /// \r
  70   /// The internal data is an outer sorted dictionary that maps each\r
  71   /// x coordinate of an endpoint of some edge to an inner sorted set\r
  72   /// of the edges crossing or touching the vertical line at that x\r
  73   /// coordinate, the edges being ordered by their y coordinates\r
  74   /// to the immediate right of x. Lookup of a point (x,y) is done by\r
  75   /// finding the predecessor of x cell the outer dictionary and then locating\r
  76   /// the edges above and below (x,y) by searching in the inner sorted set.\r
  77   /// \r
  78   /// The creation of the inner sorted sets is done by maintaining a\r
  79   /// (persistent) tree of edges, inserting and deleting edges according\r
  80   /// to a horzontal sweep of the edges while saving a snapshot of the\r
  81   /// inner tree in the outer dictionary at each new x coordinate.\r
  82   ///\r
  83   /// If there are n edges, there will be 2n updates to the inner tree,\r
  84   /// and in the worst case, the inner tree will have size Omega(n) for\r
  85   /// Omega(n) snapshots. We will use O(n*logn) time and O(n) space for\r
  86   /// sorting the endpoints. If we use a nodecopying persistent inner tree,\r
  87   /// we will use O(n) space and time for building the data structure proper.\r
  88   /// If we use a pathcopy persistent tree, we will use O(n*logn) time and\r
  89   /// space for the data struicture. Finally, if we use a non-persistent\r
  90   /// tree with a full copy for snapshot, we may use up to O(n^2) space and\r
  91   /// time for building the datastructure.\r
  92   ///\r
  93   /// Lookup will take O(logn) time in any case, but taking the memory\r
  94   /// hierarchy into consideration, a low space use is very beneficial\r
  95   /// for large problems.\r
  96   ///\r
  97   /// The code assumes that the given set of edges is correct, in particular\r
  98   /// that they do not touch at interior points (e.g. cross or coincide). \r
  99   /// </summary>\r
 100         \r
 101   public class PointLocator<T>\r
 102   {\r
 103     private TreeDictionary<double,ISorted<Edge<T>>> htree;\r
 104     \r
 105     private EdgeComparer<T> lc = new EdgeComparer<T>();\r
 106     \r
 107     private SCG.IComparer<EndPoint> epc = new EndPoint(0, 0, true, 0);\r
 108     \r
 109     private DoubleComparer dc = new DoubleComparer();\r
 110     \r
 111     private TreeDictionary<EndPoint,Edge<T>> endpoints;\r
 112     \r
 113     private int count;\r
 114     \r
 115     private bool built = false;\r
 116     \r
 117     public PointLocator()\r
 118     {\r
 119       //htree = new TreeDictionary<double,TreeSet<Edge<T>>>(dc);\r
 120       endpoints = new TreeDictionary<EndPoint,Edge<T>>(epc);\r
 121     }\r
 122     \r
 123     public PointLocator(SCG.IEnumerable<Edge<T>> edges)\r
 124     {\r
 125       //htree = new TreeDictionary<double,TreeSet<Edge<T>>>(dc);\r
 126       endpoints = new TreeDictionary<EndPoint,Edge<T>>(epc);\r
 127       foreach (Edge<T> edge in edges)\r
 128         add(edge);\r
 129     }\r
 130     \r
 131     private void add(Edge<T> edge)\r
 132     {\r
 133       int c = DoubleComparer.StaticCompare(edge.xs, edge.xe);\r
 134       \r
 135       if (c == 0)\r
 136         return;\r
 137       \r
 138       endpoints.Add(new EndPoint(edge.xs, edge.ys, c < 0, count), edge);\r
 139       endpoints.Add(new EndPoint(edge.xe, edge.ye, c > 0, count++), edge);\r
 140     }\r
 141 \r
 142     public void Add(Edge<T> edge)\r
 143     {\r
 144       if (built)\r
 145         throw new InvalidOperationException("PointLocator static when built");\r
 146       add(edge);\r
 147     }\r
 148     \r
 149     public void AddAll(SCG.IEnumerable<Edge<T>> edges)\r
 150     {\r
 151       if (built)\r
 152         throw new InvalidOperationException("PointLocator static when built");\r
 153       \r
 154       foreach (Edge<T> edge in edges)\r
 155         add(edge);\r
 156     }\r
 157     \r
 158     public void Build()\r
 159     {\r
 160       //htree.Clear();\r
 161       htree = new TreeDictionary<double,ISorted<Edge<T>>>(dc);\r
 162       \r
 163       TreeSet<Edge<T>> vtree = new TreeSet<Edge<T>>(lc);\r
 164       double lastx = Double.NegativeInfinity;\r
 165       \r
 166       foreach (KeyValuePair<EndPoint,Edge<T>> p in endpoints)\r
 167         {\r
 168           if (dc.Compare(p.Key.x,lastx)>0)\r
 169             {\r
 170               //Put an empty snapshot at -infinity!\r
 171               htree[lastx] = (ISorted<Edge<T>>)(vtree.Snapshot());\r
 172               lc.X = lastx = p.Key.x;\r
 173               lc.compareToRight = false;\r
 174             }\r
 175           \r
 176           if (p.Key.start)\r
 177             {\r
 178               if (!lc.compareToRight)\r
 179                 lc.compareToRight = true;\r
 180               Debug.Assert(vtree.Check());\r
 181               bool chk = vtree.Add(p.Value);\r
 182               Debug.Assert(vtree.Check());\r
 183               \r
 184               Debug.Assert(chk,"edge was not added!",""+p.Value);\r
 185             }\r
 186           else\r
 187             {\r
 188               Debug.Assert(!lc.compareToRight);\r
 189               \r
 190               Debug.Assert(vtree.Check("C"));\r
 191               \r
 192               bool chk = vtree.Remove(p.Value);\r
 193               Debug.Assert(vtree.Check("D"));\r
 194               \r
 195               Debug.Assert(chk,"edge was not removed!",""+p.Value);\r
 196             }\r
 197         }\r
 198       lc.compareToRight = true;\r
 199       \r
 200       htree[lastx] = (TreeSet<Edge<T>>)(vtree.Snapshot());\r
 201       built = true;\r
 202     }\r
 203     \r
 204     \r
 205     /*public void Clear()\r
 206       {\r
 207       endpoints.Clear();\r
 208       htree.Clear();\r
 209       }*/\r
 210     /// <summary>\r
 211     /// Find the cell, if any, containing (x,y).\r
 212     /// </summary>\r
 213     /// <param name="x">x coordinate of point</param>\r
 214     /// <param name="y">y coordinate of point</param>\r
 215     /// <param name="below">Associate data of cell according to edge below</param>\r
 216     /// <param name="above">Associate data of cell according to edge above</param>\r
 217     /// <returns>True if point is inside some cell</returns>\r
 218     public bool Place(double x, double y, out T cell)\r
 219     {\r
 220       if (!built)\r
 221         throw new InvalidOperationException("PointLocator must be built first");\r
 222       \r
 223       KeyValuePair<double,ISorted<Edge<T>>> p = htree.WeakPredecessor(x);\r
 224       \r
 225       //if (DoubleComparer.StaticCompare(cell.key,x)==0)\r
 226       //Just note it, we have thrown away the vertical edges!\r
 227       Edge<T> low, high;\r
 228       bool lval, hval;\r
 229       PointComparer<T> c = new PointComparer<T>(x, y);\r
 230       \r
 231       //Return value true here means we are at an edge.\r
 232       //But note that if x is in htree.Keys, we may be at a\r
 233       //vertical edge even if the return value is false here.\r
 234       //Therefore we do not attempt to sort out completely the case\r
 235       //where (x,y) is on an edge or even on several edges,\r
 236       //and just deliver some cell it is in.\r
 237       p.Value.Cut(c, out low, out lval, out high, out hval);\r
 238       if (!lval || !hval)\r
 239         {\r
 240           cell = default(T);\r
 241           return false;\r
 242         }\r
 243       else\r
 244         {\r
 245           cell = low.Cell(true);//high.Cell(false);\r
 246           return true;\r
 247         }\r
 248     }\r
 249     \r
 250     public void Place(double x, double y, out T upper, out bool hval, out T lower, out bool lval)\r
 251     {\r
 252       if (!built)\r
 253         throw new InvalidOperationException("PointLocator must be built first");\r
 254       \r
 255       KeyValuePair<double,ISorted<Edge<T>>> p = htree.WeakPredecessor(x);\r
 256       \r
 257       //if (DoubleComparer.StaticCompare(cell.key,x)==0)\r
 258       //Just note it, we have thrown away the vertical edges!\r
 259       Edge<T> low, high;\r
 260       PointComparer<T> c = new PointComparer<T>(x, y);\r
 261       \r
 262       //Return value true here means we are at an edge.\r
 263       //But note that if x is in htree.Keys, we may be at a\r
 264       //vertical edge even if the return value is false here.\r
 265       //Therefore we do not attempt to sort out completely the case\r
 266       //where (x,y) is on an edge or even on several edges,\r
 267       //and just deliver some cell it is in.\r
 268       p.Value.Cut(c, out low, out lval, out high, out hval);\r
 269       upper = hval ? high.Cell(false) : default(T);\r
 270       lower = lval ? low.Cell(true) : default(T);\r
 271       return; \r
 272     }\r
 273     \r
 274     public void Test(double x, double y)\r
 275     {\r
 276       T cell;\r
 277       \r
 278       if (Place(x, y, out cell))\r
 279         Console.WriteLine("({0}; {1}): <- {2} ", x, y, cell);\r
 280       else\r
 281         Console.WriteLine("({0}; {1}): -", x, y);\r
 282     }\r
 283     \r
 284     /// <summary>\r
 285     /// Endpoint of an edge with ordering/comparison according to x\r
 286     /// coordinates with arbitration by the id field. \r
 287     /// The client is assumed to keep the ids unique.\r
 288     /// </summary>\r
 289     public /*private*/ struct EndPoint: SCG.IComparer<EndPoint>\r
 290     {\r
 291       public double x, y;\r
 292       \r
 293       public bool start;\r
 294       \r
 295       private int id;\r
 296       \r
 297       \r
 298       public EndPoint(double x, double y, bool left, int id)\r
 299         {\r
 300           this.x = x;this.y = y;this.start = left;this.id = id;\r
 301         }\r
 302       \r
 303       \r
 304       public int Compare(EndPoint a, EndPoint b)\r
 305         {\r
 306           int c = DoubleComparer.StaticCompare(a.x, b.x);\r
 307           \r
 308           return c != 0 ? c : (a.start && !b.start) ? 1 : (!a.start && b.start) ? -1 : a.id < b.id ? -1 : a.id > b.id ? 1 : 0;\r
 309         }\r
 310     }\r
 311   }\r
 312 \r
 313   /// <summary>\r
 314   /// Compare two doubles with tolerance. \r
 315   /// </summary>\r
 316   class DoubleComparer: SCG.IComparer<double>\r
 317   {\r
 318     private const double eps = 1E-10;\r
 319     \r
 320     public int Compare(double a, double b)\r
 321     {\r
 322       return a > b + eps ? 1 : a < b - eps ? -1 : 0;\r
 323     }\r
 324 \r
 325     public static int StaticCompare(double a, double b)\r
 326     {\r
 327       return a > b + eps ? 1 : a < b - eps ? -1 : 0;\r
 328     }\r
 329   }\r
 330 \r
 331   /// <summary>\r
 332   /// Compare a given point (x,y) to edges: is the point above, at or below\r
 333   /// the edge. Assumes edges not vertical. \r
 334   /// </summary>\r
 335   class PointComparer<T>: IComparable<Edge<T>>\r
 336   {\r
 337     private double x, y;\r
 338     \r
 339     public PointComparer(double x, double y)\r
 340     {\r
 341       this.x = x; this.y = y;\r
 342     }\r
 343     \r
 344     public int CompareTo(Edge<T> a)\r
 345     {\r
 346       double ya = (a.ye - a.ys) / (a.xe - a.xs) * (x - a.xs) + a.ys;\r
 347       \r
 348       return DoubleComparer.StaticCompare(y, ya);\r
 349     }\r
 350     \r
 351     public bool Equals(Edge<T> a) { return CompareTo(a) == 0; }\r
 352   }\r
 353 \r
 354   /// <summary>\r
 355   /// Compare two edges at a given x coordinate:\r
 356   /// Compares the y-coordinate  to the immediate right of x of the two edges.\r
 357   /// Assumes edges to be compared are not vertical.\r
 358   /// </summary>\r
 359   class EdgeComparer<T>: SCG.IComparer<Edge<T>>\r
 360   {\r
 361     private double x;\r
 362     \r
 363     public bool compareToRight = true;\r
 364     \r
 365     public double X { get { return x; } set { x = value; } }\r
 366     \r
 367     public int Compare(Edge<T> line1, Edge<T> line2)\r
 368     {\r
 369       double a1 = (line1.ye - line1.ys) / (line1.xe - line1.xs);\r
 370       double a2 = (line2.ye - line2.ys) / (line2.xe - line2.xs);\r
 371       double ya = a1 * (x - line1.xs) + line1.ys;\r
 372       double yb = a2 * (x - line2.xs) + line2.ys;\r
 373       int c = DoubleComparer.StaticCompare(ya, yb);\r
 374       \r
 375       return c != 0 ? c : (compareToRight ? 1 : -1) * DoubleComparer.StaticCompare(a1, a2);\r
 376     }\r
 377   }\r
 378 \r
 379   namespace Test\r
 380     {\r
 381       public class Ugly : EnumerableBase<Edge<int>>, SCG.IEnumerable<Edge<int>>, SCG.IEnumerator<Edge<int>>\r
 382       {\r
 383         private int level = -1, maxlevel;\r
 384         \r
 385         private bool leftend = false;\r
 386         \r
 387         public Ugly(int maxlevel)\r
 388         {\r
 389           this.maxlevel = maxlevel;\r
 390         }\r
 391         \r
 392         public override SCG.IEnumerator<Edge<int>> GetEnumerator()\r
 393         {\r
 394           return (SCG.IEnumerator<Edge<int>>)MemberwiseClone();\r
 395         }\r
 396         \r
 397         public void Reset()\r
 398         {\r
 399           level = -1;\r
 400           leftend = false;\r
 401         }\r
 402         \r
 403         public bool MoveNext()\r
 404         {\r
 405           if (level > maxlevel)\r
 406             throw new InvalidOperationException();\r
 407           \r
 408           if (leftend)\r
 409             {\r
 410               leftend = false;\r
 411               return true;\r
 412             }\r
 413           else\r
 414             {\r
 415               leftend = true;\r
 416               return ++level <= maxlevel;\r
 417             }\r
 418         }\r
 419         \r
 420         public Edge<int> Current\r
 421         {\r
 422           get\r
 423             {\r
 424               if (level < 0 || level > maxlevel)\r
 425                 throw new InvalidOperationException();\r
 426               \r
 427               double y = (level * 37) % maxlevel;\r
 428               double deltax = leftend ? 1 : maxlevel;\r
 429               \r
 430               if (leftend)\r
 431                 return new Edge<int>(0, y, level, y - 0.5, 0, 0);\r
 432               else\r
 433                 return new Edge<int>(level, y - 0.5, level, y, 0, 0);\r
 434             }\r
 435         }\r
 436         \r
 437         \r
 438         public void Dispose() { }\r
 439         \r
 440 #region IEnumerable Members\r
 441 \r
 442         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()\r
 443         {\r
 444           throw new Exception("The method or operation is not implemented.");\r
 445         }\r
 446 \r
 447 #endregion\r
 448         \r
 449 #region IEnumerator Members\r
 450         \r
 451         object System.Collections.IEnumerator.Current\r
 452         {\r
 453           get { throw new Exception("The method or operation is not implemented."); }\r
 454         }\r
 455         \r
 456         void System.Collections.IEnumerator.Reset()\r
 457         {\r
 458           throw new Exception("The method or operation is not implemented.");\r
 459         }\r
 460         \r
 461 #endregion\r
 462       }\r
 463 \r
 464       public class TestUgly\r
 465       {\r
 466         private Ugly ugly;\r
 467         \r
 468         private int d;\r
 469         \r
 470         private PointLocator<int> pointlocator;\r
 471         \r
 472         \r
 473         public TestUgly(int d)\r
 474         {\r
 475           this.d = d;\r
 476           ugly = new Ugly(d);\r
 477         }\r
 478         \r
 479         \r
 480         public double Traverse()\r
 481         {\r
 482           double xsum = 0;\r
 483           \r
 484           foreach (Edge<int> e in ugly) xsum += e.xe;\r
 485           \r
 486           return xsum;\r
 487         }\r
 488         \r
 489         public bool LookUp(int count, int seed)\r
 490         {\r
 491           Random random = new Random(seed);\r
 492           bool res = false;\r
 493           \r
 494           for (int i = 0; i < count; i++)\r
 495             {\r
 496               int cell;\r
 497               \r
 498               res ^= pointlocator.Place(random.NextDouble() * d, random.NextDouble() * d, out cell);\r
 499             }\r
 500           \r
 501           return res;\r
 502         }\r
 503 \r
 504         public static void Run(string[] args)\r
 505         {\r
 506           int d = args.Length >= 2 ? int.Parse(args[1]) : 400;//00;\r
 507           int repeats = args.Length >= 3 ? int.Parse(args[2]) : 10;\r
 508           int lookups = args.Length >= 4 ? int.Parse(args[3]) : 500;//00;\r
 509           \r
 510           new TestUgly(d).run(lookups);\r
 511         }\r
 512         \r
 513         \r
 514         public void run(int lookups)\r
 515         {\r
 516           double s = 0;\r
 517           \r
 518           s += Traverse();\r
 519           \r
 520           pointlocator = new PointLocator<int>(ugly);\r
 521           pointlocator.Build();\r
 522           \r
 523           LookUp(lookups, 567);\r
 524         }\r
 525       }\r
 526       \r
 527       public class Lattice : EnumerableBase<Edge<string>>, SCG.IEnumerable<Edge<string>>, SCG.IEnumerator<Edge<string>>, System.Collections.IEnumerator\r
 528       {\r
 529         private int currenti = -1, currentj = 0, currentid = 0;\r
 530         \r
 531         private bool currenthoriz = true;\r
 532         \r
 533         private int maxi, maxj;\r
 534         \r
 535         private double a11 = 1, a21 = -1, a12 = 1, a22 = 1;\r
 536         \r
 537         public Lattice(int maxi, int maxj, double a11, double a21, double a12, double a22)\r
 538         {\r
 539           this.maxi = maxi;\r
 540           this.maxj = maxj;\r
 541           this.a11 = a11;\r
 542           this.a12 = a12;\r
 543           this.a21 = a21;\r
 544           this.a22 = a22;\r
 545         }\r
 546 \r
 547         public Lattice(int maxi, int maxj)\r
 548         {\r
 549           this.maxi = maxi;\r
 550           this.maxj = maxj;\r
 551         }\r
 552         \r
 553         public override SCG.IEnumerator<Edge<string>> GetEnumerator()\r
 554         {\r
 555           return (SCG.IEnumerator<Edge<string>>)MemberwiseClone();\r
 556         }\r
 557         \r
 558         public void Reset()\r
 559         {\r
 560           currenti = -1;\r
 561           currentj = 0;\r
 562           currentid = -1;\r
 563           currenthoriz = true;\r
 564         }\r
 565         \r
 566         public bool MoveNext()\r
 567         {\r
 568           currentid++;\r
 569           if (currenthoriz)\r
 570             {\r
 571               if (++currenti >= maxi)\r
 572                 {\r
 573                   if (currentj >= maxj)\r
 574                     return false;\r
 575                   \r
 576                   currenti = 0;\r
 577                   currenthoriz = false;\r
 578                 }\r
 579               \r
 580               return true;\r
 581             }\r
 582           else\r
 583             {\r
 584               if (++currenti > maxi)\r
 585                 {\r
 586                   currenti = 0;\r
 587                   currenthoriz = true;\r
 588                   if (++currentj > maxj)\r
 589                     return false;\r
 590                 }\r
 591               \r
 592               return true;\r
 593             }\r
 594         }\r
 595         \r
 596         \r
 597         private string i2l(int i)\r
 598         {\r
 599           int ls = 0, j = i;\r
 600           \r
 601           do { ls++; j = j / 26 - 1; } while (j >= 0);\r
 602           \r
 603           char[] res = new char[ls];\r
 604           \r
 605           while (ls > 0) { res[--ls] = (char)(65 + i % 26); i = i / 26 - 1; }\r
 606           \r
 607           //res[0]--;\r
 608           return new String(res);\r
 609         }\r
 610         \r
 611         \r
 612         private string fmtid(int i, int j)\r
 613         {\r
 614           return "";//cell + ";" + cell;\r
 615           /*if (cell < 0 || cell < 0 || cell >= maxi || cell >= maxj)\r
 616             return "Outside";\r
 617             \r
 618             return String.Format("{0}{1}", i2l(cell), cell);*/\r
 619         }\r
 620         \r
 621         \r
 622         public Edge<string> Current\r
 623         {\r
 624           get\r
 625             {\r
 626               if (currenti >= maxi && currentj >= maxj)\r
 627                 throw new InvalidOperationException();\r
 628               \r
 629               double xs = currenti * a11 + currentj * a12;\r
 630               double ys = currenti * a21 + currentj * a22;\r
 631               double deltax = currenthoriz ? a11 : a12;\r
 632               double deltay = currenthoriz ? a21 : a22;\r
 633               string r = fmtid(currenti, currenthoriz ? currentj - 1 : currentj);\r
 634               string l = fmtid(currenthoriz ? currenti : currenti - 1, currentj);\r
 635               \r
 636               return new Edge<string>(xs, ys, xs + deltax, ys + deltay, r, l);\r
 637             }\r
 638         }\r
 639         \r
 640         \r
 641         public void Dispose() { }\r
 642         \r
 643 #region IEnumerable Members\r
 644         \r
 645         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()\r
 646         {\r
 647           throw new Exception("The method or operation is not implemented.");\r
 648         }\r
 649         \r
 650 #endregion\r
 651         \r
 652 #region IEnumerator Members\r
 653         \r
 654         object System.Collections.IEnumerator.Current\r
 655         {\r
 656           get { throw new Exception("The method or operation is not implemented."); }\r
 657         }\r
 658         \r
 659         bool System.Collections.IEnumerator.MoveNext()\r
 660         {\r
 661           throw new Exception("The method or operation is not implemented.");\r
 662         }\r
 663         \r
 664         void System.Collections.IEnumerator.Reset()\r
 665         {\r
 666           throw new Exception("The method or operation is not implemented.");\r
 667         }\r
 668         \r
 669 #endregion\r
 670       }\r
 671       \r
 672       public class TestLattice\r
 673       {\r
 674         private Lattice lattice;\r
 675         \r
 676         private int d;\r
 677         \r
 678         private PointLocator<string> pointlocator;\r
 679         \r
 680         \r
 681         public TestLattice(int d)\r
 682         {\r
 683           this.d = d;\r
 684           lattice = new Lattice(d, d, 1, 0, 0, 1);\r
 685         }\r
 686 \r
 687         public TestLattice(int d, double shear)\r
 688         {\r
 689           this.d = d;\r
 690           lattice = new Lattice(d, d, 1, 0, shear, 1);\r
 691         }\r
 692 \r
 693         public double Traverse()\r
 694         {\r
 695           double xsum = 0;\r
 696           \r
 697           foreach (Edge<string> e in lattice)   xsum += e.xe;\r
 698           \r
 699           return xsum;\r
 700         }\r
 701         \r
 702         \r
 703         public bool LookUp(int count, int seed)\r
 704         {\r
 705           Random random = new Random(seed);\r
 706           bool res = false;\r
 707           \r
 708           for (int i = 0; i < count; i++)\r
 709             {\r
 710               string cell;\r
 711               \r
 712               res ^= pointlocator.Place(random.NextDouble() * d, random.NextDouble() * d, out cell);\r
 713             }\r
 714           \r
 715           return res;\r
 716         }\r
 717         \r
 718         \r
 719         public static void Run()\r
 720         {\r
 721           int d = 200;\r
 722           int repeats = 2;\r
 723           int lookups = 50000;\r
 724           TestLattice tl = null;\r
 725           \r
 726           Console.WriteLine("TestLattice Run({0}), means over {1} repeats:", d, repeats);\r
 727           tl = new TestLattice(d, 0.000001);\r
 728 \r
 729           tl.Traverse();\r
 730           \r
 731           tl.pointlocator = new PointLocator<string>();\r
 732           \r
 733           tl.pointlocator.AddAll(tl.lattice);\r
 734           \r
 735           tl.pointlocator.Build();\r
 736           \r
 737           tl.LookUp(lookups, 567);\r
 738         }\r
 739         \r
 740         \r
 741         public void BasicRun()\r
 742         {\r
 743           pointlocator.Test(-0.5, -0.5);\r
 744           pointlocator.Test(-0.5, 0.5);\r
 745           pointlocator.Test(-0.5, 1.5);\r
 746           pointlocator.Test(0.5, -0.5);\r
 747           pointlocator.Test(0.5, 0.5);\r
 748           pointlocator.Test(0.5, 1.5);\r
 749           pointlocator.Test(1.5, -0.5);\r
 750           pointlocator.Test(1.5, 0.5);\r
 751           pointlocator.Test(1.5, 1.5);\r
 752           pointlocator.Test(1.5, 4.99);\r
 753           pointlocator.Test(1.5, 5);\r
 754           pointlocator.Test(1.5, 5.01);\r
 755           pointlocator.Test(1.99, 4.99);\r
 756           pointlocator.Test(1.99, 5);\r
 757           pointlocator.Test(1.99, 5.01);\r
 758           pointlocator.Test(2, 4.99);\r
 759           pointlocator.Test(2, 5);\r
 760           pointlocator.Test(2, 5.01);\r
 761           pointlocator.Test(2.01, 4.99);\r
 762           pointlocator.Test(2.01, 5);\r
 763           pointlocator.Test(2.01, 5.01);\r
 764         }\r
 765       }\r
 766     }\r
 767 \r
 768   public class TestPointLocation {\r
 769     public static void Main(String[] args) {\r
 770       Test.TestUgly.Run(new String[0]);\r
 771     }\r
 772   }\r
 773 }\r
 774 \r