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

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

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

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

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

textual
Листинг программы
struct Point
{
    public double X;
    public double Y;
    
    public Point(double x, double y)
    {
        X = x;
        Y = y;
    }
    
    public Point(Point from, Point to)
    {
        X = to.X - from.X;
        Y = to.Y - from.Y;
    }
    
    // [0; 2pi]
    public double GetAngle()
    {
        var angle = Math.Atan2(Y, X);
        if (angle < 0)
        {
            return Math.PI * 2 + angle;
        }
        return angle;
    }
    
    public override string ToString()
    {
        return $"({X}, {Y})";
    }
}
 
static class AngleHelper
{
    private static Point[] ToSegments(double fromAngle, double toAngle)
    {
        if (fromAngle > toAngle)
        {
            return new[] { new Point(fromAngle, Math.PI * 2), new Point(0, toAngle) };
        }
        return new[] { new Point(fromAngle, toAngle) };
    }
    
    private static Point? IntersectSegments(Point first, Point second)
    {
        double from = Math.Max(first.X, second.X);
        double to = Math.Min(first.Y, second.Y);
        return to < from - 1e-8 ? (Point?)null : new Point(Math.Min(from, to), Math.Max(from, to));
    }
    
    private static Point GetAngle(Point first, Point center, Point last)
    {
        var firstOffset = new Point(center, first);
        var lastOffset = new Point(center, last);
        var fromAngle = firstOffset.GetAngle();
        var toAngle = lastOffset.GetAngle();
        return new Point(fromAngle, toAngle);
    }
    
    private static Point GetStraightAngle(Point center, Point last)
    {
        var offset = new Point(center, last);
        var toAngle = offset.GetAngle();
        return new Point((toAngle + Math.PI) % (Math.PI * 2), toAngle);
    }
 
    public static IList<Point> IntersectAngles(Point firstAngle, Point secondAngle)
    {
        Point[] firstSegments = ToSegments(firstAngle.X, firstAngle.Y);
        Point[] secondSegments = ToSegments(secondAngle.X, secondAngle.Y);
        var resultAngles = new List<Point>();
        foreach (var firstSegment in firstSegments)
        {
            foreach (var secondSegment in secondSegments)
            {
                Point? intersected = IntersectSegments(firstSegment, secondSegment);
                if (intersected != null)
                {
                    resultAngles.Add((Point)intersected);
                }
            }
        }
        return resultAngles;
    }
    
    public static IEnumerable<Point> GetAngles(IList<Point> polygonalLine)
    {
        yield return GetStraightAngle(polygonalLine[0], polygonalLine[1]);
        for (int i = 1; i < polygonalLine.Count - 1; i++)
        {
            yield return GetAngle(polygonalLine[i - 1], polygonalLine[i], polygonalLine[i + 1]);
        }
        var last = GetStraightAngle(polygonalLine[polygonalLine.Count - 1], polygonalLine[polygonalLine.Count - 2]);
        yield return new Point(last.Y, last.X);
    }
    
    public static double GetTotalAngleValue(Point angle)
    {
        double value = angle.Y - angle.X;
        if (value < 0)
        {
            value += Math.PI * 2;
        }
        return value;
    }
}
 
static class SeveringResolver
{
    public static IList<Point> GetDirectionsToSever(IList<Point> polygonalLine)
    {
        var intersection = new List<Point>();
        intersection.Add(new Point(0, Math.PI * 2));
        foreach (Point angle in AngleHelper.GetAngles(polygonalLine).OrderBy(AngleHelper.GetTotalAngleValue))
        {
            var newIntersection = new List<Point>();
            foreach (Point oldAngle in intersection)
            {
                newIntersection.AddRange(AngleHelper.IntersectAngles(oldAngle, angle));
            }
            intersection = newIntersection;
        }
        return intersection;
    }
}
 
void Main()
{
    Point[] polygonalLine = {
        new Point(0, 0),
        new Point(0, 2),
        new Point(1, 1),
        new Point(1, 3),
        new Point(0, 4)
    };
    var severingAngles = SeveringResolver.GetDirectionsToSever(polygonalLine);
    foreach (var angle in severingAngles)
    {
        var fromDegree = angle.X * 360 / 2 / Math.PI;
        var toDegree = angle.Y * 360 / 2 / Math.PI;
        new Point(fromDegree, toDegree).Dump();
    }
}

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


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

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

13   голосов , оценка 3.846 из 5
Похожие ответы