Просто в теории, тяжело на деле
Небольшая предыстроия
Учусь на втором курсе СПО, квалификация программист. Преподаватель по программированию (C#) дал на новогодние каникулы эту задачку. Решил написать статью с подробным описанием, так как многие из моей параллели её не «выкупили».
Условие
Дана некоторая точка на координатной плоскости, затем некоторое количество точек, описывающих многоугольник. Разработать функцию IsInside, которая определит, находится ли введеная точка внутри многоугольника.
Условия разработки
Так как обучение проходит только на 2 курсе, использовать можно только пройденные темы, которые включают в себя все базовые конструкции, а также структуры «коробки» для данных.
Перед написанием кода
Как бы я не ненавидел работать с точками в координатах, использовать готовые формулы я не решился — так просто напросто нечестно и неинтересно. Поэтому в поисках методов решения задачи я наткнулся на самый простой и принялся за его реализацию: Учет числа пересечений.
Непосредственно код
Для работы с точками на плоскости хорошо было бы сделать некоторую сущность, описывающую точку:
struct Point
{
public readonly double X;
public readonly double Y;
public Point(double x, double y)
{
X = x;
Y = y;
}
}Дальше в Main осуществляется обработка ввода. В результате получается искомая точка для проверки и массив точек, образующих многоугольник.
Я посчитал, что удобно представить многоугольник как массив отрезков, а потом просто искать между ними пересечения с лучом, отправленным из точки куда-либо (в моей реализации луч летит вверх параллельно 
Для этого следует реализовать структуру отрезка:
struct Segment
{
public Point P1;
public Point P2;
private double Length =>
Math.Sqrt(Math.Pow(P2.X - P1.X, 2) + Math.Pow(P2.Y - P1.Y, 2));
public Segment(Point p1, Point p2)
{
P1 = p1;
P2 = p2;
}
}Тогда еще необходима функция для построения многоугольника из полученного ранее массива точек:
private static Segment[] CreatePolygon(Point[] points)
{
var polygon = new List();
for (int i = 0; i < points.Length - 1; ++i)
{
polygon.Add(new Segment(
new Point(points[i].X + 1e-7, points[i].Y),
new Point(points[i + 1].X + 1e-7, points[i + 1].Y)));
}
polygon.Add(new Segment(new Point(points[0].X + 1e-7, points[0].Y),
new Point(points[points.Length - 1].X + 1e-7,
points[points.Length - 1].Y)));
return polygon.ToArray();
} Второй абзац статьи на Вики выбранной в качестве метода для решения подсказывает, что в будущем поджидает проблема того, что луч может проходить через вершины многоугольника, что повлечет за собой проблемы (одна вершина принадлежит сразу двум отрезкам, программа засчитает сразу два пересечения), поэтому заранее добавляется та самая «бесконечно малая» 
величина к абсциссам вершин многоугольника (так как луч пойдет вертикально, то малый сдвиг по оси 
сможет гарантировать, что луч встретит на своем пути именно ребро, а не вершину).
Луч, улетающий в бесконечность в рамках этой программы можно реализовать, как отрезок с началом в нужной точке и с концом в точке 
Напишем основу для функции, которую от нас требуется написать:
public static bool IsInside(Point p, Segment[] polygon)
{
// Vertical line towards positive Y (x = p.X, y >= p.Y)
Segment verticalSegment = new Segment(p, new Point(p.X, int.MaxValue));
int intersectionsCount = 0;
foreach (var segment in polygon)
{
}
return intersectionsCount % 2 != 0;
}Внутри цикла необходимо реализовать проверку пересечения некоторого отрезка многоугольника с нашим лучом. Для этого следует реализовать метод Intersects структуры Segment. Именно на этом моменте начинаются проблемы у людей, которые плохо понимают в математике и в координатой плоскости (например, как я).
Условие пересчения двух отрезков
Пусть у нас есть два отрезка — s1 и s2. По двум точкам каждого из них мы можем получить уравнение прямой вида 
.
Если две эти прямые параллельны 
, то и точки пересечения у них не будет, ровно как и у отрезков. В ином случае найти точку пересечения можно, решив систему уравнений
Тогда если эта точка с координатами 
принадлежит обоим отрезкам (сумма расстояний от точки до концов отрезка равна длине самого отрезка) s1 и s2, то эти отрезки пересекаются.
Дальше к написанию кода
Для начала необходимо реализовать структуру прямой вида 
, а также метод поиска точки пересечения двух таких прямых:
struct Line
{
public readonly double A;
public readonly double B;
public readonly double C;
public Line(Segment s)
{
var p1 = s.P1;
var p2 = s.P2;
A = p2.Y - p1.Y;
B = -(p2.X - p1.X);
C = A * -p1.X + B * -p1.Y;
}
public Point FindIntersectionPoint(Line line)
{
double determinant = A * line.B - line.A * B;
double x = -(C * line.B - line.C * B) / determinant;
double y = -(A * line.C - line.A * C) / determinant;
return new Point(x, y);
}
}Внутри структуры Segment необходимо написать метод проверки пересечения отрезков, а также метод, проверяющий принадлежность точки отрезку:
public bool Intersects(Segment segment)
{
var line1 = new Line(this);
var line2 = new Line(segment);
// if lines are not parallel
if (Math.Abs(line1.A * line2.B - line1.B * line2.A) > 1e-9)
{
var intersectionPoint = line1.FindIntersectionPoint(line2);
return this.ContainsPoint(intersectionPoint) &&
segment.ContainsPoint(intersectionPoint);
}
return false;
}
public bool ContainsPoint(Point p)
{
return Math.Abs(p.DistanceToPoint(P1) + p.DistanceToPoint(P2) -
Length) < 1e-9;
}Почти финал
Все, что осталось сделать — реализовать тело цикла в искомом методе IsInside:
foreach (var segment in polygon)
{
if (segment.ContainsPoint(p))
return false;
if (segment.Intersects(verticalSegment))
intersectionsCount++;
}Первое условие зависит от задачи — в нем проверяется, принадлежит ли искомая точка какому-то из отрезков многоугольника. В каких-то случаях необходимо возвращать true, в каких-то false. Для себя я решил, что точка на границе многоугольника не лежит непосредственно в многоугольнике, поэтому возвращаю false.
Заключение
Я удивлен, что смог осилить эту задачу, даже несмотря на всю свою искреннюю ненависть к координатной плоскости. Тем не менее я рад, что смог ее решить, преодолеть все математические препятствия на всем этом пути. Хочу поблагодарить своего преподавателя за подобный опыт.
Кроме того, надеюсь, что статья была полезна и другим начинающим программистам, вроде меня, решающим такие типовые (но от этого не менее интересные) задачи.
