Небольшая предыстория
Учусь на втором курсе СПО, квалификация программист. Преподаватель по программированию (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<Segment>();
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.
Заключение
Я удивлен, что смог осилить эту задачу, даже несмотря на всю свою искреннюю ненависть к координатной плоскости. Тем не менее я рад, что смог ее решить, преодолеть все математические препятствия на всем этом пути. Хочу поблагодарить своего преподавателя за подобный опыт.
Кроме того, надеюсь, что статья была полезна и другим начинающим программистам, вроде меня, решающим такие типовые (но от этого не менее интересные) задачи.
Комментарии (63)
MeOwn
13.01.2022 11:06+2Сработает на чём-то, вроде такого?
robesper
13.01.2022 11:19+1когда-то решал эту задачу. Все оказалось куда сложнее, так как много частных случаев: кольцо, подкова и пр. У меня также были сегменты-дуги, что еще больше затрудняло выполнение. Решение по объему могло бы стать если не дипломной, то курсовой работой точно.
abutorin
13.01.2022 11:54+1Общий алгоритм простой. Все сводится к определению количества пересечений с гранями. Для каждого вида грани (прямая, кривая) просто нужно реализовать свою процедуру опредения количества пересечений с лучом.
robesper
14.01.2022 08:40-1да, алгоритм простой, но не отрабатывает некоторых случаев. Я общался с профессиональным математиком. Он знал эту и несколько других методик (сейчас не вспомню каких). Ни одна не покрывала 100% случаев.
ViacheslavNk
13.01.2022 15:47Чисто алгоритмически должно сработать, пускаем луч и считаем число пересечения с ребрами многоугольника, тут куда не пускай везде будет четное количество пересечений. Тут только вопрос реализации и обработки граничных случаев, когда луч попадает в вершину и еще не маловажный вопрос это точности вычислений/погрешности, хотя если не вычислять точную точку пересечения, а сам факт то эту проблему можно избежать.
abutorin
13.01.2022 11:26+6что повлечет за собой проблемы (одна вершина принадлежит сразу двум
отрезкам, программа засчитает сразу два пересечения), поэтому заранее
добавляется та самая "бесконечно малая"
величина к абсциссам вершин многоугольникаКажется что "прибавлять" бесконечно малые отклонения не лучший вариант. Ведь вся сложность с в случае "попадания" в вершину в выбраном алгоритме определения факта пересечения грани. Чтобы исключить двойное "засчитывание" при попадании в вершину, достаточно проверять не вовпадает ли точка пересечения луча и ребра с одной из вершин многогранника, если сопадает, то просто вычитать 1 из числа пересечений.
ShadowTheAge
13.01.2022 11:47+4можно еще проще. Считать попаданием в начальную точку отрезка, но не считать в конечную. Т.е. для одной из точек условие будет что то типа >= а для второй строго >
t13s
13.01.2022 12:01Нельзя :)
Во-первых, в реальной жизни полное равенство двух double - штука маловероятная. Собственно, поэтому тут везде дельта.
Во-вторых, а что такое "начало отрезка"?
И пока вы не ответили, спрошу еще: а что мешает иметь два отрезка, заданные как (A, B) и (A, C)?ShadowTheAge
13.01.2022 12:14+1Можно. Проверка здесь будет только по одной из координат, а не результат какого-то вычисления (которое подвержено ошибкам)
Многоугольник обходится в одну сторону (по или против часовой стрелки). Вот для каждого отрезка одна из точек — начало, вторая — конец. Конец одного отрезка это начало другого
Второй вариант — считать точку с меньшим Х началом, с большим Х концом. Это будет лучше обрабатывать еще один особый случай (внутреннее касание вершины)
Я могу точно сказать что можно потому что такой алгоритм я писал и он работает в проде.
Последний вопрос я не понял
avdx
13.01.2022 12:45Ну вообще то такой алгоритм не будет корректно различать такой случай: есть три последовательные точки многоугольника (для просто можно рассматривать треугольник) A, B и C. Луч проходит через точку B. Есть два случая: точки A и С лежать по разные стороны луча(линии проходящей через луч) или точки A и С лежат по одну сторону луча. В первом случае луч пересекает границу многоугольника, во втором, нет.
ShadowTheAge
13.01.2022 13:48+1Поэтому и "второй вариант".
avdx
13.01.2022 14:27+1Из описания сначала не понял суть "второго варианта". Ну так да, он будет правильно обрабатывать. Наверное это самый простой и эффективный способ корректной реализации данного алгоритма.
t13s
13.01.2022 12:54Точка, из которой луч попадает в вершину, может являться результатом каких-то других вычислений. То есть в совсем общем случае я бы не гарантировал совпадения хотя бы одной из координат побитово (хотя в вашем продакшен случае это вполне может быть именно так).
А в случае обхода полигона надо тогда добавить шаг фильтрации, который будет выкидывать отрезки, длина которых сравнима с дельтой.
Про последний вопрос: видимо, тут разница в понимании того, как может быть задан полигон. Вы подразумеваете, что он задается подряд идущими сегментами: (A, B), (B, C), (C, D), ..., (Z, A). Но в общем случае полигон может быть задан как попало: (C, B), (A, B), ..., (A, Z), (D, C).
ShadowTheAge
13.01.2022 13:49+1То что точка является результатом вычислений это неважно. Важно чтобы она была учтена один раз, и в этом случае полуоткрытые отрезки работают.
Полигон это массив точек а не отрезков. В отрезки уже превращаем его мы в алгоритме, и мы можем это сделать аккуратно.
Ну и "второму варианту" на порядок пофиг, а он все равно лучше первого
wataru
13.01.2022 18:00Нет, правильно — считать нижнюю точку отрезка, а горизонтальные можно тупо игнорировать. Тогда нормально обработаются случаи, когда многоугольник касается луча сверху или снизу вершиной (будет 0 или 2 пересечений). И случай, когда луч проходит через вершину (будет 1 пересечение от верхнего отрезка).
ShadowTheAge
13.01.2022 19:55В статье выпускаемый луч вертикальный поэтому правильно считать по Х а не по У
SlFed
13.01.2022 13:33+3Добалю про "бесконечно малую". Нас в институте на такой фразе сразу обрывали и посылали переделывать курсовик.... Тогда-то и приучили что нет просто малых или просто больших величин - они всегда малы или велики по сравнению с чем-то.
Вы не знаете заранее насколько велики или малы будут координаты точек, соответственно абсолютное значение смещения может либо быть проигнорировано при сложении (координаты имеют порядок 1e+20 или больше), либо может привести к серьезному сдвигу всей фигуры (координаты порядка 1e-8 ).
Минимально тут надо поправить на вычисление относительного сдвига, например 0,00001% от координаты проверяемой точки.
t13s
13.01.2022 11:46+3Если слегка поревьювить:
Почему точки отрезка (Segment) мутабельные?
Массив отрезков, в общем случае, полигоном не является.
Портить координаты дельтой, действительно, не хорошо.
Должно быть достаточно ввести некий tolerance для сравнения вещественных чисел.
Ну и само это сравнение вынести в отдельный метод, не размазывая по коду.Кстати, как эта "порча" должа помочь избежать двойного зачета точки, если портятся абсолютно все точки полигона?
ShadowTheAge
13.01.2022 11:49+1В данном случае для пересечения совсем не обязательно считать детерминанты и т.п. — пересечение с лучом параллельным оси можно посчитать проще, и, главное, с меньшим влиянием ошибок точности плавающей запятой.
Exclipt
13.01.2022 11:53Тоже давали такую задачу где-то в середине обучения в универе, только это было примерно в 2000-м году и задачу дали не преподаватели, а сотрудники фирмы Esma (картография), которые искали себе джунов. Решил примерно похожим способом на паскале, но с нюансами (с википедией тогда были некоторые проблемки).
В кажестве теста тогда делали "заливку" цветом фигуры по этому алгоритму, наглядно было видно, какие нюансы не учел.
KongEnGe
13.01.2022 12:02+1Что задачу давал -- помню, а кому именно -- уже не помню :)
Exclipt
13.01.2022 12:21Нас тогда человека три подписалось, уж не помню кто решил, а кто нет, зато помню, что мне там показали свое решение размером в одну или две страницы кода, я тогда был впечатлен и понял, что слишком хорошего мнения о своих тогдашних способностях.
Еще помню там же упоминалась задача вида "как определить в какой последовательности рисовать стены домов на 3д карте".
Вспомнил еще: первое мое решение было вообще на основе подсчета площадей треугольников, но помню косяков и различных условий там было немеряно.
Andy_U
13.01.2022 11:59А учли ли в случаи, когда:
Ваш луч из точки наружу пройдет через точку, определяющую границу многоугольника. Тут можно или два раза посчитать, или ноль. Координаты же вещественные?
Ваш луч точно ляжет на ребро между двумя точками, определяющими многоугольник?
Exclipt
13.01.2022 12:33Там много нюансов, как минимум прохождений через вершину может быть 4 разных типа: извне вовнутрь, изнутри наружу, изнутри, не покидая фигуру и снаружи не проходя. В общум или куча ифов, или менять подход к этому алгоритму.
Andy_U
13.01.2022 15:57Именно. Мне вообще кажется, что тут нужно переходить на квадратную (целочисленную, с точностью до масштаба сетку), точки в узлах, все (наклонные) линии превращаются в последовательности вертикальных и горизонтальных отрезков. Тогда никаких проблем с точностью вычисленией нет. Ну, пересечение луча и отрезка будет интереснее считать (это может быть не точка а отрезок). А, может, можно и наклоны с рациональными тангенсами разрешить? Но как бы тогда и арифметика с произвольной разрядностью не потребовалась?
ShadowTheAge
13.01.2022 17:24Если точки многоугольника и искомая точка целые числа то там надо просто математикой выкинуть все операции деления, это возможно, и считать в целых числах. Достаточно просто. Но алгоритм пересечения отрезка с лучом придется переписать. Превращаться в последовательности вертикальных и горизонтальных отрезков не надо.
Gutt
13.01.2022 13:55Если многоугольник задан только точками, то зачастую существует несколько способов его построения, отличающихся порядком соединения точек:
Поэтому получать на входе массив вершин -- так себе идея, нужно требовать сразу отрезки.
abutorin
13.01.2022 14:03+3нужно требовать сразу отрезки
А затем сразу проверять что они имеют общие "концы"? А если нет?
Если задан массив, то он уже порядочен. Просто нужно прямо сказать что порядок в массиве определяет порядок соединения точек.
Gutt
13.01.2022 14:28+1А затем сразу проверять что они имеют общие "концы"? А если нет?
Ну да. Это ведь будут просто общие координаты. А если нет -- то нет и многоугольника, и полные исходные данные отсутствуют. Потом придётся ещё проверить, что отрезки не пересекаются.
Если задан массив, то он уже порядочен. Просто нужно прямо сказать что порядок в массиве определяет порядок соединения точек.
Тоже вариант, но почему-то при постановке задачи это было опущено. И проверку на самопересечение ограничивающей ломаной в этом случае тоже нужно делать: в условии не сказано, что многоугольник должен быть простым, но в данном случае лучше ввести это требование, иначе понятие "внутри многоугольника" станет намного труднее определить.
abutorin
13.01.2022 14:53"внутри многоугольника" станет намного труднее определить
Тут весь вопрос как поступать с самопересекающимся многогранником. Но в любом случае это просто добавляет "предварительный" этап приведения его к нужному виду. Дальше алгоритм остаёться прежним.
ShadowTheAge
13.01.2022 15:40+3Массив это не множество — массив уже имеет порядок. Массив точек однозначно задает многоугольник.
Для данного конкретного алгоритма самопересечение многоугольника не играет роли.
pyur
13.01.2022 14:26вопрос к спецам: а почему нельзя разбить многоугольник на треугольники, методом обхода против часовой стрелки, и затем последовательно проверить каждый треугольник?
abutorin
13.01.2022 14:50Треугольник по каким точкам вы хотите строить? От произвольной точки многогранника и 2-м другим? Этот вариант годится для выпукного многогранника, а например для "подковы" уже не подойдёт.
wataru
13.01.2022 18:06Можно, но это на порядки сложнее. Если многугольник невыпуклый, то его триангулировать — та еще задачка. И дальше проверки на принадлежность треугольнику будут дольше, чем проверка на пересечение с отрезком.
Но есть особый случай, когда похожий на ваш метод — лучше. Если надо быстро определеять принадлежность многих точек к выпуклому многоугольнику. Тогда надо разбить многоугольник на трапеции горизонтальными линиями. Потом для каждого запроса бинпоиском найти тот срез, к которому точка может относится и дальше проверить, что она лежит между левой и правой границей трапеции.
kovserg
13.01.2022 14:58А нельзя было как-то проще сделать?
bool inside(Point t, Point[] p) { double d; int c=0, n=p.Length; for(int i=0;i<n;i++) { int a=i, b=i+1; if(b>=n) b-=n; if (p[a].y>p[b].y) { a=b; b=i; } if ((p[a].y<=t.y && t.y<=p[b].y)) { if (p[a].y!=p[b].y) { d=(p[a].x-p[b].x)*(t.y-p[a].y)-(p[a].y-p[b].y)*(t.x-p[a].x); if (d==0) { c=1; break; } if (d<0) c++; } } } return (c&1)==1; }kovserg
13.01.2022 18:40+1Исправленый вариант
bool inside(Point t, Point[] p) { double d; int c=0, n=p.Length; for(int i=0;i<n;i++) { int a=i, b=i+1; if(b>=n) b-=n; if (p[a].y>p[b].y) { a=b; b=i; } if (p[a].y<=t.y && t.y<=p[b].y) { if (p[a].y==p[b].y) { if ((p[a].x-t.x)*(p[b].x-t.x)<=0) { c=1; break; } } else { d=(p[a].x-p[b].x)*(t.y-p[a].y)-(p[a].y-p[b].y)*(t.x-p[a].x); if (d==0) { c=1; break; } if (d<0) c++; } } } return (c&1)==1; }
hfinn
13.01.2022 15:14+1Я бы последовательно отсекал от многоугольника треугольники, которым точно не принадлежит проверяемая точка, сведя задачу к определению принадлежности точки последнему оставшемуся треугольнику.
ShadowTheAge
13.01.2022 15:30+4Превратили O(N) задачу в O(N^3) потому что найти треугольник в многоугольнике это O(N^2) в худшем случае для простых алгоритмов. Есть сложные (сложнее чем определение точки в многоугольнике) которые побыстрее на больших многоугольниках но все равно получается больше чем O(N^2)
hfinn
13.01.2022 15:47Искать не надо. Треугольник - это любые три последовательные точки в массиве.
Exclipt
13.01.2022 16:07+1а как определять, что площадь этого треугольника принадлежит фигуре, а не вне ее?
hfinn
13.01.2022 18:14Определять не надо. Не могу придумать варианта, где это было бы важно. Важно, чтобы проверяемая точка в любом случае не находилась на этой площади или на стороне треугольника. Иначе, пропускаем этот треугольник и переходим к следующему. Может оказаться, в конце останется четырёхугольник с точкой ровно на пересечении диагоналей - надо отследить, чтобы не зациклиться.
ShadowTheAge
13.01.2022 19:58+2Вы должны доказать что это работает, а не "не могу придумать варианта".
Вон возьмите пример из правой верхней картинки статьи, только точка находится "между ног" а треугольник вы взяли из трех нижних точек. Точка в нем лежит, а в исходном многоугольнике — нет.
hfinn
14.01.2022 11:52Вижу, что вы не поняли алгоритм. Перечитайте внимательнее. Я же про это как раз и написал. Аж два раза. Если точка лежит в треугольнике — мы этот треугольник не трогаем вообще, поскольку не знаем, принадлежит ли он (вместе с точкой) многоугольнику или нет. Но если точки там нет, то нам без разницы, уменьшаем мы площадь многоугольника или увеличиваем, удалив этот треугольник, — точка от этого не перескачет границу многоугольника и не перестанет принадлежать или не принадлежать ему.
ShadowTheAge
14.01.2022 23:26Но многоугольник от этого может перестать быть "хорошим" — в нем могут появиться самопересечения. А значит в конце можно остаться не с одним треугольником, а с рандомной кашей из намотаных вокруг точки вершин.
Ну вот представьте многоугольник в виде буквы М с соединением снизу. Удалив треугольник из двух нижних точек и одной верхней мы получим самопересечение.
Возможно в конце можно будет сделать какой то вывод. Но это надо бы доказать. И в любом случае получится больше чем O(N) из-за того что "если с треугольником не получилось — переходим к следующему". Насколько больше — тоже как-то нетривиально посчитать.
hfinn
15.01.2022 13:32Та же история. Мы не можем ничего намотать вокруг точки по этому алгоритму. Но, действительно, должны выделить случаи, когда вокруг точки намотано изначально (как в звезде с точкой по центру), и сделать вывод о принадлежности точки многоугольнику при принадлежности её всем оставшимся треугольникам.
В общем, пока никто не показал, как конкретно алгоритм может не сработать. Хотя, большие сомнения остаются, поскольку нетщательный гуглёж не находит ничего похожего.
Насчёт O(N) надо смотреть. Вроде бы не должно быть сильно больше — нам же достаточно каждый треугольник просчитать только один раз, а пустые треугольники тут же удаляются.
DimPal
13.01.2022 16:28Если полигон выпуклый то триангулизация тривиальна. Но для вогнутого все сложно. Тут скорее BSP подход был бы эффективнее...
ShadowTheAge
13.01.2022 17:18В случае выпуклого многоугольника исходная задача становится супер простой — проверить что точка лежит с одной стороны от прямых созданных из всех отрезков (например слева от всех отрезков)
Однако в задаче очевидно подразумевается произвольный многоугольник, что и нарисовано на картинках В произвольном многоугольнике треугольник составленный из трех последовательной точки может ему не принадлежать полностью или частично.
chnav
13.01.2022 19:00+2Небольшой читинг. Несколько лет назад понадобилось инжектировать подобную задачу в ARM-бинарник. Само собой был нужен максимально эффективный и простой алгоритм,нагуглил этот:
A winding Number and Point-in-Polygon Algorythm, David G. Alciatore, Colorado State University (скан, PDF)
Работает даже с некоторыми самопересекающимися полигонами (в документе есть пример пятиконечной звезды). Вкратце - считается количество оборотов, которое линия сделала вокруг указанной точки, т.е. можно нарисовать спираль, вернуться обратно, ткнуть точку - и алгоритм укажет попали или нет.
После некоторых оптимизаций удалось полностью избавиться от деления и обойтись двумя операциями умножения на цикл (функция DotProduct). Фокус в том, что в основном интересуют знаки операций, а не их значения. Пример подобных оптимизаций в комментарии @kovserg выше.
Проверку на нахождение точки точно на линии я тогда не рассматривал, ИМО это отдельный случай.
chnav
13.01.2022 20:10...а может и не отдельный, если анализировать DotProduct на ноль... детально не помню...
Nail_S
13.01.2022 20:35Согласен с автором что задача весьма не тривиальна.
Для себя в свое время решил, что лучше уйти от Float вычислений на Int.
Если интерессно нашел свой репозиторий с этим участком кода, как раз на C#
https://github.com/iShapeUnity/Clipper/blob/master/Runtime/iShape/Clipper/Util/PolygonExt.cs
skiedr
13.01.2022 22:37Можно площадь всех треугольников посчитать с этоц точкой, и без нее. И сравнить что больше.
GooG2e
14.01.2022 10:25На олимпиаде была подобная задача - нужно было на SQL решать. Вот тут было веселье)
Lyova5
14.01.2022 19:00Казалось бы, это задача на углы, а не на лучи-отрезки. Если просуммировать все углы, под которыми видно стороны многоугольника, для внешней точки должен получиться ноль, для внутренней - 2*Math.PI.
AntZ_RU
14.01.2022 19:00В .NET есть стандартные средства для решения подобной задачи System.Drawing.Graphics.IsVisible
RegressX
14.01.2022 19:00Еще можно попробовать таким образом: представить многоугольник в виде нескольких треугольников, затем проверить принадлежность точки каждому из треугольников.
Как проверить, принадлежит ли точка треугольнику: проводим в нее из всех вершин прямые, получая теперь еще 3 треугольника. Сумма их площадей должна совпадать с площадью большого треугольника. Если не совпадает, то точка лежит вне его. Для расчета площадей можно использовать векторное произведение векторов или формулу Герона
Vitya_Nikolayev
14.01.2022 19:01Лично я когда ещё был школьником всегда использовал метод учёта оборотов, по-моему он гибче и под микроусловия в олимпиадках подстроиться проще (и лично мне чуть более понятно): Самопересечения не входят? - Не вопрос - посчитаем сколько оборотов делает, а если входят - просто смотрим близка ли сумма к нулю
VladPavlushin
14.01.2022 19:01Если площадь небольшая - Создаем массив пикселей, у каждой координаты, - проверяем принадлежит ли точка массиву. а если в процессе создания провера идет, можем сократить до совпадения.
Если плащадь большая создаем массив не пикселей, а массив фигур с координатами, ищем к какому принадлежит точка. если принадлежит, выбранный масив бъем на пиксельные точки и далее см. пункт 1
Kyselov1
14.01.2022 19:01Не программист. Но можно сделать не через луч, а через копиравание точки вокру себя. Если точка не сможет скопироватся из-за отсутсвтия места, то пространство замкнутое, посколько она упрется в свои же копии и стенку. В случае если точка не упирается в стенку, то соседние точки и последующие должны образовывать круг, если круг замкнулся, то пространство открытое было, но тут нужно добавить условия с объемами и цветами. Допустим круг замкнулся и если в нем есть черные точки-да, пространство открытое, если круг замкнулся и в нём нет черных точек во всём объеме-не канает. По такому алгоритму не будет исключений в сложности геометрии фигуры.
oleg1977
15.01.2022 03:42Интересно, это в условии задачи оговорено явно, что координаты вещественные или автор так решил?
FD4A
Случай когда отрезок лежит на луче не потеряли?