【算法】十一月阳光下的阴影面积

【算法】十一月阳光下的阴影面积 十一月阳光下的阴影面积 算法

十一月的阳光透过窗户,照射在一位笑起来甜美、青春洋溢的女子的办公桌上。小悦,一个总是以高马尾造型亮相的软件工程师,展现出她的干练与活力。那乌黑亮丽的长发轻盈飘动,仿佛在诉说着她的独特魅力。她的眉眼如画,那双明亮的眼睛里闪烁着对知识的渴望和对技术挑战的热情。

这一天,她收到了一封来自医院的邮件,邮件中提到的扫描设备技术更新问题让她感到有些挑战。然而,对于技术挑战,小悦总是充满了好奇心和热情。她决定主动联系医院,表达自己愿意参与这个项目的意愿。幸运的是,医院方面很快回复了她的邮件,并安排了一次电话会议。

在电话会议中,小悦与医院的管理人员和相关领域的专家进行了交流。他们的声音充满了对新技术和新思维的渴望。小悦也意识到这次机会对于自己的事业发展可能是一个重大的突破。

不久之后,小悦成功加入了医院方面的团队。在团队中,她发现了很多优秀的专家和工程师。其中有一位资深医生对扫描设备的需求非常了解,而另一位工程师则对图像处理算法有深入的研究。小悦深知自己在这个团队中担任着关键的角色,必须充分发挥自己的优势。

在团队的合作中,小悦与大家建立了良好的合作关系。她不断地与团队成员沟通和交流,了解他们的需求和想法。她的声音总是温柔而自信,让人感到安心和信任。同时,她也向团队成员分享了自己的经验和专业知识,为项目的进展做出了巨大的贡献。

然而,随着项目的深入,小悦逐渐发现了一些技术难题。其中最大的问题是如何计算阴影部分的面积并集。为了解决这个问题,她不断地查阅文献、研究算法,并尝试了多种方法。有时候,她会陷入深深的困境,甚至整晚都无法入睡。但是,她从未放弃过对这个问题的探索和解决。

经过一段时间的努力,小悦终于提出了一种有效的方法来计算阴影部分的面积并集。这个方法不仅得到了团队的认可和支持,也成功地解决了项目中的一大难题。小悦的贡献让整个团队都感到非常惊喜和敬佩。

在接下来的时间中,小悦和团队继续努力工作,终于成功地开发出了一款新的扫描设备程序设计。这款程序采用了小悦提出的阴影面积计算方法,有效地提高了扫描的准确性和效率。医院方面对这款程序非常满意,并决定将其投入使用。

在这个过程中,小悦学到了很多东西。她不仅在技术方面取得了突破和成长,还学会了如何与不同背景的人合作和沟通。她深刻地认识到人际关系的重要性以及如何利用人际关系来拓展自己的视野和能力。同时,她也体验到了帮助他人的喜悦和成就感。


小悦面临的问题是,医学影像重建:医学影像(如CT、MRI等)通常是由多个切片图像组成的,这些图像可能存在重叠或交叉的区域。矩形面积并集算法可以用于计算这些图像之间的重叠区域,从而实现准确的图像重建和融合。

她需要开发一个名为Calculate的方法,该方法接受一个二维数组作为参数,其中每个子数组表示一个矩形的坐标。在这个例子中,三个矩形的坐标分别为[1,2,5,6]、[1,3,4,5]和[3,1,5,4]。并返回期望的面积并集。

每个矩形表示为:[x0,y0,x1,y1]
(x0,y0)-矩形左下角的坐标
(x1,y1)-矩形右上角的坐标

图例(面积=18):


 算法实现1:

 1 private class Rectangle // 定义一个名为Rectangle的私有类
 2 {
 3     public long x0; // 矩形的左边界
 4     public long y0; // 矩形的底边界
 5     public long x1; // 矩形的右边界
 6     public long y1; // 矩形的顶边界
 7     public bool ToDelete = false; // 标记是否需要删除该矩形
 8 
 9     public Rectangle(long x0, long y0, long x1, long y1) // 构造函数,用于初始化矩形对象的边界值
10     {
11         this.x0 = x0;
12         this.x1 = x1;
13         this.y0 = y0;
14         this.y1 = y1;
15     }
16 
17     public long S() // 计算矩形的面积
18     {
19         return (x1 - x0) * (y1 - y0);
20     }
21 
22     public bool IsInside(Rectangle r) // 判断当前矩形是否完全包含另一个矩形r
23     {
24         return ((r.x0 >= x0) && (r.x1 <= x1) && (r.y0 >= y0) && (r.y1 <= y1)) ? true : false;
25     }
26 
27     public bool IsOutside(Rectangle r) // 判断当前矩形是否完全在另一个矩形r的外部
28     {
29         return ((r.x0 >= x1) || (r.x1 <= x0) || (r.y0 >= y1) || (r.y1 <= y0)) ? true : false;
30     }
31 
32     public List<Rectangle> GetIntersection(Rectangle r) // 获取当前矩形与另一个矩形r的相交部分
33     {
34         List<Rectangle> rests = new List<Rectangle>();
35         if (r.x0 < x0)
36             rests.Add(new Rectangle(r.x0, r.y0, x0, r.y1));
37         if (r.x1 > x1)
38             rests.Add(new Rectangle(x1, r.y0, r.x1, r.y1));
39         if (r.y0 < y0)
40             rests.Add(new Rectangle(Math.Max(r.x0, x0), r.y0, Math.Min(r.x1, x1), y0));
41         if (r.y1 > y1)
42             rests.Add(new Rectangle(Math.Max(r.x0, x0), y1, Math.Min(r.x1, x1), r.y1));
43         return rests;
44     }
45 }
46 
47 public static long Calculate(IEnumerable<int[]> rectangles) // 定义一个名为Calculate的静态方法,用于计算矩形的最大面积
48 {
49     long maxS = 0; // 最大面积的初始值为0
50     List<Rectangle> lastRectangle = new List<Rectangle>(rectangles.Select(x => new Rectangle((long)x[0], (long)x[1], (long)x[2], (long)x[3]))); // 将传入的矩形参数转换为Rectangle对象,并添加到lastRectangle列表中
51     while (lastRectangle.Count > 0) // 当lastRectangle列表不为空时,进行循环
52     {
53         Rectangle top = lastRectangle.First(); // 获取lastRectangle列表的第一个矩形对象
54         lastRectangle.Remove(top); // 从lastRectangle列表中移除该矩形对象
55         List<Rectangle> intersect = new List<Rectangle>() { top }; // 创建一个名为intersect的列表,初始值为包含top矩形对象的列表
56         var intersected = lastRectangle.Where(x => !x.IsOutside(top)); // 从lastRectangle列表中筛选出与top矩形相交的矩形对象,并存储在intersected变量中
57         foreach (Rectangle r in intersected) // 遍历intersected列表中的每个矩形对象
58         {
59             intersect.RemoveAll(x => r.IsInside(x)); // 从intersect列表中移除完全被r矩形包含的矩形对象
60             List<Rectangle> newIntersections = new List<Rectangle>();
61             foreach (Rectangle x in intersect) // 遍历intersect列表中的每个矩形对象
62                 if (!r.IsOutside(x)) // 如果r矩形与x矩形相交
63                 {
64                     newIntersections.AddRange(r.GetIntersection(x)); // 获取r矩形与x矩形的相交部分,并添加到newIntersections列表中
65                     x.ToDelete = true; // 标记x矩形需要删除
66                 }
67             intersect.RemoveAll(x => x.ToDelete); // 从intersect列表中移除需要删除的矩形对象
68             intersect.AddRange(newIntersections); // 将newIntersections列表中的矩形对象添加到intersect列表中
69             if (intersect.Count == 0) // 如果intersect列表为空,跳出循环
70                 break;
71         }
72         if (intersect.Count > 0) // 如果intersect列表不为空
73             maxS += intersect.Sum(x => x.S()); // 将intersect列表中每个矩形对象的面积相加,并累加到maxS变量中
74     }
75     return maxS; // 返回最大面积maxS
76 }

 首先,矩形的相交关系是指两个矩形是否有共同的区域。我们可以通过判断两个矩形的边界是否有重叠来确定它们是否相交。如果两个矩形的边界有重叠,则它们相交;否则,它们不相交。

其次,矩形的包含关系是指一个矩形是否完全包含另一个矩形。我们可以通过比较两个矩形的边界来确定包含关系。如果一个矩形的边界完全包含在另一个矩形的边界内部,则前者包含后者;否则,前者不包含后者。

在算法中,我们首先将传入的矩形参数转换为Rectangle对象,并存储在lastRectangle列表中。然后,通过循环处理lastRectangle列表中的矩形对象,找到与当前矩形相交的其他矩形对象,并计算它们的相交部分。

在处理每个矩形对象时,我们首先找到与当前矩形相交的矩形对象,并将它们存储在intersected变量中。然后,我们遍历intersected列表中的每个矩形对象,将完全被当前矩形包含的矩形对象从intersect列表中移除。接下来,对于与当前矩形相交的每个矩形对象,我们计算它们的相交部分,并将相交部分添加到intersect列表中。最后,我们将intersect列表中的矩形对象的面积相加,并累加到maxS变量中。

通过这种逐步计算矩形的相交部分,我们可以找到一组矩形的最大面积。这是因为我们通过不断更新intersect列表来剔除已经被其他矩形完全包含的矩形,只保留与其他矩形相交的部分。最终,我们将intersect列表中的矩形对象的面积相加,得到这组矩形的最大面积。

这个算法的数学原理基于矩形的几何性质和集合运算的概念,通过对矩形的相交和包含关系进行处理,最终得到最大面积并集。 


 算法实现2:

 1 struct Rect // 定义一个名为Rect的结构体
 2 {
 3     public int l, r, t, b; // 定义四个整型变量,分别表示矩形的左、右、上、下边界
 4     public long area => (long)(r - l) * (t - b); // 定义一个名为area的只读属性,表示矩形的面积
 5     public bool exist => l < r && b < t; // 定义一个名为exist的只读属性,表示矩形是否存在
 6 
 7     public static Rect Create(params int[] c) => // 定义一个名为Create的静态方法,用于创建一个新的Rect对象
 8         new Rect() { l = c[0], b = c[1], r = c[2], t = c[3] };
 9 
10     public bool intersects(Rect rc, out Rect result) => // 定义一个名为intersects的方法,用于判断两个矩形是否相交,并返回相交部分的矩形对象
11         (result = Create(
12             Math.Max(l, rc.l), Math.Max(b, rc.b),
13             Math.Min(r, rc.r), Math.Min(t, rc.t)))
14         .exist;
15 
16     public Rect[] octants(int n = int.MinValue, int p = int.MaxValue) => // 定义一个名为octants的方法,用于将当前矩形分成八个象限,并返回八个象限的矩形对象数组
17         new [] {
18             Create(n, n, l, b),
19             Create(n, b, l, t),
20             Create(n, t, l, p),
21             Create(l, t, r, p),
22             Create(r, t, p, p),
23             Create(r, b, p, t),
24             Create(r, n, p, b),
25             Create(l, n, r, b)
26         };
27 }
28 
29 class OctTreeNode // 定义一个名为OctTreeNode的类
30 {
31     Rect          origin; // 定义一个名为origin的Rect对象,表示当前节点所代表的矩形
32     Rect[]        oct_bounds; // 定义一个名为oct_bounds的Rect对象数组,表示当前节点所代表的矩形被分成的八个象限
33     OctTreeNode[] oct_values; // 定义一个名为oct_values的OctTreeNode对象数组,表示当前节点所代表的矩形被分成的八个象限所代表的子节点
34 
35     public OctTreeNode(Rect rc) // 定义一个构造函数,用于创建一个新的OctTreeNode对象
36     {
37         origin = rc; // 将传入的Rect对象赋值给origin变量
38         oct_bounds = rc.octants(); // 将当前矩形分成八个象限,并赋值给oct_bounds变量
39         oct_values = new OctTreeNode[8]; // 创建一个长度为8的OctTreeNode对象数组,并赋值给oct_values变量
40     }
41 
42     public void insert(Rect rc) // 定义一个名为insert的方法,用于向当前节点插入一个新的矩形对象
43     {
44         for (int i = 0; i < 8; i++) // 遍历oct_bounds数组中的每个矩形对象
45         {
46             if (oct_bounds[i].intersects(rc, out var part)) // 如果当前矩形与遍历到的矩形相交
47             {
48                 oct_values[i] ?.  insert(part); // 如果oct_values数组中第i个元素不为null,则递归调用insert方法,将part矩形插入到oct_values数组中第i个元素所代表的子节点中
49                 oct_values[i] ??= new OctTreeNode(part); // 如果oct_values数组中第i个元素为null,则创建一个新的OctTreeNode对象,并赋值给oct_values数组中第i个元素
50             }
51         }
52     }
53 
54     public long area => origin.area + // 定义一个名为area的只读属性,表示当前节点所代表的矩形的面积加上所有子节点所代表的矩形的面积之和
55         oct_values.Sum(v => v?.area ?? 0); // 遍历oct_values数组中的每个元素,如果元素不为null,则获取它所代表的矩形的面积,否则返回0
56 }
57 
58 public static class Edm // 定义一个名为Edm的静态类
59 {
60     public static long Calculate(IEnumerable<int[]> rc) // 定义一个名为Calculate的静态方法,用于计算一组矩形的最大面积
61     {
62         var en = rc.Select(Rect.Create).GetEnumerator(); // 将传入的矩形参数转换为Rect对象,并获取一个枚举器
63         if (!en.MoveNext()) return 0; // 如果枚举器没有下一个元素,则直接返回0
64 
65         var tree = new OctTreeNode(en.Current); // 创建一个新的OctTreeNode对象,并将枚举器的第一个元素作为参数传入
66         while (en.MoveNext()) tree.insert(en.Current); // 遍历枚举器中的每个元素,并将它们插入到tree中
67         return tree.area; // 返回tree所代表的矩形的面积
68     }
69 }

 这段代码实现了一个八叉树算法,用于计算一组矩形的最大面积。

八叉树算法是一种经典的数据结构和算法,其历史可以追溯到20世纪60年代。它最早被用于计算机图形学和计算机视觉领域,用于处理空间分割和区域查询等问题。

八叉树最早由法国计算机科学家Frits van der Hoeven在1966年引入,用于在计算机图形学中进行空间分割和区域查询。八叉树的名字来源于其树状结构,每个节点有八个子节点,对应于三维空间中的八个象限。

随后,八叉树在计算机视觉领域得到广泛应用,用于处理图像和空间数据。例如,八叉树可以用于图像压缩、图像搜索、碰撞检测等应用中。

随着计算机硬件和算法的发展,八叉树的变种和改进也被提出。例如,四叉树是八叉树的二维版本,用于处理二维空间数据。此外,还有基于八叉树的自适应分割方法和多分辨率表示方法等。

八叉树算法的应用领域不仅限于计算机图形学和计算机视觉,还可以用于地理信息系统、医学图像处理、物理模拟等领域。它提供了一种高效的数据结构和算法,可以用于处理多维空间数据和进行空间查询。

  1. Rect结构体表示一个矩形对象,其中包含矩形的左、右、上、下边界,以及计算矩形面积和判断矩形是否存在的属性。

  2. Rect结构体还定义了一个intersects方法,用于判断两个矩形是否相交,并返回相交部分的矩形对象。

  3. Rect结构体还定义了一个octants方法,用于将当前矩形分成八个象限,并返回八个象限的矩形对象数组。

  4. OctTreeNode类表示一个八叉树节点,每个节点代表一个矩形。该类包含一个origin变量表示当前节点所代表的矩形,以及一个oct_bounds数组表示当前节点所代表的矩形被分成的八个象限,以及一个oct_values数组表示八个象限所代表的子节点。

  5. OctTreeNode类定义了一个insert方法,用于向当前节点插入一个新的矩形对象。该方法通过遍历八个象限的矩形对象,判断当前矩形与遍历到的矩形是否相交,如果相交则递归调用insert方法将相交部分的矩形插入到对应的子节点中。

  6. OctTreeNode类还定义了一个area属性,表示当前节点所代表的矩形的面积加上所有子节点所代表的矩形的面积之和。

  7. Edm静态类定义了一个Calculate方法,用于计算一组矩形的最大面积。该方法首先将传入的矩形参数转换为Rect对象,并创建一个八叉树节点。然后,遍历矩形对象并将它们插入到八叉树中。最后,返回八叉树所代表的矩形的面积作为结果。

这个算法的数学原理基于矩形的几何性质和八叉树的概念,通过构建八叉树来处理矩形的相交和包含关系,最终得到一组矩形的最大面积并集。 


算法2中有些简写的cSharp语法,解释如下:

 1 //1.这段代码使用了C#语言的Lambda表达式和对象初始化器。Lambda表达式用于定义一个匿名方法,而对象初始化器用于在创建对象的同时对其属性进行初始化。
 2 public static Rect Create(params int[] c) =>
 3             new Rect() { l = c[0], b = c[1], r = c[2], t = c[3] };
 4 
 5 //这段代码定义了一个名为Create的静态方法,其目的是创建一个矩形对象。该方法接受一个可变长度的整数数组作为参数,数组中的元素按照特定的顺序表示矩形的左边界、底边界、右边界和顶边界。
 6 //以下是另一种常用写法:
 7 public static Rect Create(params int[] c)
 8 {
 9     int left = c[0];
10     int bottom = c[1];
11     int right = c[2];
12     int top = c[3];
13 
14     Rect rect = new Rect();
15     rect.l = left;
16     rect.b = bottom;
17     rect.r = right;
18     rect.t = top;
19 
20     return rect;
21 }
22 
23 //2.同一
24  public bool intersects(Rect rc, out Rect result) =>
25             (result = Create(
26                 Math.Max(l, rc.l), Math.Max(b, rc.b),
27                 Math.Min(r, rc.r), Math.Min(t, rc.t)))
28             .exist;
29 
30 //常用写法:
31 public bool Intersects(Rect rc, out Rect result)
32 {
33     int left = Math.Max(l, rc.l);
34     int bottom = Math.Max(b, rc.b);
35     int right = Math.Min(r, rc.r);
36     int top = Math.Min(t, rc.t);
37 
38     result = Create(left, bottom, right, top);
39 
40     return result.exist;
41 }
42 /*
43 在这个写法中,首先根据两个矩形的左边界、底边界、右边界和顶边界的最大值和最小值,分别计算出相交部分的矩形的左边界、底边界、右边界和顶边界。
44 
45 然后,使用这些计算结果调用Create方法创建一个新的矩形对象,并将其赋值给result参数。
46 
47 最后,返回新创建的矩形对象的exist属性,表示两个矩形是否相交。
48 
49 这个写法与原始代码的功能相同,但使用了更加明确的变量名和更加传统的语法,使其更容易理解。*/

 算法2和算法1都是用于计算矩形的面积交集的实现,但它们使用了不同的数据结构和算法。

算法1使用了一个二维数组来表示每个点的覆盖情况,并使用扫描线算法来计算矩形的面积交集。这个算法的优点是实现简单,但需要额外的空间来存储覆盖情况,并且在处理大量矩形时可能会变得非常慢。

相比之下,算法2使用了八叉树的数据结构来表示矩形,并使用递归的方式来插入和查询矩形。这个算法的优点是可以高效地处理大量矩形,并且可以快速地计算矩形的面积交集。但缺点是实现相对复杂,需要额外的空间来存储八叉树节点,而且在处理高维数据时可能不太适用。

总的来说,这两个算法都有各自的优缺点,可以根据具体情况选择适合的算法。如果处理的数据量不是很大,或者需要实现的算法比较简单,那么可以选择算法1;如果处理的数据量比较大,或者需要高效地计算矩形的面积交集,那么可以选择算法2。


测试用例:

  1 namespace Solution {
  2   using NUnit.Framework;
  3   using System;
  4   using System.Collections.Generic;
  5   using System.Linq;
  6   using static NUnit.Framework.Assert;
  7     
  8 
  9   public class RandSort
 10   {
 11       public static IEnumerable<int[]> Shuffle(List<int[]> recs)
 12       {
 13         var rnd = new Random();
 14         var order = new List<double>();
 15         for (int i = 0; i < recs.Count; i++) {
 16             order.Add(rnd.NextDouble());
 17         }
 18         var orderArray = order.ToArray();
 19         var recsArray = recs.ToArray();
 20         Array.Sort(orderArray, recsArray);
 21         return recsArray;
 22       }
 23   }
 24 
 25   [TestFixture]
 26   public class BasicTests
 27   {
 28     [Test]
 29     public void ZeroRectangles()
 30     {
 31       AreEqual(0, Edm.Calculate(Enumerable.Empty<int[]>()));
 32     }
 33 
 34     [Test]
 35     public void OneRectangle()
 36     {
 37       AreEqual(1, Edm.Calculate(new [] { new [] {0,0,1,1}}));
 38     }
 39  
 40     [Test]
 41     public void OneRectangleV2()
 42     {
 43       AreEqual(22, Edm.Calculate(new [] { new [] {0, 4, 11, 6}}));
 44     }
 45   
 46     [Test]
 47     public void TwoRectangles()
 48     {
 49       AreEqual(2, Edm.Calculate(new [] { new [] {0,0,1,1}, new [] {1,1,2,2}}));
 50     }
 51 
 52     [Test]
 53     public void TwoRectanglesV2()
 54     {
 55       AreEqual(4, Edm.Calculate(new [] { new [] {0,0,1,1}, new [] {0,0,2,2}}));
 56     }
 57 
 58     [Test]
 59     public void ThreeRectangles()
 60     {
 61       AreEqual(36, Edm.Calculate(new [] { new [] {3,3,8,5}, new [] {6,3,8,9}, new [] {11,6,14,12}}));
 62     }
 63   }
 64   
 65   [TestFixture]
 66   public class ExpandedTests
 67   {
 68     [Test]
 69     public void RectanglesWithoutIntersections()
 70     {
 71       var recs = new [] {
 72         new [] { 1, 1, 2, 2 },
 73         new [] { 2, 2, 3, 3 },
 74         new [] { 3, 3, 4, 4 },
 75         new [] { 4, 4, 5, 5 },
 76         new [] { 2, 1, 3, 2 }
 77       }; 
 78     
 79       AreEqual(5, Edm.Calculate(recs));
 80     }
 81     
 82     
 83     [Test]
 84     public void RectanglesWithSimpleIntersections()
 85     {
 86       var recs = new [] {
 87         new [] { 1, 1, 2, 2 },
 88         new [] { 1, 4, 2, 7 },
 89         new [] { 1, 4, 2, 6 },
 90         new [] { 1, 4, 4, 5 },
 91         new [] { 2, 5, 6, 7 },
 92         new [] { 4, 3, 7, 6 },
 93       }; 
 94     
 95       AreEqual(21, Edm.Calculate(recs));
 96     }
 97 
 98     [Test]
 99     public void RectanglesWithSimpleIntersectionsV2()
100     {
101       var recs = new [] {
102         new [] { 1, 3, 4, 5 },
103         new [] { 2, 1, 4, 7 },
104         new [] { 3, 4, 5, 6 },
105         new [] { 6, 6, 8, 7 },
106         new [] { 5, 3, 8, 4 },
107         new [] { 6, 0, 7, 3 },
108       };
109     
110       AreEqual(24, Edm.Calculate(recs));
111     }
112     
113     [Test]
114     public void DifficultCommonFaces()
115     {
116       var rnd = new Random();
117       int stepX = rnd.Next(10,20);
118       int stepY = rnd.Next(10,20);
119       int startX = rnd.Next(0, 1000);
120       int startY = rnd.Next(0, 1000);
121       int count = rnd.Next(1000, 1500);
122       
123       var recs = new List<int[]>();
124     
125       for (var i = 0; i < count; i++)
126       {
127         var x = startX + i * stepX;
128         var y = startY + i * stepY;
129         recs.Add(new [] { x,     y,     x + 1, y + 1 });
130         recs.Add(new [] { x + 1, y,     x + 3, y + 2 });
131         recs.Add(new [] { x,     y + 2, x + 3, y + 3 });
132         recs.Add(new [] { x + 3, y,     x + 4, y + 3 });
133         recs.Add(new [] { x + 2, y + 3, x + 4, y + 5 });
134       }
135       
136       var recsArray = RandSort.Shuffle(recs);
137       AreEqual(15 * count, Edm.Calculate(recsArray));
138     }
139     
140     
141     [Test]
142     public void DifficultLocatedFarAway()
143     {
144       var rnd = new Random();
145       int stepX = rnd.Next(1000,2000);
146       int stepY = rnd.Next(1000,2000);
147       int startX = rnd.Next(0, 1000);
148       int startY = rnd.Next(0, 1000);
149       int count = rnd.Next(1000, 1500);
150       
151       var recs = new List<int[]>();
152     
153       for (var i = 0; i < count; i++)
154       {
155         var x = startX + i * stepX;
156         var y = startY + i * stepY;
157         recs.Add(new [] { x,       y,       x + 202, y + 300 });
158         recs.Add(new [] { x + 100, y + 500, x + 500, y + 765 });
159         recs.Add(new [] { x + 150, y + 330, x + 170, y + 360 });
160       }
161         
162       var recsArray = RandSort.Shuffle(recs);
163       AreEqual(167200 * count, Edm.Calculate(recsArray));
164     }       
165     
166     
167     [Test]
168     public void DifficultNestedRectangles()
169     {
170       var rnd = new Random();
171       int stepX = rnd.Next(10,200);
172       int stepY = rnd.Next(10,200);
173       int startX = rnd.Next(0, 1000);
174       int startY = rnd.Next(0, 1000);
175       int count = rnd.Next(1000, 1500);
176       
177       var recs = new List<int[]>();
178     
179       for (var i = 0; i < count; i++)
180       {
181         var x = startX + i * stepX;
182         var y = startY + i * stepY;
183         
184         recs.Add(new [] { x,     y,     x + 1, y + 1 });
185         recs.Add(new [] { x,     y,     x + 1, y + 3 });
186         recs.Add(new [] { x,     y + 1, x + 3, y + 2 });
187         recs.Add(new [] { x,     y + 3, x + 4, y + 4 });
188         recs.Add(new [] { x + 2, y,     x + 6, y + 2 });
189         recs.Add(new [] { x + 3, y + 3, x + 6, y + 5 });
190       }
191       
192       var recsArray = RandSort.Shuffle(recs);
193       AreEqual(21 * count, Edm.Calculate(recsArray));
194     }       
195 
196 
197     [Test]
198     public void DifficultRectanglesWithLotsOfIntersections()
199     {
200       var rnd = new Random();
201       int stepX = rnd.Next(10,200);
202       int stepY = rnd.Next(10,200);
203       int startX = rnd.Next(0, 1000);
204       int startY = rnd.Next(0, 1000);
205       int count = rnd.Next(1000, 1500);
206       
207       var recs = new List<int[]>();
208     
209       for (var i = 0; i < count; i++)
210       {
211         var x = startX + i * stepX;
212         var y = startY + i * stepY;
213         
214         recs.Add(new [] { x,     y + 2, x + 2, y + 4 });
215         recs.Add(new [] { x + 1, y + 3, x + 3, y + 5 });
216         recs.Add(new [] { x + 1, y + 1, x + 3, y + 3 });
217         recs.Add(new [] { x + 7, y + 3, x + 8, y + 4 });
218         recs.Add(new [] { x + 8, y + 2, x + 9, y + 7 });
219         recs.Add(new [] { x + 6, y + 2, x + 9, y + 7 });
220         recs.Add(new [] { x + 3, y + 5, x + 10,y + 6 });
221         recs.Add(new [] { x + 3, y + 2, x + 6, y + 3 });
222         recs.Add(new [] { x + 2, y + 4, x + 4, y + 7 });
223         recs.Add(new [] { x + 9, y,     x + 10,y + 3 });
224       }
225       
226       var recsArray = RandSort.Shuffle(recs);
227       AreEqual(39 * count, Edm.Calculate(recsArray));
228     }       
229 
230 
231     [Test]
232     public void DifficultRectanglesWithLongSides()
233     {
234       var rnd = new Random();
235       int stepX = rnd.Next(100000,111000);
236       int stepY = rnd.Next(100000,111000);
237       int startX = rnd.Next(0, 1000);
238       int startY = rnd.Next(0, 1000);
239       int count = rnd.Next(1000, 1500);
240       
241       var recs = new List<int[]>();
242     
243       for (var i = 0; i < count; i++)
244       {
245         var x = startX + i * stepX;
246         var y = startY + i * stepY;
247 
248         recs.Add(new [] { x,         y,     x + 30000, y + 1 });
249         recs.Add(new [] { x,         y + 1, x + 1,     y + 30001 });
250         recs.Add(new [] { x + 30000, y + 1, x + 30001, y + 30001 });
251       }
252       
253       var recsArray = RandSort.Shuffle(recs);
254       AreEqual(90000 * count, Edm.Calculate(recsArray));
255     }       
256 
257 
258     [Test]
259     public void DifficultRectanglesWithCommonFacesV2()
260     {
261       var rnd = new Random();
262       int stepX = 0; //rnd.Next(100000,111000);
263       int stepY = rnd.Next(10,200);
264       int startX = rnd.Next(0, 1000);
265       int startY = rnd.Next(0, 1000);
266       int count = rnd.Next(1000, 1500);
267       
268       var recs = new List<int[]>();
269     
270       for (var i = 0; i < count; i++)
271       {
272         var x = startX + i * stepX;
273         var y = startY + i * stepY;
274 
275         recs.Add(new [] { x,     y,     x + 1, y + 1 });
276         recs.Add(new [] { x + 1, y,     x + 3, y + 2 });
277         recs.Add(new [] { x,     y + 2, x + 3, y + 3 });
278         recs.Add(new [] { x + 3, y,     x + 4, y + 3 });
279         recs.Add(new [] { x + 2, y + 3, x + 4, y + 5 });
280      }
281       
282       var recsArray = RandSort.Shuffle(recs);
283       AreEqual(15 * count, Edm.Calculate(recsArray));
284     }       
285 
286 
287     [Test]
288     public void DifficultRectanglesLocatedFarAwayV2()
289     {
290       var rnd = new Random();
291       int stepX = 0; //rnd.Next(100000,111000);
292       int stepY = rnd.Next(1000,2000);
293       int startX = rnd.Next(0, 1100);
294       int startY = rnd.Next(0, 1100);
295       int count = rnd.Next(1000, 1500);
296       
297       var recs = new List<int[]>();
298     
299       for (var i = 0; i < count; i++)
300       {
301         var x = startX + i * stepX;
302         var y = startY + i * stepY;
303 
304         recs.Add(new [] { x,       y,       x + 202, y + 300 });
305         recs.Add(new [] { x + 100, y + 500, x + 500, y + 765 });
306         recs.Add(new [] { x + 150, y + 330, x + 170, y + 360 });        
307      }
308         
309       var recsArray = RandSort.Shuffle(recs);
310       AreEqual(167200 * count, Edm.Calculate(recsArray));
311     }  
312 
313 
314     [Test]
315     public void DifficultNestedRectanglesV2()
316     {
317       var rnd = new Random();
318       int stepX = 0; //rnd.Next(100000,111000);
319       int stepY = rnd.Next(10,200);
320       int startX = rnd.Next(0, 1100);
321       int startY = rnd.Next(0, 1100);
322       int count = rnd.Next(1000, 1500);
323       
324       var recs = new List<int[]>();
325     
326       for (var i = 0; i < count; i++)
327       {
328         var x = startX + i * stepX;
329         var y = startY + i * stepY;
330 
331         recs.Add(new [] { x,     y,     x + 1, y + 1 });
332         recs.Add(new [] { x,     y,     x + 1, y + 3 });
333         recs.Add(new [] { x,     y + 1, x + 3, y + 2 });
334         recs.Add(new [] { x,     y + 3, x + 4, y + 4 });
335         recs.Add(new [] { x + 2, y,     x + 6, y + 2 });
336         recs.Add(new [] { x + 3, y + 3, x + 6, y + 5 });       
337       }
338       
339       var recsArray = RandSort.Shuffle(recs);
340       AreEqual(21 * count, Edm.Calculate(recsArray));
341     }  
342 
343     [Test]
344     public void DifficultRectanglesWithLotsOfIntersectionsV2()
345     {
346       var rnd = new Random();
347       int stepX = 0; //rnd.Next(100000,111000);
348       int stepY = rnd.Next(10,200);
349       int startX = rnd.Next(0, 1100);
350       int startY = rnd.Next(0, 1100);
351       int count = rnd.Next(1000, 1500);
352       
353       var recs = new List<int[]>();
354     
355       for (var i = 0; i < count; i++)
356       {
357         var x = startX + i * stepX;
358         var y = startY + i * stepY;
359 
360         recs.Add(new [] { x,     y + 2, x + 2, y + 4 });
361         recs.Add(new [] { x + 1, y + 3, x + 3, y + 5 });
362         recs.Add(new [] { x + 1, y + 1, x + 3, y + 3 });
363         recs.Add(new [] { x + 7, y + 3, x + 8, y + 4 });
364         recs.Add(new [] { x + 8, y + 2, x + 9, y + 7 });
365         recs.Add(new [] { x + 6, y + 2, x + 9, y + 7 });
366         recs.Add(new [] { x + 3, y + 5, x + 10,y + 6 });
367         recs.Add(new [] { x + 3, y + 2, x + 6, y + 3 });
368         recs.Add(new [] { x + 2, y + 4, x + 4, y + 7 });
369         recs.Add(new [] { x + 9, y,     x + 10,y + 3 });        
370       }
371       
372       var recsArray = RandSort.Shuffle(recs);
373       AreEqual(39 * count, Edm.Calculate(recsArray));
374     }  
375     
376     
377     [Test]
378     public void DifficultRectanglesWithLongSidesV2()
379     {
380       var rnd = new Random();
381       int stepX = 0; //rnd.Next(100000,111000);
382       int stepY = rnd.Next(100000,111200);
383       int startX = rnd.Next(0, 1100);
384       int startY = rnd.Next(0, 1100);
385       int count = rnd.Next(1000, 1500);
386       
387       var recs = new List<int[]>();
388     
389       for (var i = 0; i < count; i++)
390       {
391         var x = startX + i * stepX;
392         var y = startY + i * stepY;
393 
394         recs.Add(new [] { x,         y,     x + 30000, y + 1 });
395         recs.Add(new [] { x,         y + 1, x + 1,     y + 30001 });
396         recs.Add(new [] { x + 30000, y + 1, x + 30001, y + 30001 });
397       }
398       
399       var recsArray = RandSort.Shuffle(recs);
400       AreEqual(90000 * count, Edm.Calculate(recsArray));
401     }      
402 
403     private static long Solve(IEnumerable<int[]> rectangles)
404     {
405       if (!rectangles.Any()) return 0;
406       rectangles = rectangles.OrderBy(r => r[0]).ToList();
407       var xs = rectangles.Select(r=>r[0]).Concat(rectangles.Select(r=>r[2])).Distinct().OrderBy(x=>x).ToList();
408       var scan = new List<int[]>();    
409       // long recIndex = 0;
410       long area = 0;
411       long scanLeft = xs[0];
412       xs.RemoveAt(0);
413       using(var recsEnum = rectangles.GetEnumerator())
414       {
415         bool hasMoreRec = recsEnum.MoveNext();
416         
417         xs.ForEach(scanRight =>
418         {
419           // add rectangles to scan that align on scan left...
420           for(;hasMoreRec && recsEnum.Current[0] == scanLeft; hasMoreRec = recsEnum.MoveNext())
421           {
422             scan.Add(recsEnum.Current);
423           }
424           
425           scan.Sort((a,b) => a[1] - b[1]); // order by top
426           long height = 0;
427           long lastY = long.MinValue; // last y accounted for in height
428           scan.ForEach(s =>
429           {
430             long top = s[1];
431             long bottom = s[3];
432             if (lastY < bottom) // overlaps, add height of overlapping portion
433             {
434               height += bottom - Math.Max(lastY, top);
435               lastY = bottom;
436             }
437           });
438           
439           // area of rectangles that overlap scan: height * width
440           area += height * (scanRight - scanLeft);
441             
442           // proceding left-to-right, so remove the scan rectangles whose right-side is to the left of current scan
443           scan.RemoveAll(r=>r[2] <= scanRight);
444           scanLeft = scanRight;
445         });
446       }
447       
448       return area;
449     }
450 
451     [Test]
452     public void DifficultRandomTests()
453     {
454       const int scale = 100000;
455       var rnd = new Random();
456       for(int i=0; i<25; i++) 
457       {
458         int sx=rnd.Next(0,scale);
459         int sy=rnd.Next(0,scale);
460         var recs = Enumerable.Range(0,rnd.Next(300,500)).Select(_ => new [] { sx, sy, sx + rnd.Next(0,scale), sy + rnd.Next(0, scale) }).ToArray();
461         var expected = Solve(recs);
462         var actual = Edm.Calculate(recs);
463         AreEqual(expected, actual);
464       }
465     }
466   }    
467 }

 

评论