Круг разрезан несамопересекающейся ломаной, координаты вершин которой заданы парами натуральных чисел - 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();
}
}