Помогите, пожалуйста, с данным алгоритмом. Нужно чтобы работал не только с выпуклыми. Если можно пример кода или псевдокод.
-
3Проверять принадлежность 2-м треугольникам?)– Sh4dow25 дек 2011 в 17:27
-
А ведь правда.. :) Буду пробовать...– ilayer25 дек 2011 в 19:30
-
Я все-таки советую пользовать вариант из ответа) В оем еще для определения угла всякие косинусы для каждых 3 точек искать.– Sh4dow25 дек 2011 в 19:32
-
Как раз вариант с треугольниками проще в реализации. Проверка на попадание точки в треугольник это подсчёт 2 векторных произведений и сравнение их Z координат по знаку (т.к. треугольники лежат в плоскости): blackpawn.com/texts/pointinpoly/default.html– AlexeyM25 дек 2011 в 20:56
-
Есть кое-что посвежее: то же для многоугольника– Yuri Negometyanov18 ноя 2015 в 0:57
1 ответ
Проводим луч из проверяемой точки в любую бесконечно удаленную.
Для каждого ребра проверяем, пересекает ли данное ребро этот луч.
Если количество ребер которое луч пересекает четное, то точка вне многоугольника.
Если нечетное, то внутри.
Единственное, если данный луч проходит через пересечение соседних ребер, то определить нельзя или как то с бубном попытаться это сделать... Наверняка выход из этой ситуации есть.
PS @Sh4dow ваше предложение будет работать, только для выпуклого многоугольника. Если я неправильно понял, то пожалуйста объясните :)
UPD: вот реализация hardfire.far.ru
-
Вводим точки по часовой стрелке. У невыпуклого 4-хугольника один угол из четырех будет отрицательным или больше 180 (смотря как считать). Если такой есть - берем эту точку за первую, если нет - любую. Строим 2 треугольника: (1, 2, 3) и (1, 3, 4). Если точка принадлежит любому из них - принадлежит и 4-хугольнику. Хотя ваш вариант, скорее всего, полегче в плане расхода памяти и нагрузки.– Sh4dow25 дек 2011 в 19:19
-
2
-
@ilayer, для варианта @BogolyubskiyAlexey вам нужна одна формула - пересечение двух отрезков) например вот на дельфях. любая точка - да возьмите
{ 10000, 10000 }
. Посчитайте кол-во пересечений сторон многоугольника и отрезка (искомая точка, любая точка). Четность определить вроде не должно быть трудно))– Sh4dow25 дек 2011 в 19:28 -
Хорошо, спасибо, про луч смутило сначала немного, в голове не сходилось))– ilayer25 дек 2011 в 19:45
-
Кстати та реализация нифига не работает правильно... Если допустим у меня четыре полигона и у каждого одна из точек имеет одинаковые координаты, то при проверке пригадлежности этой точки к каждому полигону выводит, что она только одному полигону принадлежит)) Засада короче.. Вот пример - i074.radikal.ru/1112/b2/2118c7ac645e.png– ilayer25 дек 2011 в 21:28