<repo_name>penguin-of-linux/PenguinsLib<file_sep>/Geometry/Objects/Ray.cs
﻿namespace Geometry
{public struct Ray
    {
        public readonly Vector2 Begin;
        public readonly Vector2 Vector;

        public Ray(Vector2 begin, Vector2 vector)
        {
            Begin = begin;
            Vector = vector;
        }

        public bool Equals(Ray other)
        {
            return Begin.Equals(other.Begin) && Vector.Equals(other.Vector);
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj)) return false;
            return obj is Ray && Equals((Ray)obj);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                return (Begin.GetHashCode() * 397) ^ Vector.GetHashCode();
            }
        }
    }
}<file_sep>/Tests/GeometryTests.cs
﻿using System;
using System.Collections.Generic;
using System.Security.Cryptography.X509Certificates;
using NUnit.Framework;

using Geometry;
using NUnit.Framework.Internal;

namespace Tests
{
    public class GeometryTests
    {
        // Замечание: в большинстве тестов на пересечение проверяется только тип возвращаемого объекта, 
        //т.к. все пересечения основаны на пересечении прямых. Пересечение прямых и отрезков проверяется нормально.

        [TestCase(0, 0, -1, 1, 2, 1, 0, 1, TestName = "Simple perpendicular")]
        [TestCase(0, 0, 1, 1, 2, 1, 1, 1, TestName = "Left seg point")]
        [TestCase(0, 0, -2, 1, 0, 1, 0, 1, TestName = "Right seg point")]
        [TestCase(0, 0, -1, 0, 1, 0, 0, 0, TestName = "On segment")]
        [TestCase(0, 0, 1, 0, 2, 0, 1, 0, TestName = "On seg line")]
        public void GetNearestPointOfSegment_TestCase(double xp, double yp, double xs1, double ys1, 
            double xs2, double ys2, double expx, double expy)
        {
            var point = new Vector2(xp, yp);
            var seg = new Segment(xs1, ys1, xs2, ys2);
            var expPoint = new Vector2(expx, expy);

            var intPoint = GeometryMethods.GetNearestPointOfSegment(point, seg);

            Assert.True(intPoint.Equals(expPoint));
        }

        [TestCase(0, 0, 2, 2, 1, 1, 3, 3, ExpectedResult = true, TestName = "Simple 1")]
        [TestCase(2, 2, 0, 0, 3, 3, 1, 1, ExpectedResult = true, TestName = "Somple 2")]
        [TestCase(0, 0, 2, 2, 2, 0, 3, 2, ExpectedResult = true, TestName = "Common side")]
        [TestCase(0, 0, 2, 2, 2, 2, 3, 3, ExpectedResult = true, TestName = "Common vertex")]
        [TestCase(0, 0, 3, 3, 1, 1, 2, 2, ExpectedResult = true, TestName = "Inserted")]
        [TestCase(0, 0, 0, 10, -1, 3, 1, 7, ExpectedResult = true, TestName = "One rect is segment! Proizvol! Hotya it works...")]
        [TestCase(0, 0, 2, 2, 2, 0, 2, 2, ExpectedResult = true, TestName = "Another rect is segment")]
        [TestCase(0, 0, 1, 1, 2, 2, 3, 3, ExpectedResult = false, TestName = "Simple false 1")]
        [TestCase(1, 1, 0, 0, 3, 3, 2, 2, ExpectedResult = false, TestName = "Simple false 2")]
        public bool IsSimplifiedRectanglesInterescting_TestCase(double x1, double y1, double x2, double y2, 
            double x3, double y3, double x4, double y4)
        {
            var rect1 = new SimplifiedRectangle(x1, y1, x2, y2);
            var rect2 = new SimplifiedRectangle(x3, y3, x4, y4);

            return GeometryMethods.IsSimplifiedRectanglesInterescting(rect1, rect2);
        }

        [TestCase(0, 0, 0, 2, -1, 1, 1, 1, ExpectedResult = IntersectionResult.Point, TestName = "Simple '+'")]
        [TestCase(0, 0, 2, 0, 1, 0, 3, 0, ExpectedResult = IntersectionResult.Segment, TestName = "One common line")]
        [TestCase(0, 0, 2, 0, 2, 0, 2, 2, ExpectedResult = IntersectionResult.Point, TestName = "One common vertex, on line")]
        [TestCase(0, 0, 0, 2, 0, 2, 3, 3, ExpectedResult = IntersectionResult.Point, TestName = "One common vertex, off line")]
        [TestCase(0, 0, 2, 0, 2, 2, 4, 2, ExpectedResult = IntersectionResult.None, TestName = "Parallel OX")]
        [TestCase(0, 0, 0, 2, 1, 0, 1, 2, ExpectedResult = IntersectionResult.None, TestName = "Parallel OY")]
        [TestCase(0, 2, 2, 0, 0, 0, 2, 2, ExpectedResult = IntersectionResult.Point, TestName = "No simple '+'")]
        [TestCase(0, 1, 1, 2, 0, 0, 42, -42, ExpectedResult = IntersectionResult.None, TestName = "Just NONE")]
        public IntersectionResult GetSegmentsIntersection_TestCase(double x1, double y1, double x2, double y2, 
            double x3, double y3, double x4, double y4)
        {
            var seg1 = new Segment(x1, y1, x2, y2);
            var seg2 = new Segment(x3, y3, x4, y4);

            return GeometryMethods.GetSegmentsIntersection(seg1, seg2, out var result);
        }

        [TestCase(0, 0, 1, 0, 0, 1, 0, 0, ExpectedResult = IntersectionResult.Point, TestName = "+")]
        [TestCase(0, 0, 1, 1, 0, 1, 1, 0, ExpectedResult = IntersectionResult.Point, TestName = "x")]
        [TestCase(0, 0, 1, 0, 0, 1, 1, 1, ExpectedResult = IntersectionResult.None, TestName = "===")]
        [TestCase(0, 0, 1, 0, -1, 0, 3, 0, ExpectedResult = IntersectionResult.Line, TestName = "----")]
        [TestCase(0, 0, 0, 1, 1, 0, 1, 1, ExpectedResult = IntersectionResult.None, TestName = "||")]
        [TestCase(0, 0, 0, 1, 0, 4, 0, 10, ExpectedResult = IntersectionResult.Line, TestName = "|")]
        [TestCase(0, 0, 1, 1, 1, 0, 2, 1, ExpectedResult = IntersectionResult.None, TestName = "//")]
        public IntersectionResult GetLinesIntersection_Type_TestCase(double x1, double y1, double x2, double y2, 
            double x3, double y3, double x4, double y4)
        {
            var line1 = new Line(x1, y1, x2, y2);
            var line2 = new Line(x3, y3, x4, y4);

            return GeometryMethods.GetLinesIntersection(line1, line2, out var result);
        }

        [TestCase(0, 0, 1, 0, 0, 1, 0, 0, 0, 0, TestName = "+")]
        [TestCase(0, 0, 1, 1, -5, 3, -4, 2, -1, -1, TestName = @"\/")]
        public void GetLinesIntersection_Value_TestCase(double x1, double y1, double x2, double y2,
            double x3, double y3, double x4, double y4, double expx, double expy)
        {
            var line1 = new Line(x1, y1, x2, y2);
            var line2 = new Line(x3, y3, x4, y4);

            GeometryMethods.GetLinesIntersection(line1, line2, out var result);

            Assert.AreEqual(new Vector2(expx, expy), (Vector2)result);
        }

        [TestCase(1, 0, 1, 0, ExpectedResult = true, TestName = "(1, 0) (1, 0)")]
        [TestCase(1, 0, 2, 0, ExpectedResult = true, TestName = "(1, 0) (2, 0)")]
        [TestCase(1, 0, 0, 1, ExpectedResult = false, TestName = "(1, 0) (0, 1)")]
        public bool IsVectorCollinear_TestCase(double x1, double y1, double x2, double y2)
        {
            var v1 = new Vector2(x1, y1);
            var v2 = new Vector2(x2, y2);

            return GeometryMethods.IsVectorsCollinear(v1, v2);
        }

        [TestCase(false, 0, 2, 2, 2, 0, 0, 1, 1, ExpectedResult = IntersectionResult.None, TestName = "F, Not intersecting")]
        [TestCase(true, 0, 2, 2, 2, 0, 0, 1, 1, ExpectedResult = IntersectionResult.None, TestName = "T, Not intersecting")]
        [TestCase(false, -1, 0, 1, 2, 0, 0, 1, 1, ExpectedResult = IntersectionResult.Point, TestName = "F, Rect vertex")]
        [TestCase(true, -1, 0, 1, 2, 0, 0, 1, 1, ExpectedResult = IntersectionResult.Point, TestName = "T, Rect vertex")]
        [TestCase(false, 1, 3, 1, 1, 0, 0, 2, 2, ExpectedResult = IntersectionResult.Point, TestName = "F, One side inter")]
        [TestCase(true, 1, 3, 1, 1, 0, 0, 2, 2, ExpectedResult = IntersectionResult.Segment, TestName = "T, One side inter")]
        [TestCase(false, 1, 2, 1, 1, 0, 0, 2, 2, ExpectedResult = IntersectionResult.Point, TestName = "F, Seg begin on rect side")]
        [TestCase(true, 1, 3, 1, 1, 0, 0, 2, 2, ExpectedResult = IntersectionResult.Segment, TestName = "T, Seg begin on rect side")]
        [TestCase(false, 1, 1, 2, 1, 0, 0, 3, 3, ExpectedResult = IntersectionResult.None, TestName = "F, Seg full inside rect")]
        [TestCase(true, 1, 1, 2, 1, 0, 0, 3, 3, ExpectedResult = IntersectionResult.Segment, TestName = "T, Seg full inside rect")]
        [TestCase(false, 0, 0, 2, 2, 0, 0, 2, 2, ExpectedResult = IntersectionResult.Points, TestName = "F, Seg vertexes on rect")]
        [TestCase(true, 0, 0, 2, 2, 0, 0, 2, 2, ExpectedResult = IntersectionResult.Segment, TestName = "T, Seg vertexes on rect")]
        [TestCase(false, 0, 0, 2, 0, 0, 0, 2, 2, ExpectedResult = IntersectionResult.Segment, TestName = "F, Seg on rect side")]
        [TestCase(true, 0, 0, 2, 0, 0, 0, 2, 2, ExpectedResult = IntersectionResult.Segment, TestName = "T, Seg on rect side")]

        [TestCase(true, 0, 0, 75, 75, 25, 25, 75, 75, ExpectedResult = IntersectionResult.Segment, TestName = "T, LALALA")]
        public IntersectionResult GetSegmentSimplifiedRectangleIntersection_TestCase(bool filled, params double[] nums)
        {
            var seg = new Segment(nums[0], nums[1], nums[2], nums[3]);
            var rect = new SimplifiedRectangle(nums[4], nums[5], nums[6], nums[7]);

            return GeometryMethods.GetSegmentSimplifiedRectangleIntersection(seg, rect, out var result, filled);
        }

        [TestCase(Math.PI, Math.PI, TestName = "P -> P")]
        [TestCase(3 * Math.PI, Math.PI, TestName = "3P -> P")]
        [TestCase(-3 * Math.PI, Math.PI, TestName = "-3P -> P")]
        [TestCase(3 * Math.PI + Math.PI / 2, 3 * Math.PI / 2, TestName = "3.5P -> 1.5P")]
        [TestCase(-3 * Math.PI - Math.PI / 2, Math.PI / 2, TestName = "-3.5P -> P/2")]
        [TestCase(1, 1, TestName = "1 -> 1")]
        public void GetNormalizedAngle_TestCase(double angle, double expected)
        {
            var result = GeometryMethods.GetNormalizedAngle(angle);

            Assert.AreEqual(expected, result, 0.01);
        }

        [TestCase(0, Math.PI, Math.PI, TestName = "0, P")]
        [TestCase(0, Math.PI * 3/2d, -Math.PI / 2, TestName = "0, 3/2P")]
        [TestCase(Math.PI, Math.PI * 3/2d, Math.PI / 2, TestName = "P, 3/2P")]
        [TestCase(Math.PI * 3/2d, Math.PI, -Math.PI / 2, TestName = "3/2P, P")]
        [TestCase(1, 1, 0, TestName = "1, 1")]
        [TestCase(Math.PI / 4, -Math.PI / 4, -Math.PI / 2, TestName = "P/4, -P/4")]
        public void GetAnglesDifference_TestCase(double a1, double a2, double expected)
        {
            var result = GeometryMethods.GetAnglesDifference(a1, a2);

            Assert.AreEqual(expected, result, 0.01);
        }

        [TestCase(1, 0, 1, 1, Math.PI / 4, TestName = "(1, 0), (1, 1), P/4")]
        [TestCase(1, 1, 1, 0, 2 * Math.PI - Math.PI / 4, TestName = "(1, 1), (1, 0), 7P/4")]
        public void GetAngleBetweenVectorCww_TestCase(double x1, double y1, double x2, double y2, double exp)
        {
            var v1 = new Vector2(x1, y1);
            var v2 = new Vector2(x2, y2);

            var result = GeometryMethods.GetAngleBetweenVectorCww(v1, v2);

            Assert.AreEqual(exp, result, 0.01);
        }

        [TestCase(0, 0, 1, 1, 0, 0, 3, ExpectedResult = IntersectionResult.Point, TestName = "Circle center is ray begin")]
        public IntersectionResult GetRayCircleIntersection(double x1, double y1, double x2, double y2, double xc, double yc, double r)
        {
            var ray = new Ray(new Vector2(x1, y1), new Vector2(x2, y2));
            var circle = new Circle(xc, yc, r);

            return GeometryMethods.GetRayCircleIntersection(ray, circle, out var _);
        }

        [Test]
        public void GetLineCircleIntersection_NoPoints()
        {
            var line = new Line(0, 2, 1, 2);
            var circle = new Circle(0, 0, 1);

            var inter = GeometryMethods.GetLineCircleIntersection(line, circle, out var result);

            Assert.AreEqual(IntersectionResult.None, inter);
        }

        [Test]
        public void GetLineCircleIntersection_OnePoint()
        {
            var line = new Line(0, 1, 1, 1);
            var circle = new Circle(0, 0, 1);

            var inter = GeometryMethods.GetLineCircleIntersection(line, circle, out var result);

            Assert.AreEqual(new Vector2(0, 1), (Vector2) result);
        }
    }
}
<file_sep>/Geometry/Objects/IntVector2.cs
﻿using System;

namespace Geometry
{
    public struct IntVector2
    {
        public double Length => Math.Sqrt(X * X + Y * Y);

        public readonly int X;
        public readonly int Y;

        public IntVector2(int x, int y)
        {
            X = x;
            Y = y;
        }

        public static IntVector2 operator +(IntVector2 v1, IntVector2 v2)
        {
            return new IntVector2(v1.X + v2.X, v1.Y + v2.Y);
        }

        public static IntVector2 operator -(IntVector2 v1, IntVector2 v2)
        {
            return v1 + (-v2);
        }

        public static IntVector2 operator -(IntVector2 v)
        {
            return new IntVector2(-v.X, -v.Y);
        }

        public static IntVector2 operator *(IntVector2 v, int k)
        {
            return new IntVector2(v.X * k, v.Y * k);
        }

        public static IntVector2 operator *(int k, IntVector2 v)
        {
            return v * k;
        }

        public static implicit operator IntVector2(Vector2 vec)
        {
            return new IntVector2((int)vec.X, (int)vec.Y);
        }

        public IntVector2 GetNormalized()
        {
            if (Length.Equal(0))
                return new IntVector2(0, 0);

            var x = (int)(X / Length);
            var y = (int)(Y / Length);

            return new IntVector2(x, y);
        }

        public override string ToString()
        {
            return $"{X} {Y}";
        }

        public override bool Equals(object other)
        {
            if (other is IntVector2 vector2)
                return Equals(vector2);

            if (other is Vector2 vec)
                return Equals(vec);

            return false;
        }

        private bool Equals(IntVector2 other)
        {
            return X == other.X && Y == other.Y;
        }

        private bool Equals(Vector2 other)
        {
            IntVector2 vec = other;
            return Equals(vec);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                return X.GetHashCode() * 397 + Y.GetHashCode() * 7;
            }
        }
    }
}<file_sep>/Geometry/Objects/Vector2.cs
﻿using System;

namespace Geometry
{
    public struct Vector2
    {
        public double Length => Math.Sqrt(X * X + Y * Y);

        public readonly double X;
        public readonly double Y;

        public Vector2(double x, double y)
        {
            X = x;
            Y = y;
        }

        public static Vector2 operator +(Vector2 v1, Vector2 v2)
        {
            return new Vector2(v1.X + v2.X, v1.Y + v2.Y);
        }

        public static Vector2 operator -(Vector2 v1, Vector2 v2)
        {
            return v1 + (-v2);
        }

        public static Vector2 operator -(Vector2 v)
        {
            return new Vector2(-v.X, -v.Y);
        }

        public static Vector2 operator *(Vector2 v, double k)
        {
            return new Vector2(v.X * k, v.Y * k);
        }

        public static Vector2 operator *(double k, Vector2 v)
        {
            return v * k;
        }

        public static implicit operator Vector2(IntVector2 vec)
        {
            return new Vector2(vec.X, vec.Y);
        }

        public Vector2 GetNormalized()
        {
            if (Length.Equal(0))
                return new Vector2(0, 0);

            var x = X / Length;
            var y = Y / Length;

            return new Vector2(x, y);
        }

        public override string ToString()
        {
            return $"{X} {Y}";
        }

        public override bool Equals(object other)
        {
            if (other is Vector2 vector2)
                return Equals(vector2);

            if (other is IntVector2 intVector2)
                return Equals(intVector2);

            return false;
        }

        private bool Equals(Vector2 other)
        {
            return X.Equal(other.X) && Y.Equal(other.Y);
        }

        private bool Equals(IntVector2 other)
        {
            Vector2 vec = other;
            return Equals(vec);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                return X.GetHashCode() * 397 + Y.GetHashCode() * 7;
            }
        }
    }
}<file_sep>/Geometry/tie.py
import glob
import re


def short_using_string(str):
	index = str.find('using')
	if not index == -1:
		return str[index:]
	else:
		return ""
	

if __name__ == "__main__":


	body = ""
	usings = set()

	files = glob.glob('**/*.cs', recursive=True)
	for filename in files:
		if not filename.startswith('obj') and not filename.startswith('bin') and not filename.startswith('Properties'):
			with open(filename, 'r') as file:
				text = file.read()
				start = text.index('{')
				finish = text.rindex('}')
				
				namespace_index = text.find('namespace')
				for using in text[:namespace_index].splitlines():
					usings.add(short_using_string(using))
				
				body += text[start+1:finish]
			
	with open('tie_result.txt', 'w') as file:
		for using in usings:
			if not using == "":
				file.write(using + '\n')
		file.write('\n\nnamespace FantasticBits {\n')
		file.write(body)
		file.write('\n}')<file_sep>/Geometry/DoubleExtensions.cs
﻿namespace Geometry
{
    public static class DoubleExtensions
    {
        public static bool Less(this double a, double b, double eps = 0.001)
        {
            return b - a > eps;
        }
        public static bool Greater(this double a, double b, double eps = 0.001)
        {
            return b.Less(a, eps);
        }
        public static bool Equal(this double a, double b, double eps = 0.001)
        {
            return !a.Less(b, eps) && !a.Greater(b, eps);
        }
        public static bool LessOrEqual(this double a, double b, double eps = 0.001)
        {
            return a.Less(b, eps) || a.Equal(b, eps);
        }
        public static bool GreaterOrEqual(this double a, double b, double eps = 0.001)
        {
            return a.Greater(b, eps) || a.Equal(b, eps);
        }
    }
}<file_sep>/Geometry/Objects/Segment.cs
﻿namespace Geometry
{
    public struct Segment
    {
        public readonly Vector2 Begin;
        public readonly Vector2 End;

        public Vector2[] Points => new[] { Begin, End };

        public Segment(Vector2 begin, Vector2 end)
        {
            Begin = begin;
            End = end;
        }

        public Segment(double x1, double y1, double x2, double y2)
            : this(new Vector2(x1, y1), new Vector2(x2, y2))
        {

        }

        public override string ToString()
        {
            return $"{Begin}, {End}";
        }

        public override int GetHashCode()
        {
            unchecked
            {
                return (Begin.GetHashCode() * 397) ^ End.GetHashCode();
            }
        }

        public bool Equals(Segment other)
        {
            return Begin.Equals(other.Begin) && End.Equals(other.End);
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj)) return false;
            return obj is Segment && Equals((Segment) obj);
        }
    }
}<file_sep>/Geometry/Objects/SimplifiedRectangle.cs
﻿using System;
using System.Collections.Generic;

namespace Geometry
{
    public struct SimplifiedRectangle
    {
        public readonly Vector2 V1;
        public readonly Vector2 V2;

        public readonly double Height;
        public readonly double Width;

        /// <summary>
        /// Rectangle with parallel to axis OY OX sides
        /// </summary>
        public SimplifiedRectangle(Vector2 v1, Vector2 v2) : this(v1.X, v1.Y, v2.X, v2.Y)
        {
        }

        /// <summary>
        /// Rectangle with parallel to axis OY OX sides
        /// </summary>
        public SimplifiedRectangle(double x1, double y1, double x2, double y2)
        {
            V1 = new Vector2(x1, y1);
            V2 = new Vector2(x2, y2);

            Width = Math.Abs(x1 - x2);
            Height = Math.Abs(y1 - y2);
        }

        /*public bool HasPoint(Vector2 point, bool withInsides = false)
        {
            if (withInsides) throw new NotImplementedException("I am so lazy");

            if (point.Equals(V1)) return true;
            if (point.Equals(V2)) return true;
            if (point.Equals(new Vector2(V1.X, V2.Y))) return true;
            if (point.Equals(new Vector2(V2.X, V1.Y))) return true;

            return false;
        }*/

        public IEnumerable<Vector2> Vertexes => new[]
        {
            V1, V2, new Vector2(V1.X, V2.Y), new Vector2(V2.X, V1.Y)
        };

        /*public bool HasPoint(double x, double y, bool withInsides = false)
        {
            return HasPoint(new Vector2(x, y), withInsides);
        }*/

        public Segment[] Segments => new[]
        {
            new Segment(V1.X, V1.Y, V2.X, V1.Y),
            new Segment(V1.X, V1.Y, V1.X, V2.Y),
            new Segment(V2.X, V1.Y, V2.X, V2.Y),
            new Segment(V1.X, V2.Y, V2.X, V2.Y)
        };

        public bool Equals(SimplifiedRectangle other)
        {
            return V1.Equals(other.V1) && V2.Equals(other.V2);
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj)) return false;
            return obj is SimplifiedRectangle && Equals((SimplifiedRectangle)obj);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                return (V1.GetHashCode() * 397) ^ V2.GetHashCode();
            }
        }
    }
}<file_sep>/Geometry/Objects/Circle.cs
﻿namespace Geometry
{
    public struct Circle
    {
        public readonly Vector2 Center;
        public readonly double R;

        public Circle(Vector2 center, double r)
        {
            Center = center;
            R = r;
        }

        public Circle(double x, double y, double r) : this(new Vector2(x, y), r)
        {

        }

        public bool Equals(Circle other)
        {
            return Center.Equals(other.Center) && R.Equal(other.R);
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj)) return false;
            return obj is Circle && Equals((Circle) obj);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                return (Center.GetHashCode() * 397) ^ R.GetHashCode();
            }
        }
    }
}<file_sep>/Geometry/Objects/Line.cs
﻿using System;

namespace Geometry
{
    public struct Line
    {
        public readonly double A;
        public readonly double B;
        public readonly double C;

        public Line(double a, double b, double c)
        {
            if (a.Equal(0) && b.Equal(0))
                throw new ArgumentException("A and B are equal 0");

            A = a;
            B = b;
            C = c;
        }

        public Line(double x1, double y1, double x2, double y2)
        {
            if (x1.Equal(x2) && y1.Equal(y2))
                throw new ArgumentException("Equivalent points");

            A = y1 - y2;
            B = x2 - x1;
            C = x1 * y2 - x2 * y1;
        }

        public Line(Vector2 v1, Vector2 v2) : this(v1.X, v1.Y, v2.X, v2.Y)
        {
        }

        public Line(Vector2 vector, double x, double y)
        {
            if (vector.X.Equal(0) && vector.Y.Equal(0))
                throw new ArgumentException($"Vector cannot be zero");

            A = vector.Y;
            B = -vector.X;
            C = vector.X * y - vector.Y * x;
        }

        public Line(Ray ray) : this(ray.Vector, ray.Begin.X, ray.Begin.Y)
        {
        }

        public Line(Segment seg) : this(seg.Begin, seg.End)
        {
        }

        public bool Equals(Line other)
        {
            return A.Equal(other.A) && B.Equal(other.B) && C.Equal(other.C);
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj)) return false;
            return obj is Line && Equals((Line)obj);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                var hashCode = A.GetHashCode();
                hashCode = (hashCode * 397) ^ B.GetHashCode();
                hashCode = (hashCode * 397) ^ C.GetHashCode();
                return hashCode;
            }
        }
    }
}<file_sep>/Geometry/IntersectionResult.cs
﻿namespace Geometry
{
    /// <summary>
    /// Тип пересечения фигур. Point - Vector2,  Points - Vector2[], None - null, остальные соответствуют классам
    /// </summary>
    public enum IntersectionResult
    {
        Point,
        Points,
        Line,
        Segment,
        Ray,
        None
    }
}<file_sep>/Geometry/GeometryMethods.cs
﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace Geometry
{
    public static class GeometryMethods
    {
        /// <summary>
        /// Returns angle between vectors counterclock-wise
        /// </summary>
        public static double GetAngleBetweenVectorCww(Vector2 v1, Vector2 v2)
        {
            var p = v1.X * v2.X + v1.Y * v2.Y;
            var cos = p / (v1.Length * v2.Length);
            var angle = Math.Acos(cos);

            if (cos.Equal(1))
                return 0;

            if (cos.Equal(-1))
                return Math.PI;

            // векторное произведение векторов на плоскости в базисе [(1, 0), (0, 1)]
            var c = new Vector3(0, 0, 1) * (v1.X * v2.Y - v2.X * v1.Y);

            if (c.Z > 0)
                return angle;

            return 2 * Math.PI - angle;
        }

        /// <summary>
        /// Angle difference, conterclock-wise. Those how much to add to a1 to get a2.
        /// </summary>
        /// <returns></returns>
        public static double GetAnglesDifference(double a1, double a2)
        {
            a1 = GetNormalizedAngle(a1);
            a2 = GetNormalizedAngle(a2);

            if (a1 > a2)
            {
                var cw = a1 - a2; // clockwise
                var ccw = 2 * Math.PI - cw; // counter cw

                return cw < ccw ? -cw : ccw;
            }
            else
            {
                var ccw = a2 - a1;
                var cw = 2 * Math.PI - ccw;

                return cw < ccw ? -cw : ccw;
            }
        }

        /// <summary>
        /// Distance on plane.
        /// </summary>
        public static double GetDistance(Vector2 v1, Vector2 v2)
        {
            return Math.Sqrt((v1.X - v2.X) * (v1.X - v2.X) + (v1.Y - v2.Y) * (v1.Y - v2.Y));
        }

        /// <summary>
        /// Distance from point to segment.
        /// </summary>
        public static double GetDistanceToSegment(Vector2 point, Segment segment)
        {
            var npoint = GetNearestPointOfSegment(point, segment);
            return GetDistance(point, npoint);
        }

        /// <summary>
        /// Line and circle intersection. Returns Point, Points, None
        /// </summary>
        public static IntersectionResult GetLineCircleIntersection(Line line, Circle circle, out object result)
        {
            var pline = new Line(new Vector2(line.A, line.B), circle.Center.X, circle.Center.Y);
            GetLinesIntersection(line, pline, out var intres);
            var ipoint = (Vector2) intres;  // перпендикулярные прямые, всегда точка

            var dist = GetDistance(circle.Center, ipoint);

            if (dist.Greater(circle.R))
            {
                result = null;
                return IntersectionResult.None;
            }


            if (dist.Equal(circle.R, 0.01)) // боюсь за точность тут
            {
                result = ipoint;
                return IntersectionResult.Point;
            }

            var d = Math.Sqrt(circle.R * circle.R + dist * dist);
            var a = Math.Sqrt(d * d / (line.A * line.A + line.B * line.B));
            var v = new Vector2(a, a);

            result = new[] { ipoint + v, ipoint - v };
            return IntersectionResult.Points;
        }

        /// <summary>
        /// Lines intersection. Returns Line, Point, None.
        /// </summary>
        public static IntersectionResult GetLinesIntersection(Line line1, Line line2, out object result)
        {
            /*// если прямые вертикальны
            if (line1.B.Equal(0) && line2.B.Equal(0))
            {
                // A и B не могут быть одновременно нулями, см. конструкторы Line
                if ((-line1.C / line1.A).Equal(-line2.C / line2.A)) 
                {
                    // если x1 == x2, то прямые совпадают
                    result = line1;
                    return IntersectionResult.Line;
                }

                result = null;
                return IntersectionResult.None;
            }

            if (line1.A.Equal(0) && line2.A.Equal(0))*/

            var v1 = new Vector2(-line1.B, line1.A);
            var v2 = new Vector2(-line2.B, line2.A);

            if (IsVectorsCollinear(v1, v2))
            {
                if (v1.X.Equal(0)) // если прямые вертикальны
                {
                    // A и B не могут быть одновременно нулями, см. конструкторы Line
                    if ((-line1.C / line1.A).Equal(-line2.C / line2.A))
                    {
                        // если x1 == x2, то прямые совпадают
                        result = line1;
                        return IntersectionResult.Line;
                    }

                    result = null;
                    return IntersectionResult.None;
                }
                else
                {
                    if (line1.C.Equal(line2.C))
                    {
                        result = line1;
                        return IntersectionResult.Line;
                    }
                    else
                    {
                        result = null;
                        return IntersectionResult.None;
                    }
                }
            }
            
            // вектора не коллинеарны
            try
            {
                var x = (line1.C * line2.B - line2.C * line1.B) / (line2.A * line1.B - line1.A * line2.B);
                var nonYLine = line1.B != 0 ? line1 : line2; // ищем прямую с B != 0
                var y = -(nonYLine.C + nonYLine.A * x) / nonYLine.B;

                if (double.IsNaN(x) || double.IsNaN(y))
                {
                    // прямые совпадают
                    result = line1;
                    return IntersectionResult.Line;
                }

                result = new Vector2(x, y);
                return IntersectionResult.Point;
            }
            catch (DivideByZeroException)
            {
                result = null;
                return IntersectionResult.None;
            }
        }

        /// <summary>
        /// Returns value of function that define by line. If line is vertical then returns null;
        /// </summary>
        public static double? GetLineFunctionValue(Line line, double arg)
        {
            if (line.B.Equal(0))
                return null;

            return (-line.C - line.A * arg) / line.B;
        }


        /// <summary>
        /// Line and segment intersection. Returns Segment, Point, None.
        /// </summary>
        public static IntersectionResult GetLineSegmentIntersection(Line line, Segment segment, out object result)
        {
            var segmentLine = new Line(segment.Begin.X, segment.Begin.Y, segment.End.X, segment.End.Y);
            var intersection = GetLinesIntersection(line, segmentLine, out var intres);

            if (intersection == IntersectionResult.Line)
            {
                result = segment;
                return IntersectionResult.Segment;
            }

            var iPoint = (Vector2) intres; // intersection point

            if (HasSegmentPoint(segment, iPoint))
            {
                result = iPoint;
                return IntersectionResult.Point;
            }
            else
            {
                result = null;
                return IntersectionResult.None;
            }
        }

        /// <summary>
        /// Nearest point of segment to given point.
        /// </summary>
        public static Vector2 GetNearestPointOfSegment(Vector2 point, Segment segment)
        {
            var segmentLine = new Line(segment.Begin.X, segment.Begin.Y, segment.End.X, segment.End.Y);
            var pVector = new Vector2(segmentLine.A, segmentLine.B); // perpendicular vector
            var pLine = new Line(pVector, point.X, point.Y); // perpendicular point

            var intersection = GetLineSegmentIntersection(pLine, segment, out var intres); // только Point

            if (intersection == IntersectionResult.Point)
                return (Vector2) intres;

            var distToBegin = GetDistance(point, segment.Begin);
            var distToEnd = GetDistance(point, segment.End);

            return distToBegin < distToEnd ? segment.Begin : segment.End;
        }

        /// <summary>
        /// Returns angle int range [0, 2P) that equals given
        /// </summary>
        public static double GetNormalizedAngle(double a)
        {
            return a - Math.Floor(a / (2 * Math.PI)) * 2 * Math.PI;
        }

        /// <summary>
        /// Ray and circle intersection. Returns Point, Point, None
        /// </summary>
        public static IntersectionResult GetRayCircleIntersection(Ray ray, Circle circle, out object result)
        {
            var line = new Line(ray);
            var intersection = GetLineCircleIntersection(line, circle, out var intres);

            if (intersection == IntersectionResult.None)
            {
                result = intres;
                return intersection;
            }

            if (intersection == IntersectionResult.Point)
            {
                var p = (Vector2) intres;
                if (HasRayPoint(ray, p))
                {
                    result = intres;
                    return IntersectionResult.Points;
                }
                else
                {
                    result = null;
                    return IntersectionResult.None;
                }
            }

            // intersection = Points
            var points = (Vector2[]) intres;
            var firstInRay = HasRayPoint(ray, points[0]);
            var secondInRay = HasRayPoint(ray, points[1]);

            if (firstInRay && secondInRay)
            {
                result = intres;
                return IntersectionResult.Points;
            }
            else if (firstInRay)
            {
                result = points[0];
                return IntersectionResult.Point;
            }
            else if (secondInRay)
            {
                result = points[1];
                return IntersectionResult.Point;
            }
            else
            {
                result = null;
                return IntersectionResult.None;
            }
        }

        /// <summary>
        /// Ray and line intersection. Return Ray, Point, None
        /// </summary>
        public static IntersectionResult GetRayLineIntersection(Ray ray, Line line, out object result)
        {
            var rayLine = new Line(ray.Vector, ray.Begin.X, ray.Begin.Y);
            var intersection = GetLinesIntersection(line, rayLine, out var intres);

            switch (intersection)
            {
                case IntersectionResult.Line:
                    result = ray;
                    return IntersectionResult.Ray;
                case IntersectionResult.None:
                    result = null;
                    return IntersectionResult.None;
                case IntersectionResult.Point:
                    if (HasRayPoint(ray, (Vector2)intres))
                    {
                        result = intres;
                        return IntersectionResult.Point;
                    }
                    else
                    {
                        result = null;
                        return IntersectionResult.None;
                    }
            }

            throw new Exception($"Internal error. GetLinesIntersection returned {intersection}");
        }

        /// <summary>
        /// Ray and segment intersection. Returns Segment, Point None.
        /// </summary>
        public static IntersectionResult GetRaySegmentIntersection(Ray ray, Segment segment, out object result)
        {
            var sline = new Line(segment.Begin.X, segment.Begin.Y, segment.End.X, segment.End.Y);
            var intersection = GetRayLineIntersection(ray, sline, out var intres);

            switch (intersection)
            {
                case IntersectionResult.Ray:
                    result = ray;
                    return IntersectionResult.Ray;
                case IntersectionResult.None:
                    result = null;
                    return IntersectionResult.None;
                case IntersectionResult.Point:
                    if (HasRayPoint(ray, (Vector2)intres))
                    {
                        result = intres;
                        return IntersectionResult.Point;
                    }
                    else
                    {
                        result = null;
                        return IntersectionResult.None;
                    }
            }

            throw new Exception($"Internal error. GetRaySegmentIntersection returned {intersection}");
        }

        /// <summary>
        /// Segments intersection. Returns Segment, Point, None
        /// </summary>
        public static IntersectionResult GetSegmentsIntersection(Segment seg1, Segment seg2, out object result)
        {
            var intersection = GetLinesIntersection(new Line(seg1), new Line(seg2), out var intres);

            if (intersection == IntersectionResult.None)
            {
                result = null;
                return IntersectionResult.None;
            }

            if (intersection == IntersectionResult.Point)
            {
                var iPoint = (Vector2) intres;
                if (HasSegmentPoint(seg1, iPoint) && HasSegmentPoint(seg2, iPoint))
                {
                    /*if (!includeBorders)
                        if (seg1.Begin.Equals(iPoint) || seg2.Begin.Equals(iPoint)
                                                      || seg1.End.Equals(iPoint) || seg2.End.Equals(iPoint))
                            return null;*/

                    result = intres;
                    return IntersectionResult.Point;
                }

                result = null;
                return IntersectionResult.None;
            }

            // отрезки лежат на одной прямой
            return GetSegmentsOnLineIntersection(seg1, seg2, out result);
        }

        public static IntersectionResult GetSegmentSimplifiedRectangleIntersection(Segment seg, 
            SimplifiedRectangle rect, out object result, bool filledRectangle = false)
        {
            var points = new List<Vector2>();

            foreach (var s in rect.Segments)
            {
                var intersection = GetSegmentsIntersection(seg, s, out var intres);

                switch (intersection)
                {
                    case IntersectionResult.Segment:
                        result = intres;
                        return IntersectionResult.Segment;
                    case IntersectionResult.Point:
                        points.Add((Vector2)intres);
                        break;
                    case IntersectionResult.None:
                        continue;
                }
            }

            points = points.Distinct().ToList(); // ох ужас

            // если точек пересечения нет, то вернем None
            // если точка пересечения одна, то она либо вершина прямоугольника и тогда мы вернем ее,
            //     либо точка пересечения является вершиной отрезка, и тогда мы вернем ее, если not filledRectangle, 
            //     иначе вернем отрезок,
            // если точек пересечения две, то вернем либо отрезок, либо 2 точки в зависимости от filledRectangle

            var beginInRect = IsPointInsideSimplifiedRectangle(seg.Begin, rect);
            var endInRect = IsPointInsideSimplifiedRectangle(seg.End, rect);

            if (points.Count == 0)
            {
                if (beginInRect && endInRect && filledRectangle)
                {
                    result = seg;
                    return IntersectionResult.Segment;
                }
                else
                {
                    result = null;
                    return IntersectionResult.None;
                }
            }

            if (points.Count == 1)
            {
                var point = points[0];

                if (filledRectangle)
                {
                    if (!beginInRect && !endInRect)
                    {
                        result = point;
                        return IntersectionResult.Point;
                    }

                    if (beginInRect && endInRect)
                    {
                        result = seg;
                        return IntersectionResult.Segment;
                    }

                    var pointInRect = beginInRect ? seg.Begin : seg.End;

                    if (pointInRect.Equals(point))
                    {
                        result = point;
                        return IntersectionResult.Point;
                    }
                    else
                    {
                        result = new Segment(pointInRect, point);
                        return IntersectionResult.Segment;
                    }
                }
                else
                {
                    result = points[0];
                    return IntersectionResult.Point;
                }
            }

            // точки две
            if (filledRectangle)
            {
                result = new Segment(points[0], points[1]);
                return IntersectionResult.Segment;
            }
            else
            {
                result = new[] { points[0], points[1] };
                return IntersectionResult.Points;
            }
        }

        /// <summary>
        /// Intersection of segments that lie on one line. Returns Segment, Point, None
        /// </summary>
        public static IntersectionResult GetSegmentsOnLineIntersection(Segment seg1, Segment seg2, out object result)
        {
            var axisChanged = false;

            if (seg1.Begin.X.Equal(seg1.End.X)) // если отрезки вертикальны
            {
                seg1 = new Segment(seg1.Begin.Y, seg1.Begin.X, seg1.End.Y, seg1.End.X);
                seg2 = new Segment(seg2.Begin.Y, seg2.Begin.X, seg2.End.Y, seg2.End.X);
                axisChanged = true;
            }

            var minx2 = Math.Min(seg2.Begin.X, seg2.End.X);
            var maxx2 = Math.Max(seg2.Begin.X, seg2.End.X);
            var minx1 = Math.Min(seg1.Begin.X, seg1.End.X);
            var maxx1 = Math.Max(seg1.Begin.X, seg1.End.X);

            if (minx1.Greater(maxx2) || minx2.Greater(maxx1)) // не пересекаются
            {
                result = null;
                return IntersectionResult.None;
            }

            var x1 = Math.Max(minx1, minx2);
            var x2 = Math.Min(maxx1, maxx2);

            var line = new Line(seg1);

            // решарпер не знает, что line не вертикальная, т.к. мы отразили отрезки в начале функции. Глупый решарпер.
            var y1 = GetLineFunctionValue(line, x1).Value;
            var y2 = GetLineFunctionValue(line, x2).Value;
            var seg = axisChanged ? new Segment(y1, x1, y2, x2) : new Segment(x1, y1, x2, y2);

            if (x1.Equal(x2))
            {
                result = new Vector2(x1, y1);
                return IntersectionResult.Point;
            }
            else
            {
                result = seg;
                return IntersectionResult.Segment;
            }
        }

        /// <summary>
        /// Проверяет, лежит ли точка на луче. Точка point лежит на линии луча.
        /// </summary>
        public static bool HasRayPoint(Ray ray, Vector2 point)
        {
            if (point.Equals(ray.Begin))
                return true;

            if (!ray.Vector.X.Equal(0))
            {
                if (ray.Vector.X.Greater(0))
                {
                    if (point.X.GreaterOrEqual(ray.Begin.X)) return true;
                    else return false;
                }
                else
                {
                    if (point.X.LessOrEqual(ray.Begin.X)) return true;
                    else return false;
                }
            }

            else
            {
                if (ray.Vector.Y.Greater(0))
                {
                    if (point.Y.GreaterOrEqual(ray.Begin.Y)) return true;
                    else return false;
                }
                else
                {
                    if (point.Y.LessOrEqual(ray.Begin.Y)) return true;
                    else return false;
                }
            }
        }

        /// <summary>
        /// Проверяет, лежит ли точка в отрезке. Точка point - точка, лежащая на линии отрезка
        /// </summary>
        public static bool HasSegmentPoint(Segment segment, Vector2 point)
        {
            var rspoint = segment.Begin.X.Greater(segment.End.X) ? segment.Begin : segment.End; // right segment point
            var lspoint = rspoint.Equals(segment.Begin) ? segment.End : segment.Begin;              // left segment point
            var tspoint = segment.Begin.Y.Greater(segment.End.Y) ? segment.Begin : segment.End; // top segment point
            var bspoint = tspoint.Equals(segment.Begin) ? segment.End : segment.Begin;              // bottom segment point

            return point.X.GreaterOrEqual(lspoint.X) && point.X.LessOrEqual(rspoint.X) &&
                   point.Y.GreaterOrEqual(bspoint.Y) && point.Y.LessOrEqual(tspoint.Y);
        }

        public static bool IsPointInsideSimplifiedRectangle(Vector2 point, SimplifiedRectangle rect)
        {
            return IsSimplifiedRectanglesInterescting(rect, new SimplifiedRectangle(point, point)); // :P смекалочка
        }

        public static bool IsSimplifiedRectanglesInterescting(SimplifiedRectangle rect1, SimplifiedRectangle rect2)
        {
            var minx1 = Math.Min(rect1.V1.X, rect1.V2.X);
            var maxx1 = Math.Max(rect1.V1.X, rect1.V2.X);
            var miny1 = Math.Min(rect1.V1.Y, rect1.V2.Y);
            var maxy1 = Math.Max(rect1.V1.Y, rect1.V2.Y);
            var minx2 = Math.Min(rect2.V1.X, rect2.V2.X);
            var maxx2 = Math.Max(rect2.V1.X, rect2.V2.X);
            var miny2 = Math.Min(rect2.V1.Y, rect2.V2.Y);
            var maxy2 = Math.Max(rect2.V1.Y, rect2.V2.Y);

            return (minx1 >= minx2 && minx1 <= maxx2 || maxx1 >= minx2 && maxx1 <= maxx2 || minx2 >= minx1 && maxx2 <= maxx1) &&
                   (miny1 >= miny2 && miny1 <= maxy2 || maxy1 >= miny2 && maxy1 <= maxy2 || miny2 >= miny1 && maxy2 <= maxy1);
        }

        public static bool IsVectorsCollinear(Vector2 v1, Vector2 v2)
        {
            var len1 = v1.Length;
            var len2 = v2.Length;
            if (len1.Equal(0) || len2.Equal(0))
                return true;

            var p = v1.X * v2.X + v1.Y * v2.Y;
            var cos = p / len1 / len2;

            return Math.Abs(cos).Equal(1);
        }
    }
}<file_sep>/Geometry/Objects/Vector3.cs
﻿using System;

namespace Geometry
{
    public struct Vector3
    {
        public double Length => Math.Sqrt(X * X + Y * Y + Z * Z);

        public readonly double X;
        public readonly double Y;
        public readonly double Z;

        public Vector3(double x, double y, double z)
        {
            X = x;
            Y = y;
            Z = z;
        }

        public static Vector3 operator +(Vector3 v1, Vector3 v2)
        {
            return new Vector3(v1.X + v2.X, v1.Y + v2.Y, v1.Z + v2.Z);
        }

        public static Vector3 operator -(Vector3 v1, Vector3 v2)
        {
            return v1 + (-v2);
        }

        public static Vector3 operator -(Vector3 v)
        {
            return new Vector3(-v.X, -v.Y, -v.Z);
        }

        public static Vector3 operator *(Vector3 v, double k)
        {
            return new Vector3(v.X * k, v.Y * k, v.Z * k);
        }

        public static Vector3 operator *(double k, Vector3 v)
        {
            return v * k;
        }

        public Vector3 GetNormalized()
        {
            if (Length.Equal(0))
                return new Vector3(0, 0, 0);

            var x = X / Length;
            var y = Y / Length;
            var z = Z / Length;

            return new Vector3(x, y, z);
        }

        public override string ToString()
        {
            return $"{X} {Y} {Z}";
        }

        public override bool Equals(object other)
        {
            if (other is Vector3 vector3)
                return Equals(vector3);

            return false;
        }

        private bool Equals(Vector3 other)
        {
            return X.Equal(other.X) && Y.Equal(other.Y) && Z.Equal(other.Z);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                return X.GetHashCode() * 397 + Y.GetHashCode() * 7 + Z.GetHashCode() * 13;
            }
        }
    }
}<file_sep>/Tests/Algorithms_FindPathAmongRectanglesTests.cs
﻿using Algorithms;
using Geometry;
using NUnit.Framework;

namespace Tests
{
    public class Algorithms_FindPathAmongRectanglesTests
    {
        [Test]
        public void WithoutBarriers()
        {
            var rectangles = new SimplifiedRectangle[0];
            var start = new Vector2(0, 0);
            var finish = new Vector2(10, 10);

            var path = AlgorithmsMethods.FindPathAmongRectangles(start, finish, rectangles);

            Assert.AreEqual(1, path.Length);
            Assert.AreEqual(finish, path[0]);
        }

        [Test]
        public void OneBarrier()
        {
            var rectangles = new SimplifiedRectangle[] {new SimplifiedRectangle(25, 25, 75, 75), };
            var start = new Vector2(0, 0);
            var finish = new Vector2(100, 100);

            var path = AlgorithmsMethods.FindPathAmongRectangles(start, finish, rectangles);

            Assert.AreEqual(2, path.Length);
            Assert.AreEqual(finish, path[1]);
        }


        [Test]
        public void DifficultTest()
        {
            /*
             11 x 11

             0 0 0 0 0 0 0 0 0 0 0
             0 0 0 0 0 0 0 0 0 0 0
             0 0 0 0 0 0 0 * * * *
             0 0 0 0 0 0 0 * * * *
             * * * 0 0 0 0 0 0 0 0
             * * * 0 0 0 * * * * *
             * * * 0 0 0 * * * * *
             0 0 * * * 0 * * * * *
             0 0 * * * 0 0 0 0 0 0
             0 0 0 0 0 0 0 0 0 0 0
             0 0 0 0 0 0 0 0 0 0 0
             */

            var rectangles = new SimplifiedRectangle[]
            {
                new SimplifiedRectangle(0, 4, 2, 6),
                new SimplifiedRectangle(2, 2, 4, 3), 
                new SimplifiedRectangle(6, 3, 10, 5), 
                new SimplifiedRectangle(7, 7, 10, 8), 
            };
            var start = new Vector2(0, 0);
            var finish = new Vector2(10, 10);

            var path = AlgorithmsMethods.FindPathAmongRectangles(start, finish, rectangles);

            // результат непредсказуем, т.к. юзаем бфс :)
            ;
            //Assert.AreEqual(4, path.Length);
        }

        [Test]
        public void PathToRectMiddleFromItsVertext()
        {
            var rectangles = new SimplifiedRectangle[]
            {
                new SimplifiedRectangle(0, 0, 20, 20)
            };
            var start = new Vector2(0, 0);
            var finish = new Vector2(10, 10);

            var path = AlgorithmsMethods.FindPathAmongRectangles(start, finish, rectangles);

            Assert.IsEmpty(path);
        }
    }
}<file_sep>/Algorithms/Algorithms.cs
﻿using System.Collections.Generic;
using System.Linq;

using Geometry;

namespace Algorithms
{
    public static class AlgorithmsMethods
    {
        /// <summary>
        /// Юзаем бфс :)
        /// </summary>
        public static Vector2[] FindPathAmongRectangles(Vector2 start, Vector2 finish, params SimplifiedRectangle[] rectangles)
        {
            //var begInRect = GeometryMethods.IsPointInsideSimplifiedRectangle(start, rect);
            //var endInRect = GeometryMethods.IsPointInsideSimplifiedRectangle(finish, rect);
            //if (begInRect && !endInRect || !begInRect && endInRect)
            //    return new Vector2[0];
            if (rectangles.Length == 0)
                return new Vector2[] { finish };

            var searchRect = new SimplifiedRectangle(start, finish);
            rectangles = rectangles
                .Where(e => GeometryMethods.IsSimplifiedRectanglesInterescting(searchRect, e))
                .ToArray();

            var queue = new Queue<Vector2>();
            queue.Enqueue(start);
            var visited = new HashSet<Vector2> {start};
            var parent = new Dictionary<Vector2, Vector2?>();

            while (queue.Count > 0)
            {
                var current = queue.Dequeue();
                var seg = new Segment(current, finish);

                if (!rectangles.Any(r => IsSegmentIntersectingRectangle(seg, r)))
                {
                    parent[finish] = current;
                    break;
                }

                foreach (var n in GetNeighbors(current, rectangles, visited))
                {
                    parent[n] = current;
                    visited.Add(n);
                    queue.Enqueue(n);
                    // проверка на visited в GetNeighbors - для ускорения
                }
            }

            var result = new LinkedList<Vector2>();
            var a = finish;
            while (parent.ContainsKey(a))
            {
                result.AddFirst(a);
                a = parent[a].Value;
            }

            return result.ToArray();
        }

        private static IEnumerable<Vector2> GetNeighbors(Vector2 point, SimplifiedRectangle[] rectangles, HashSet<Vector2> visited)
        {
            // очень медленно :C

            var result = new List<Vector2>();

            foreach (var rect in rectangles)
            {
                var hasPoint = rect.Vertexes.Contains(point);

                foreach (var v in rect.Vertexes)
                {
                    if (visited.Contains(v)) // для скорости запихал сюда
                        continue;

                    if (hasPoint)
                    {
                        if (v.X.Equal(point.X) && !v.Y.Equal(point.Y) || !v.X.Equal(point.X) && v.Y.Equal(point.Y))
                            result.Add(v);
                    }
                    else
                    {
                        var seg = new Segment(point, v);
                        if (rectangles.Any(r => IsSegmentIntersectingRectangle(seg, r)))
                            continue;

                        result.Add(v);
                    }
                }
            }

            return result;
        }

        private static bool IsSegmentIntersectingRectangle(Segment seg, SimplifiedRectangle rect)
        {
            var intersection =
                GeometryMethods.GetSegmentSimplifiedRectangleIntersection(seg, rect, out var intres, true);

            if (intersection == IntersectionResult.None)
            {
                return false;
            }

            if (intersection == IntersectionResult.Point)
            {
                if (intres.Equals(seg.Begin) || intres.Equals(seg.End))
                    return false;
            }

            if (intersection == IntersectionResult.Points)
            {
                var points = (Vector2[])intres;
                if (seg.Begin.Equals(points[0]) && seg.End.Equals(points[1]) ||
                    seg.Begin.Equals(points[1]) && seg.End.Equals(points[0]))
                    return false;
            }

            return true;
        }
    }
}
