Алгоритм сканирующей прямой (Бентли-Оттманна)

namespace Core2022.Plane
{
    /// <summary>Структура для точки на плоскости.</summary>
    public struct Point2D : IEquatable<Point2D>
    {
        public double X { get; set; }
        public double Y { get; set; }
 
        public Point2D(double x, double y)
        {
            X = x;
            Y = y;
        }
 
        public override bool Equals(object? obj)
        {
            return obj is Point2D d && Equals(d);
        }
 
        public bool Equals(Point2D other)
        {
            return X == other.X &&
                   Y == other.Y;
        }
 
        public override int GetHashCode()
        {
            return HashCode.Combine(X, Y);
        }
 
        public static bool operator ==(Point2D left, Point2D right)
        {
            return left.Equals(right);
        }
 
        public static bool operator !=(Point2D left, Point2D right)
        {
            return !(left == right);
        }
        public override string ToString() => $"({X}; {Y})";
        public static Point2D Parse(string text)
        {
            var split = text.Split("( ;)".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);
            if (split.Length != 2)
                throw new ArgumentException("Должно быть два числа разделённых пробелом и/или точкой запятой, скобками.", nameof(text));
            return new Point2D(double.Parse(split[0]), double.Parse(split[1]));
        }
        public static bool TryParse(string text, out Point2D point)
        {
            var split = text.Split(' ', ';', StringSplitOptions.RemoveEmptyEntries);
            if (split.Length != 2 ||
                !double.TryParse(split[0], out double x) ||
                !double.TryParse(split[1], out double y))
            {
                point = new Point2D();
                return false;
            }
            point = new Point2D(x, y);
            return true;
        }
 
        public static double Distance(Point2D a, Point2D b)
        {
            double dx = b.X - a.X;
            double dy = b.Y - a.Y;
            return Math.Sqrt(dx * dx + dy * dy);
        }
        public double Distance(Point2D b)
           => Distance(this, b);
    }
}

namespace Core2022.Plane
{
    /// <summary>Структура для сектора обзора.</summary>
    public struct Sector
    {
        /// <summary>Угол средней линии.</summary>
        public double MeanLine { get; set; }
 
        private double _width;
        /// <summary>Ширина угла сектора.</summary>
        public double Width
        {
            get => _width;
            set
            {
                if (value < 0)
                    throw new ArgumentOutOfRangeException(nameof(value), "Отрицательное значение не допускается.");
                _width = value;
            }
        }
 
        /// <summary>Угол начала сектора.</summary>
        public double Begin => MeanLine - 0.5 * Width;
 
        /// <summary>Угол конца сектора.</summary>
        public double End => MeanLine + 0.5 * Width;
 
        /// <summary>Создаёт сектор перекрытия окружности для точки.</summary>
        /// <param name="point">Точка, которой перекрывается сектор.</param>
        /// <param name="center">Центр окружности, перекрывающей сектор.</param>
        /// <param name="radius">Радиус окружности, перекрывающей сектор.</param>
        /// <returns><see cref="Sector"/>.</returns>
        /// <exception cref="ArgumentException">Если <paramref name="radius"/> Не число.</exception>
        /// <exception cref="ArgumentOutOfRangeException">Если <paramref name="radius"/> отрицательное число.</exception>
        public static Sector Create(Point2D point, Point2D center, double radius)
        {
            if (!double.IsNormal(radius))
                throw new ArgumentException("Не число.", nameof(radius));
            if (radius < 0)
                throw new ArgumentOutOfRangeException(nameof(radius), "Отрицательное значение не допускается.");
 
            Sector @new = new()
            {
                MeanLine = Math.Atan2(center.Y - point.Y, center.X - point.X),
                Width = 2 * Math.Asin(radius / point.Distance(center))
            };
 
            return @new;
        }
    }
}

namespace Core2022.Data
{
    public readonly struct DoubleRange : IEquatable<DoubleRange>, IComparable<DoubleRange>, IComparable
    {
        public double Start { get; }
 
        public double End { get; }
 
        public DoubleRange(double start, double end)
        {
            if (!double.IsNormal(start))
                throw new ArgumentException("Допускаются только нормальные числа.", nameof(start));
            if (!double.IsNormal(end))
                throw new ArgumentException("Допускаются только нормальные числа.", nameof(end));
            if (start > end)
                throw new ArgumentOutOfRangeException(nameof(start), "Не может превышать end.");
 
            Start = start;
            End = end;
        }
 
        public int CompareTo(DoubleRange other)
        {
            int comp = Start.CompareTo(other.Start);
            if (comp == 0)
            {
                comp = End.CompareTo(other.End);
            }
            return comp;
        }
 
        public int CompareTo(object? obj)
        {
            if (obj is not DoubleRange range)
                throw new NotImplementedException("Сравнение реализовано только для DoubleRange.");
            return CompareTo(range);
        }
 
        public override bool Equals(object? obj)
        {
            return obj is DoubleRange range && Equals(range);
        }
 
        public bool Equals(DoubleRange other)
        {
            return Start == other.Start &&
                   End == other.End;
        }
 
        public override int GetHashCode()
        {
            return HashCode.Combine(Start, End);
        }
 
        public static bool operator ==(DoubleRange left, DoubleRange right)
        {
            return left.Equals(right);
        }
 
        public static bool operator !=(DoubleRange left, DoubleRange right)
        {
            return !(left == right);
        }
 
    }
}

using System.Collections.ObjectModel;
 
namespace Core2022.Data
{
    /// <summary>Класс фрагментированного диапазона.</summary>
    public class FragmentedRange
    {
        /// <summary>Коллекция фрагментов.
        /// Коллекция сортирована по <see cref="DoubleRange.Start"/>.
        /// Все пересекающиеся фрагменты объединены.</summary>
        public ReadOnlyCollection<DoubleRange> Ranges { get; }
 
        // Приватный мутабельный список фрагментов.
        private readonly List<DoubleRange> rangeList = new();
 
        // Конструктор. В нём связываются публичная иммутабельная коллекция и приватный мутабельный список.
        public FragmentedRange() => Ranges = new ReadOnlyCollection<DoubleRange>(rangeList);
 
        /// <summary>Добавление фрагмента.</summary>
        /// <param name="range">Диапазон фрагмента.</param>
        public void Add(DoubleRange range)
        {
            int index = rangeList.BinarySearch(range);
 
            // Если индекс положительный, значит есть диапазон с таким началом.
            if (index >= 0)
            {
                // Если конец диапазона не превышает конец имеющегося, то добавлять ничего не нужно.
                if (range.End <= rangeList[index].End)
                {
                    return;
                }
                // В противном случая - заменяем диапазон.
                rangeList[index] = range;
            }
 
            // Если диапазона с таким же индексом нет, то индекс будет отрицательным.
            // Его значение - инверсия индекса ближайшего большего элемента или Count.
            else
            {
                index = ~index; // Индекс ближайшего большего.
 
                // Проверка пересечения с предыдущим диапазоном
                if (index > 0 && rangeList[index - 1].End >= range.Start)
                {
                    index--;
                    // Если конец диапазона не превышает конец имеющегося, то добавлять ничего не нужно.
                    if (range.End <= rangeList[index].End)
                    {
                        return;
                    }
                    // В противном случая - объединяем диапазоны.
                    range = new DoubleRange(rangeList[index].Start, range.End);
                    rangeList[index] = range;
                }
                // Если не сливается с предыдущим, то вставка перед ближайшим большим.
                else
                {
                    rangeList.Insert(index, range);
                }
            }
 
            // Теперь нужно проверить слияние диапазонов.
 
            for (int i = index + 1; i < rangeList.Count; i++)
            {
                var current = rangeList[i];
                // Проверка условия выхода.
                // Если диапазон заканчивается после конца добавленного,
                // то дальше перебирать нет смысла. 
                if (current.End > range.End)
                {
                    // Проверка условия объединения.
                    // Если диапазон начинается до конца добавленного,
                    // то нужно объединить диапазоны. 
                    if (current.Start <= range.End)
                    {
                        range = new(range.Start, current.End);
                        rangeList[index] = range;
                        rangeList.RemoveAt(i);
                    }
 
                    break;
                }
 
                // Если диапазон заканчивается до конца добавленного,
                // то его нужно удалить.
                rangeList.RemoveAt(i);
                i--;
            }
        }
    }
}