Обьект внутри четырех угольника Опции

[gsm_starter]

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

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

[mluk]

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

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

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

[aaarrr]

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

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

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

[mluk]

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

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

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

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

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

[mluk]

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

[MrYuran]

И это работает только для выпуклах четырехугольников.

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

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

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

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

Заметьте, что если вы поменяете местами x1,y1 и x2,y2 знак изменится.

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