[Algorithm] Shadow area under November sunshine-1024programmer

[Algorithm] Shadow area under November sunshine

The November sunshine shines through the window on the desk of a woman with a sweet and youthful smile. Xiaoyue, a software engineer who always appears in a high ponytail, shows her competence and vitality. The long, shiny black hair fluttered lightly, as if telling her unique charm. Her eyebrows are picturesque, and her bright eyes sparkle with a thirst for knowledge and a passion for technical challenges.

On this day, she received an email from the hospital. The technical update issue of the scanning equipment mentioned in the email made her feel a little challenged. However, Xiaoyue is always full of curiosity and enthusiasm for technical challenges. She decided to contact the hospital to express her willingness to participate in the project. Fortunately, the hospital responded quickly to her email and arranged a conference call.

During the conference call, Xiaoyue communicated with hospital managers and experts in related fields. Their voices are filled with a desire for new technologies and new thinking. Xiaoyue also realized that this opportunity could be a major breakthrough for his career development.

Soon after, Xiaoyue successfully joined the hospital team. In the team, she found many excellent experts and engineers. One senior doctor has a deep understanding of the needs of scanning equipment, while another engineer has in-depth research on image processing algorithms. Xiaoyue knows that she plays a key role in this team and must give full play to her strengths.

In team cooperation, Xiaoyue has established a good cooperative relationship with everyone. She constantly communicates and communicates with team members to understand their needs and ideas. Her voice is always gentle and confident, making people feel reassured and trustworthy. At the same time, she also shared her experience and professional knowledge with team members and made a huge contribution to the progress of the project.

However, as the project progressed, Xiaoyue gradually discovered some technical problems. The biggest problem is how to calculate the area union of the shaded parts. In order to solve this problem, she constantly reviewed the literature, studied algorithms, and tried various methods. Sometimes she would get so deep into trouble that she couldn’t sleep all night. However, she never gave up exploring and solving this problem.

After a period of hard work, Xiaoyue finally came up with an effective method to calculate the area union of the shaded parts. This method was not only recognized and supported by the team, but also successfully solved a major problem in the project. Xiaoyue’s contribution surprised and admired the entire team.

In the following time, Xiaoyue and the team continued to work hard and finally successfully developed a new scanning device program design. This program uses the shadow area calculation method proposed by Xiaoyue, which effectively improves the accuracy and efficiency of scanning. The hospital was so pleased with the procedure that they decided to put it into use.

In this process, Xiaoyue learned a lot. Not only did she achieve breakthroughs and growth in technology, she also learned how to collaborate and communicate with people from different backgrounds. She deeply understands the importance of interpersonal relationships and how to use them to expand her horizons and abilities. At the same time, she also experienced the joy and sense of accomplishment of helping others.

The problem Xiaoyue faces is medical image reconstruction: Medical images (such as CT, MRI, etc.) are usually composed of multiple slice images, and these images may have overlapping or intersecting areas. The rectangular area union algorithm can be used to calculate the overlapping areas between these images, allowing for accurate image reconstruction and fusion.

She needs to develop a method called Calculate that accepts a two-dimensional array as a parameter, where each subarray represents the coordinates of a rectangle. In this example, the coordinates of the three rectangles are [1,2,5,6], [1,3,4,5] and [3,1,5,4]. and returns the desired area union.

Each rectangle is represented as: [x0, y0, x1, y1]
(x0, y0) – the coordinates of the lower left corner of the rectangle
(x1, y1) – the coordinates of the upper right corner of the rectangle

Legend (area=18):

Algorithm implementation 1:

 1 private class Rectangle // Define a private class named Rectangle
  2 {
  3 public  span> long x0; // Left border of the rectangle
  4 public long y0; // Bottom boundary of the rectangle
  5 public long x1; // Right border of the rectangle
  6 public long y1; // Top border of the rectangle
  7 public bool ToDelete = false; // Mark whether the rectangle needs to be deleted
  8
  9 public Rectangle(  long x0, long  y0, long x1, long  span> y1) // Constructor  , used to initialize the boundary value of the rectangular object
 10  {
 11 this  span>.x0 = x0;
 12 this  span>.x1 = x1;
 13 this  span>.y0 = y0;
 14 this  span>.y1 = y1;
 15  }
 16
 17 public long S() //   Calculate the area of the rectangle
 18  {
 19 return  span> (x1 - x0) * (y1 - y0);
 20  }
 21
 22 public bool IsInside(Rectangle r) // Determine whether the current rectangle completely contains another rectangle r
 23  {
 24 return  span> ((r.x0 >= x0) && (r.x1 = y0) && (r.y1 <= y1)) ? true : false;
 25  }
 26
 27 public bool IsOutside(Rectangle r) // Determines whether the current rectangle is completely outside another rectangle r
 28  {
 29 return  span> ((r.x0 >= x1) || (r.x1 = y1) || (r.y1 <= y0)) ? true : false;
 30  }
 31
 32 public List GetIntersection(Rectangle r) // Get the intersection of the current rectangle and another rectangle r
 33  {
 34 List rests = new List();
 35 if  span> (r.x0 < x0)
 36 rests.Add(new Rectangle(r.x0, r.y0, x0, r.y1));
 37 if  span> (r.x1 > x1)
 38 rests.Add(new Rectangle(x1, r.y0, r.x1, r.y1));
 39 if  span> (r.y0 < y0)
 40 rests.Add(new Rectangle(Math.Max(r.x0, x0), r.y0, Math.Min(r.x1,  x1), y0));
 41 if  span> (r.y1 > y1)
 42 rests.Add(new Rectangle(Math.Max(r.x0, x0), y1, Math.Min(r.x1, x1)  , r.y1));
 43 return  span> rests;
 44  }
 45 }
 46
 47 public static long Calculate(IEnumerable<  int[]> rectangles) //   Define a static method named Calculate to calculate the maximum area of a rectangle
 48 {
 49 long  span> maxS = 0; //   The initial value of the maximum area is 0
 50 List lastRectangle = new   List(rectangles.Select(x => new Rectangle((long)x[0], (long)x[1],  (long)x[2], (long)x[3]))); // Convert the incoming rectangle parameter into a Rectangle object and add it to the lastRectangle list
 51 while (lastRectangle  .Count > 0) // When the lastRectangle list is not empty, loop
 52  {
 53 Rectangle top = lastRectangle.First(); var recsEnum = rectangles.GetEnumerator())
 414  {
 415 bool  span> 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  span> lastY = long.MinValue;   // last y accounted for in height
 428 scan.ForEach(s =>
 429  {
 430 long  span> top = s[1]  ;
 431 long  span> bottom = s[3]  ;
 432 if  span> (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  span> void DifficultRandomTests()
 453  {
 454 const  span> int scale = 100000;
 455 var  span> rnd = new Random()  ;
 456 for  span>(int i=0; i<25; i++)
 457  {
 458 int  span> sx=rnd.Next(0,scale);
 459 int  span> sy=rnd.Next(0,scale);
 460 var  span> 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  span> expected = Solve(recs);
 462 var  span> actual = Edm.Calculate(recs);
 463  AreEqual(expected  , actual);
 464  }
 465  }
 466  }
 467 }

scanLeft = scanRight;
445 });
446 }
447
448 return area;
449 }
450
451 [Test]
452 public span> void DifficultRandomTests()
453 {
454 const span> int scale = 100000;
455 var span> rnd = new Random() ;
456 for span>(int i=0; i<25; i++)
457 {
458 int span> sx=rnd.Next(0,scale);
459 int span> sy=rnd.Next(0,scale);
460 var span> 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 span> expected = Solve(recs);
462 var span> actual = Edm.Calculate(recs);
463 AreEqual(expected , actual);
464 }
465 }
466 }
467 }