Круг разрезан несамопересекающейся ломаной, координаты вершин которой заданы парами натуральных чисел - C#

Узнай цену своей работы

Формулировка задачи:

Круг разрезан несамопересекающейся ломаной, координаты вершин которой заданы парами натуральных чисел (x1,y1), ..., (xk,yk). Первая и последняя вершины лежат на границе круга, а остальные внутри его. Определить, можно ли разъединить две получившиеся части круга (выход из плоскости и повороты разнимаемых частей не допускается).

Решение задачи: «Круг разрезан несамопересекающейся ломаной, координаты вершин которой заданы парами натуральных чисел»

textual
Листинг программы
  1. struct Point
  2. {
  3.     public double X;
  4.     public double Y;
  5.    
  6.     public Point(double x, double y)
  7.     {
  8.         X = x;
  9.         Y = y;
  10.     }
  11.    
  12.     public Point(Point from, Point to)
  13.     {
  14.         X = to.X - from.X;
  15.         Y = to.Y - from.Y;
  16.     }
  17.    
  18.     // [0; 2pi]
  19.     public double GetAngle()
  20.     {
  21.         var angle = Math.Atan2(Y, X);
  22.         if (angle < 0)
  23.         {
  24.             return Math.PI * 2 + angle;
  25.         }
  26.         return angle;
  27.     }
  28.    
  29.     public override string ToString()
  30.     {
  31.         return $"({X}, {Y})";
  32.     }
  33. }
  34.  
  35. static class AngleHelper
  36. {
  37.     private static Point[] ToSegments(double fromAngle, double toAngle)
  38.     {
  39.         if (fromAngle > toAngle)
  40.         {
  41.             return new[] { new Point(fromAngle, Math.PI * 2), new Point(0, toAngle) };
  42.         }
  43.         return new[] { new Point(fromAngle, toAngle) };
  44.     }
  45.    
  46.     private static Point? IntersectSegments(Point first, Point second)
  47.     {
  48.         double from = Math.Max(first.X, second.X);
  49.         double to = Math.Min(first.Y, second.Y);
  50.         return to < from - 1e-8 ? (Point?)null : new Point(Math.Min(from, to), Math.Max(from, to));
  51.     }
  52.    
  53.     private static Point GetAngle(Point first, Point center, Point last)
  54.     {
  55.         var firstOffset = new Point(center, first);
  56.         var lastOffset = new Point(center, last);
  57.         var fromAngle = firstOffset.GetAngle();
  58.         var toAngle = lastOffset.GetAngle();
  59.         return new Point(fromAngle, toAngle);
  60.     }
  61.    
  62.     private static Point GetStraightAngle(Point center, Point last)
  63.     {
  64.         var offset = new Point(center, last);
  65.         var toAngle = offset.GetAngle();
  66.         return new Point((toAngle + Math.PI) % (Math.PI * 2), toAngle);
  67.     }
  68.  
  69.     public static IList<Point> IntersectAngles(Point firstAngle, Point secondAngle)
  70.     {
  71.         Point[] firstSegments = ToSegments(firstAngle.X, firstAngle.Y);
  72.         Point[] secondSegments = ToSegments(secondAngle.X, secondAngle.Y);
  73.         var resultAngles = new List<Point>();
  74.         foreach (var firstSegment in firstSegments)
  75.         {
  76.             foreach (var secondSegment in secondSegments)
  77.             {
  78.                 Point? intersected = IntersectSegments(firstSegment, secondSegment);
  79.                 if (intersected != null)
  80.                 {
  81.                     resultAngles.Add((Point)intersected);
  82.                 }
  83.             }
  84.         }
  85.         return resultAngles;
  86.     }
  87.    
  88.     public static IEnumerable<Point> GetAngles(IList<Point> polygonalLine)
  89.     {
  90.         yield return GetStraightAngle(polygonalLine[0], polygonalLine[1]);
  91.         for (int i = 1; i < polygonalLine.Count - 1; i++)
  92.         {
  93.             yield return GetAngle(polygonalLine[i - 1], polygonalLine[i], polygonalLine[i + 1]);
  94.         }
  95.         var last = GetStraightAngle(polygonalLine[polygonalLine.Count - 1], polygonalLine[polygonalLine.Count - 2]);
  96.         yield return new Point(last.Y, last.X);
  97.     }
  98.    
  99.     public static double GetTotalAngleValue(Point angle)
  100.     {
  101.         double value = angle.Y - angle.X;
  102.         if (value < 0)
  103.         {
  104.             value += Math.PI * 2;
  105.         }
  106.         return value;
  107.     }
  108. }
  109.  
  110. static class SeveringResolver
  111. {
  112.     public static IList<Point> GetDirectionsToSever(IList<Point> polygonalLine)
  113.     {
  114.         var intersection = new List<Point>();
  115.         intersection.Add(new Point(0, Math.PI * 2));
  116.         foreach (Point angle in AngleHelper.GetAngles(polygonalLine).OrderBy(AngleHelper.GetTotalAngleValue))
  117.         {
  118.             var newIntersection = new List<Point>();
  119.             foreach (Point oldAngle in intersection)
  120.             {
  121.                 newIntersection.AddRange(AngleHelper.IntersectAngles(oldAngle, angle));
  122.             }
  123.             intersection = newIntersection;
  124.         }
  125.         return intersection;
  126.     }
  127. }
  128.  
  129. void Main()
  130. {
  131.     Point[] polygonalLine = {
  132.         new Point(0, 0),
  133.         new Point(0, 2),
  134.         new Point(1, 1),
  135.         new Point(1, 3),
  136.         new Point(0, 4)
  137.     };
  138.     var severingAngles = SeveringResolver.GetDirectionsToSever(polygonalLine);
  139.     foreach (var angle in severingAngles)
  140.     {
  141.         var fromDegree = angle.X * 360 / 2 / Math.PI;
  142.         var toDegree = angle.Y * 360 / 2 / Math.PI;
  143.         new Point(fromDegree, toDegree).Dump();
  144.     }
  145. }

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

13   голосов , оценка 3.846 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы