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

[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 воспринимать как координаты вектора, то знак однозначно определяет, с какой стороны ваша точка по отношению к этому вектору

[ig_z]

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

CODE

bool Polygon::isInternal(const IVertex::Ptr v)
{
    double angle = 0;
    for (IVertex::iter i = _vertexes.begin(); i < _vertexes.end(); i++)
    {
        angle += v->angle(**i, **((*i)->getFWVertex()));
    }
    return (angle > 1.0)||(angle < -1.0);
}

[fontp]

Я когда то слышал о таком варианте. делаете обход вершин многоугольника из искомой точки и подсчитываете сумму углов поворота вектора, образованного из точки и вершин. Если сумма ноль, точка снаружи, если +||- 2*pi, то внутри.

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

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

[Tanya]

Именно так, а не иначе учат все книги по машинной графике, например эта

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

[fontp]

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

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

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

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