Comments 64
Случай когда отрезок лежит на луче не потеряли?
Сработает на чём-то, вроде такого?
На глаз ту всегда 2-4 пересечения, так что по идее да.
когда-то решал эту задачу. Все оказалось куда сложнее, так как много частных случаев: кольцо, подкова и пр. У меня также были сегменты-дуги, что еще больше затрудняло выполнение. Решение по объему могло бы стать если не дипломной, то курсовой работой точно.
Чисто алгоритмически должно сработать, пускаем луч и считаем число пересечения с ребрами многоугольника, тут куда не пускай везде будет четное количество пересечений. Тут только вопрос реализации и обработки граничных случаев, когда луч попадает в вершину и еще не маловажный вопрос это точности вычислений/погрешности, хотя если не вычислять точную точку пересечения, а сам факт то эту проблему можно избежать.
что повлечет за собой проблемы (одна вершина принадлежит сразу двум
отрезкам, программа засчитает сразу два пересечения), поэтому заранее
добавляется та самая "бесконечно малая"величина к абсциссам вершин многоугольника
Кажется что "прибавлять" бесконечно малые отклонения не лучший вариант. Ведь вся сложность с в случае "попадания" в вершину в выбраном алгоритме определения факта пересечения грани. Чтобы исключить двойное "засчитывание" при попадании в вершину, достаточно проверять не вовпадает ли точка пересечения луча и ребра с одной из вершин многогранника, если сопадает, то просто вычитать 1 из числа пересечений.
можно еще проще. Считать попаданием в начальную точку отрезка, но не считать в конечную. Т.е. для одной из точек условие будет что то типа >= а для второй строго >
Нельзя :)
Во-первых, в реальной жизни полное равенство двух double - штука маловероятная. Собственно, поэтому тут везде дельта.
Во-вторых, а что такое "начало отрезка"?
И пока вы не ответили, спрошу еще: а что мешает иметь два отрезка, заданные как (A, B) и (A, C)?
Можно. Проверка здесь будет только по одной из координат, а не результат какого-то вычисления (которое подвержено ошибкам)
Многоугольник обходится в одну сторону (по или против часовой стрелки). Вот для каждого отрезка одна из точек — начало, вторая — конец. Конец одного отрезка это начало другого
Второй вариант — считать точку с меньшим Х началом, с большим Х концом. Это будет лучше обрабатывать еще один особый случай (внутреннее касание вершины)
Я могу точно сказать что можно потому что такой алгоритм я писал и он работает в проде.
Последний вопрос я не понял
Ну вообще то такой алгоритм не будет корректно различать такой случай: есть три последовательные точки многоугольника (для просто можно рассматривать треугольник) A, B и C. Луч проходит через точку B. Есть два случая: точки A и С лежать по разные стороны луча(линии проходящей через луч) или точки A и С лежат по одну сторону луча. В первом случае луч пересекает границу многоугольника, во втором, нет.
Точка, из которой луч попадает в вершину, может являться результатом каких-то других вычислений. То есть в совсем общем случае я бы не гарантировал совпадения хотя бы одной из координат побитово (хотя в вашем продакшен случае это вполне может быть именно так).
А в случае обхода полигона надо тогда добавить шаг фильтрации, который будет выкидывать отрезки, длина которых сравнима с дельтой.
Про последний вопрос: видимо, тут разница в понимании того, как может быть задан полигон. Вы подразумеваете, что он задается подряд идущими сегментами: (A, B), (B, C), (C, D), ..., (Z, A). Но в общем случае полигон может быть задан как попало: (C, B), (A, B), ..., (A, Z), (D, C).
То что точка является результатом вычислений это неважно. Важно чтобы она была учтена один раз, и в этом случае полуоткрытые отрезки работают.
Полигон это массив точек а не отрезков. В отрезки уже превращаем его мы в алгоритме, и мы можем это сделать аккуратно.
Ну и "второму варианту" на порядок пофиг, а он все равно лучше первого
Нет, правильно — считать нижнюю точку отрезка, а горизонтальные можно тупо игнорировать. Тогда нормально обработаются случаи, когда многоугольник касается луча сверху или снизу вершиной (будет 0 или 2 пересечений). И случай, когда луч проходит через вершину (будет 1 пересечение от верхнего отрезка).
Добалю про "бесконечно малую". Нас в институте на такой фразе сразу обрывали и посылали переделывать курсовик.... Тогда-то и приучили что нет просто малых или просто больших величин - они всегда малы или велики по сравнению с чем-то.
Вы не знаете заранее насколько велики или малы будут координаты точек, соответственно абсолютное значение смещения может либо быть проигнорировано при сложении (координаты имеют порядок 1e+20 или больше), либо может привести к серьезному сдвигу всей фигуры (координаты порядка 1e-8 ).
Минимально тут надо поправить на вычисление относительного сдвига, например 0,00001% от координаты проверяемой точки.
Если слегка поревьювить:
Почему точки отрезка (Segment) мутабельные?
Массив отрезков, в общем случае, полигоном не является.
Портить координаты дельтой, действительно, не хорошо.
Должно быть достаточно ввести некий tolerance для сравнения вещественных чисел.
Ну и само это сравнение вынести в отдельный метод, не размазывая по коду.Кстати, как эта "порча" должа помочь избежать двойного зачета точки, если портятся абсолютно все точки полигона?
В данном случае для пересечения совсем не обязательно считать детерминанты и т.п. — пересечение с лучом параллельным оси можно посчитать проще, и, главное, с меньшим влиянием ошибок точности плавающей запятой.
Тоже давали такую задачу где-то в середине обучения в универе, только это было примерно в 2000-м году и задачу дали не преподаватели, а сотрудники фирмы Esma (картография), которые искали себе джунов. Решил примерно похожим способом на паскале, но с нюансами (с википедией тогда были некоторые проблемки).
В кажестве теста тогда делали "заливку" цветом фигуры по этому алгоритму, наглядно было видно, какие нюансы не учел.
Что задачу давал -- помню, а кому именно -- уже не помню :)
Нас тогда человека три подписалось, уж не помню кто решил, а кто нет, зато помню, что мне там показали свое решение размером в одну или две страницы кода, я тогда был впечатлен и понял, что слишком хорошего мнения о своих тогдашних способностях.
Еще помню там же упоминалась задача вида "как определить в какой последовательности рисовать стены домов на 3д карте".
Вспомнил еще: первое мое решение было вообще на основе подсчета площадей треугольников, но помню косяков и различных условий там было немеряно.
А учли ли в случаи, когда:
Ваш луч из точки наружу пройдет через точку, определяющую границу многоугольника. Тут можно или два раза посчитать, или ноль. Координаты же вещественные?
Ваш луч точно ляжет на ребро между двумя точками, определяющими многоугольник?
Там много нюансов, как минимум прохождений через вершину может быть 4 разных типа: извне вовнутрь, изнутри наружу, изнутри, не покидая фигуру и снаружи не проходя. В общум или куча ифов, или менять подход к этому алгоритму.
Именно. Мне вообще кажется, что тут нужно переходить на квадратную (целочисленную, с точностью до масштаба сетку), точки в узлах, все (наклонные) линии превращаются в последовательности вертикальных и горизонтальных отрезков. Тогда никаких проблем с точностью вычисленией нет. Ну, пересечение луча и отрезка будет интереснее считать (это может быть не точка а отрезок). А, может, можно и наклоны с рациональными тангенсами разрешить? Но как бы тогда и арифметика с произвольной разрядностью не потребовалась?
Если точки многоугольника и искомая точка целые числа то там надо просто математикой выкинуть все операции деления, это возможно, и считать в целых числах. Достаточно просто. Но алгоритм пересечения отрезка с лучом придется переписать. Превращаться в последовательности вертикальных и горизонтальных отрезков не надо.
Если многоугольник задан только точками, то зачастую существует несколько способов его построения, отличающихся порядком соединения точек:
Поэтому получать на входе массив вершин -- так себе идея, нужно требовать сразу отрезки.
нужно требовать сразу отрезки
А затем сразу проверять что они имеют общие "концы"? А если нет?
Если задан массив, то он уже порядочен. Просто нужно прямо сказать что порядок в массиве определяет порядок соединения точек.
А затем сразу проверять что они имеют общие "концы"? А если нет?
Ну да. Это ведь будут просто общие координаты. А если нет -- то нет и многоугольника, и полные исходные данные отсутствуют. Потом придётся ещё проверить, что отрезки не пересекаются.
Если задан массив, то он уже порядочен. Просто нужно прямо сказать что порядок в массиве определяет порядок соединения точек.
Тоже вариант, но почему-то при постановке задачи это было опущено. И проверку на самопересечение ограничивающей ломаной в этом случае тоже нужно делать: в условии не сказано, что многоугольник должен быть простым, но в данном случае лучше ввести это требование, иначе понятие "внутри многоугольника" станет намного труднее определить.
Массив это не множество — массив уже имеет порядок. Массив точек однозначно задает многоугольник.
Для данного конкретного алгоритма самопересечение многоугольника не играет роли.
вопрос к спецам: а почему нельзя разбить многоугольник на треугольники, методом обхода против часовой стрелки, и затем последовательно проверить каждый треугольник?
Треугольник по каким точкам вы хотите строить? От произвольной точки многогранника и 2-м другим? Этот вариант годится для выпукного многогранника, а например для "подковы" уже не подойдёт.
Можно, но это на порядки сложнее. Если многугольник невыпуклый, то его триангулировать — та еще задачка. И дальше проверки на принадлежность треугольнику будут дольше, чем проверка на пересечение с отрезком.
Но есть особый случай, когда похожий на ваш метод — лучше. Если надо быстро определеять принадлежность многих точек к выпуклому многоугольнику. Тогда надо разбить многоугольник на трапеции горизонтальными линиями. Потом для каждого запроса бинпоиском найти тот срез, к которому точка может относится и дальше проверить, что она лежит между левой и правой границей трапеции.
А есть тест кейсы?
Я б поупражнялся бы)
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;
}
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;
}
Я бы последовательно отсекал от многоугольника треугольники, которым точно не принадлежит проверяемая точка, сведя задачу к определению принадлежности точки последнему оставшемуся треугольнику.
Превратили O(N) задачу в O(N^3) потому что найти треугольник в многоугольнике это O(N^2) в худшем случае для простых алгоритмов. Есть сложные (сложнее чем определение точки в многоугольнике) которые побыстрее на больших многоугольниках но все равно получается больше чем O(N^2)
Искать не надо. Треугольник - это любые три последовательные точки в массиве.
а как определять, что площадь этого треугольника принадлежит фигуре, а не вне ее?
Определять не надо. Не могу придумать варианта, где это было бы важно. Важно, чтобы проверяемая точка в любом случае не находилась на этой площади или на стороне треугольника. Иначе, пропускаем этот треугольник и переходим к следующему. Может оказаться, в конце останется четырёхугольник с точкой ровно на пересечении диагоналей - надо отследить, чтобы не зациклиться.
Вы должны доказать что это работает, а не "не могу придумать варианта".
Вон возьмите пример из правой верхней картинки статьи, только точка находится "между ног" а треугольник вы взяли из трех нижних точек. Точка в нем лежит, а в исходном многоугольнике — нет.
Вижу, что вы не поняли алгоритм. Перечитайте внимательнее. Я же про это как раз и написал. Аж два раза. Если точка лежит в треугольнике — мы этот треугольник не трогаем вообще, поскольку не знаем, принадлежит ли он (вместе с точкой) многоугольнику или нет. Но если точки там нет, то нам без разницы, уменьшаем мы площадь многоугольника или увеличиваем, удалив этот треугольник, — точка от этого не перескачет границу многоугольника и не перестанет принадлежать или не принадлежать ему.
Но многоугольник от этого может перестать быть "хорошим" — в нем могут появиться самопересечения. А значит в конце можно остаться не с одним треугольником, а с рандомной кашей из намотаных вокруг точки вершин.
Ну вот представьте многоугольник в виде буквы М с соединением снизу. Удалив треугольник из двух нижних точек и одной верхней мы получим самопересечение.
Возможно в конце можно будет сделать какой то вывод. Но это надо бы доказать. И в любом случае получится больше чем O(N) из-за того что "если с треугольником не получилось — переходим к следующему". Насколько больше — тоже как-то нетривиально посчитать.
Та же история. Мы не можем ничего намотать вокруг точки по этому алгоритму. Но, действительно, должны выделить случаи, когда вокруг точки намотано изначально (как в звезде с точкой по центру), и сделать вывод о принадлежности точки многоугольнику при принадлежности её всем оставшимся треугольникам.
В общем, пока никто не показал, как конкретно алгоритм может не сработать. Хотя, большие сомнения остаются, поскольку нетщательный гуглёж не находит ничего похожего.
Насчёт O(N) надо смотреть. Вроде бы не должно быть сильно больше — нам же достаточно каждый треугольник просчитать только один раз, а пустые треугольники тут же удаляются.
Если полигон выпуклый то триангулизация тривиальна. Но для вогнутого все сложно. Тут скорее BSP подход был бы эффективнее...
В случае выпуклого многоугольника исходная задача становится супер простой — проверить что точка лежит с одной стороны от прямых созданных из всех отрезков (например слева от всех отрезков)
Однако в задаче очевидно подразумевается произвольный многоугольник, что и нарисовано на картинках В произвольном многоугольнике треугольник составленный из трех последовательной точки может ему не принадлежать полностью или частично.
Небольшой читинг. Несколько лет назад понадобилось инжектировать подобную задачу в ARM-бинарник. Само собой был нужен максимально эффективный и простой алгоритм,нагуглил этот:
A winding Number and Point-in-Polygon Algorythm, David G. Alciatore, Colorado State University (скан, PDF)
Работает даже с некоторыми самопересекающимися полигонами (в документе есть пример пятиконечной звезды). Вкратце - считается количество оборотов, которое линия сделала вокруг указанной точки, т.е. можно нарисовать спираль, вернуться обратно, ткнуть точку - и алгоритм укажет попали или нет.
После некоторых оптимизаций удалось полностью избавиться от деления и обойтись двумя операциями умножения на цикл (функция DotProduct). Фокус в том, что в основном интересуют знаки операций, а не их значения. Пример подобных оптимизаций в комментарии @kovserg выше.
Проверку на нахождение точки точно на линии я тогда не рассматривал, ИМО это отдельный случай.
Согласен с автором что задача весьма не тривиальна.
Для себя в свое время решил, что лучше уйти от Float вычислений на Int.
Если интерессно нашел свой репозиторий с этим участком кода, как раз на C#
https://github.com/iShapeUnity/Clipper/blob/master/Runtime/iShape/Clipper/Util/PolygonExt.cs
Можно площадь всех треугольников посчитать с этоц точкой, и без нее. И сравнить что больше.
На олимпиаде была подобная задача - нужно было на SQL решать. Вот тут было веселье)
Казалось бы, это задача на углы, а не на лучи-отрезки. Если просуммировать все углы, под которыми видно стороны многоугольника, для внешней точки должен получиться ноль, для внутренней - 2*Math.PI.
В .NET есть стандартные средства для решения подобной задачи System.Drawing.Graphics.IsVisible
Еще можно попробовать таким образом: представить многоугольник в виде нескольких треугольников, затем проверить принадлежность точки каждому из треугольников.
Как проверить, принадлежит ли точка треугольнику: проводим в нее из всех вершин прямые, получая теперь еще 3 треугольника. Сумма их площадей должна совпадать с площадью большого треугольника. Если не совпадает, то точка лежит вне его. Для расчета площадей можно использовать векторное произведение векторов или формулу Герона
Лично я когда ещё был школьником всегда использовал метод учёта оборотов, по-моему он гибче и под микроусловия в олимпиадках подстроиться проще (и лично мне чуть более понятно): Самопересечения не входят? - Не вопрос - посчитаем сколько оборотов делает, а если входят - просто смотрим близка ли сумма к нулю
Если площадь небольшая - Создаем массив пикселей, у каждой координаты, - проверяем принадлежит ли точка массиву. а если в процессе создания провера идет, можем сократить до совпадения.
Если плащадь большая создаем массив не пикселей, а массив фигур с координатами, ищем к какому принадлежит точка. если принадлежит, выбранный масив бъем на пиксельные точки и далее см. пункт 1
Не программист. Но можно сделать не через луч, а через копиравание точки вокру себя. Если точка не сможет скопироватся из-за отсутсвтия места, то пространство замкнутое, посколько она упрется в свои же копии и стенку. В случае если точка не упирается в стенку, то соседние точки и последующие должны образовывать круг, если круг замкнулся, то пространство открытое было, но тут нужно добавить условия с объемами и цветами. Допустим круг замкнулся и если в нем есть черные точки-да, пространство открытое, если круг замкнулся и в нём нет черных точек во всём объеме-не канает. По такому алгоритму не будет исключений в сложности геометрии фигуры.
Интересно, это в условии задачи оговорено явно, что координаты вещественные или автор так решил?
MaxInt может оказаться меньше координат полигона
Просто в теории, тяжело на деле