Здравствуйте. Нужно сделать следующее. Есть 4 точки (x и y-координаты) которые формируют четырехугольник. Так же есть точка с координатами. Нужно определить является ли точка внутри четырех угольника.
Сейчас делаю так. Разбиваю четырехугольник на два треугольника. Если точка в одном их треугольников, то она и в 4-угольнике в целом.
Далее как я определяю внутри мы треугольника или нет. Я имея три координаты могу посчитать площадь треугольника. Точка внутри треугольника делит его три три треугольника. Так вот если сумма трех треугольников равна площади большого треугольника то точка лежит внутри. Вот.

Но на AVR этот алгоритм работает очень долго, много времени тратится. Подскажите как сделать оптимальнее? Если поделитесь кусками кода вообще будет супер.
Заранее спасибо.

Ужас какой! Четырехугольник можно рассматривать как пересечение полуплоскостей, образованных его сторонами. То есть всего-то надо определить, принадлежит ли точка каждой из этих полуплоскостей.

Если деление на треугольники прошло успешно (с невыпуклами четырехугольниками все сложнее), проверим лежит ли точка внутри одного из треугольников. Пусть треугольник ABC и точка M. проверяем лежит ли точка M в одной полуплоскости, скажем, с вершиной A относительно стороны ВС.
Для этого находим точку пересечения O диагоналей четырехугольника МАВС (решаем систему из двух линейных уравнений). И сравниваем длины AO и АМ. Проверка успешна, если AO >= AM.
Все тоже самое для точек B и C. Если все три проверки удачные, то точка внутри треугольника.
Операций тут явно меньше, но надо проверить пару крайних случаев, в которых система линейных уравнений не решается



как же это быстро сделать?

Определить принадлежность точки полуплоскости просто. Для этого находим знак выражения:
(x2 - x1) * (y - y1) - (y2 - y1) * (x - x1), где
x1, y1 и x2, y2 - координаты точек прямой
x, y - координаты определяемой точки

Для выпуклого четырехугольника нужно выполнить четыре таких операции.

И какой же знак должен быть, плюс или минус???

Ясно, что по разные стороны от прямой это выражение принимает разные по знаку значения, а для того чтобы определить какие, нужно крепко подумать. Заметьте, что если вы поменяете местами x1,y1 и x2,y2 знак изменится.

Сообщение отредактировал mluk - Jul 1 2010, 05:22

У вас что там, графический ускоритель на АВР?
Метод научного тыка не пробовали применить?
Взять координаты прямой, координаты точки и посмотреть, как их взаимное расположение влияет на знак.

Здесь надо знак выбирать такой же как при подстановке в выражение оставшейся из двух вершин четырехугольника. И это работает только для выпуклах четырехугольников.

Всего-то вершины отсортировать нужно.


Не выпуклый разбивается на два треугольника.

А что, ещё вогнутые бывают?
Прошу не пинать, в школе давно не был, а ребёнок в 1 классе, пока ещё не дошли...

Понял, что за выпуклые.
Для вогнутых тоже сработает.
Проверьте на бумажке.

Понял, не сработает...
Тогда да, на 2 треугольника.
Причём так: внешний, образованный 3-мя внешними вершинами, и внутренний, который как бы вырезан из 1-го.
И проверять вхождение в 1-й и невхождение во 2-й.

А бывают неправильные 4-угольники?
Которые сами себя пересекают?
Или это уже по-другому называется?
Вот где ж...


А если x1,y1 и x2,y2 воспринимать как координаты вектора, то знак однозначно определяет, с какой стороны ваша точка по отношению к этому вектору

Пару месяцев назад на собеседовании в одну модную контору дали задание на пересечение простых многоугольников. Алгоритм нахождения принадлежности точки к многоугольнику я есс-но попытался найти готовый, но все что мне попадалось, как то меня не убедило. Я когда то слышал о таком варианте. делаете обход вершин многоугольника из искомой точки и подсчитываете сумму углов поворота вектора, образованного из точки и вершин. Если сумма ноль, точка снаружи, если +||- 2*pi, то внутри.
ВАЖНО! Алгоритм протестирован только (и работает) для простых(как выпуклых, так и не выпуклых) многоугольников.
Тестовое задание писалось на полном с++, так что пользы от исходников мало
Вот метод класса полигон, проверяющий принадлежность точки:

Именно так, а не иначе учат все книги по машинной графике, например эта
http://www.twirpx.com/file/31062/

То есть их там несколько, но я читал только Павлидиса))

Все это вариации одного и того же. Чтобы вычислить угол, имея координаты точек, мы должны вычислить векторное произведение, потом произвести некоторые другие манипуляции. А что за формула написана в 4-м посте?
И то, что в самом начале написал автор сводится тоже к тому же.

Не совсем. Бывают многоугольники и впуклые, но правильные. Для которых работает обход по контуру. Из обхода по контуру можно вывести формулу в 4-м посте только для выпуклых многоугольников. Но не для впуклых.

Трудно сходу представить себе правильный невыпуклый четырёхугольник)) Но это тоже бывает, буквой V
Вот треугольник - он всегда выпуклый, а так - нет

ЗЫ. Правильный, если кто забыл - это без самопересечений, если я правильно помню

Автор, наверное, имел в виду только правильные. Иначе, например, четыре точки в вершинах квадрата порождают 3 четырехугольника.
Он об этом не писал, но его мысли прослеживаются через его алгоритм.

Ускорить на AVR можно так.

1. Отказываетесь от плавающей арифметики. Оптимизируете целочисленные проверки на ассемблере, чтобы не вычислять лишних промежуточных результатов.

2. Считаете количество сторон четырехугольника, пересекающих вертикальную координату точки слева от неё. При этом сразу быстро простыми сравнениями вертикальных координат отсекаются стороны, лежащие целиком выше или ниже горизорнтали точки. Также быстро учитываются отрезки, целиком лежащие (стоящие) слева или справа от точки. Остается проверить только отрезки, обе координаты концов которых лежат по разные стороны от точки. Проверяете, вычисляя знак векторного произведения и учитывая направление отрезка. Тут придется умножать. Впрочем, если отрезок короткий - можете пройтись по его точкам Брезенхамом.

3. Если подсчитанное количество таких отрезков нечетное - точка внутри четырехугольника.

4. И не забудьте, что точка может лежать точно на отрезке. Что в этом случае делать - вам виднее.