Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [Геометрия] Находится ли точка


Автор: gepard 27.1.2005, 05:32
В пространстве есть точка, лежащая в плоскости четырёхугольника. Четырёхугольник задан 4 вершинами, координаты точки и вершин известны. Как мне узнать: лежит ли эта точка в данном четырёхугольнике?

Автор: Akina 27.1.2005, 09:24
Делим четырехугольник на 2 треугольника (2 варианта, пробуем оба - на всякий случай). Проверка того что точка лежит внутри треугольника - тривиальна.

Автор: Alx 27.1.2005, 18:07
gepard
Модератор: Ну язык-то можно указать? smile smile

Автор: GoodBoy 27.1.2005, 18:15
Alx
А какая разница!!!! Тут алгоритм только и нужен! :-))))

Автор: Alx 27.1.2005, 18:17
GoodBoy
т.е. мне на JS ответить, да? smile

Автор: GoodBoy 27.1.2005, 18:19
Alx
Да запросто! :-))))) В С - то же самое практически получится... В Паскале - чуть переделать!!! А можно вообще просто алгоритм описать...
:-)))))

Автор: maxim1000 27.1.2005, 18:46
о, нашел все-таки...
http://forum.vingrad.ru/index.php?showtopic=25198&hl=точка#

Автор: Akina 27.1.2005, 19:03
maxim1000
Неправильно там. Представь четырехугольник с вершинами (0,0) (0,5) (5,-5) (-5,-5) и точку (1,1) - она лежит справа от одних сторон и слева от других... надо сперва бить на треугольники. Кстати, этот же четырехугольник объясняет почему надо пробовать оба разбиения (для четырехугольника это быстрее чем проверять вложенность).

А вот тут правильно - http://algolist.manual.ru/maths/geom/belong/poly2d.php - особенно см. примечание trurl.

Автор: maxim1000 27.1.2005, 19:22
Цитата
Представь четырехугольник с вершинами (0,0) (0,5) (5,-5) (-5,-5) и точку (1,1) - она лежит справа от одних сторон и слева от других...

это означает, что она находится снаружи многоугольника smile
Цитата
3. если точка всегда была с одной стороны, значит, она внутри, иначе - снаружи

кстати. не стоит забывать о направлении ребер (от этого зависит справа будет точка или слева)
направление ребра должно совпадать с направлением обхода...

Автор: gepard 28.1.2005, 05:48
Цитата
Модератор: Ну язык-то можно указать?

Мне нужен алгоритм, а не исходник.
И почему тему перенесли в Работа, хобби и учёба -> Vingrad - Колледж -> Центр помощи
Что за бред-то? Я вроде алгоритм прошу.
У винграда столько ответвлений стало, что скоро заблудиться можно будет smile
maxim1000
Благодарю...

Автор: Akina 28.1.2005, 10:15
Цитата(maxim1000 @ 27.1.2005, 20:22)
это означает, что она находится снаружи многоугольника

Ты карандашик-то в руки возьми... smile


Цитата(maxim1000 @ 27.1.2005, 20:22)
не стоит забывать о направлении ребер (от этого зависит справа будет точка или слева) направление ребра должно совпадать с направлением обхода...

Вот отсюда-то и жопа...

Автор: maxim1000 28.1.2005, 11:10
Цитата
Ты карандашик-то в руки возьми...

каюсь... был неправ...
у этого алгоритма есть одно ограничение: только выпуклые многоугольники smile

а вообще есть другой:
проводим из точки луч (в любую сторну) и считаем, сколько раз он пересек границу многоугольника
для простоты можно проводить луч по оси координат...

Автор: Akina 28.1.2005, 11:18
Цитата(maxim1000 @ 28.1.2005, 12:10)
а вообще есть другой:
проводим из точки луч (в любую сторну) и считаем, сколько раз он пересек границу многоугольника, для простоты можно проводить луч по оси координат...

угу.

Автор: maxim1000 28.1.2005, 11:38
почитал внимательно ссылку, которую ты привел, обнаружил, что этот метод там описан...
вывод: надо мне внимательнее читать чужие сообщения smile
а что касается комментария trurl, то сильно сомневаюсь, что оно будет вычислительно эффективным:
1. для каждого треугольника нужно будет проводить вычисление трех определителей третьего порядка - это куча вычислений
2. в случае трассировки луча - большая часть ребер вообще не будут пересекать ось, так что для них все обойдется двумя операциями сравнения, а для той небольшой части, которые будут - всего две операции умножения+несколько операций +,-,<>

Автор: Akina 28.1.2005, 12:47
maxim1000
коммент будет вычислительно эффективен, если речь идет о проверке вхождения в полигон, не помещающийся категорически в экран, при отображении точки - т.е. когда имеют место неявные отсечения.
На бесконечной плоскости - конечно эффективнее луч. Только все проще - в лоб считается точка пересечения 2 прямых (на которой луч и на которой отрезок) и делается контроль вхождения по одной из координат (если прямая не параллельна оси - пофиг по какой, а если параллельна - именно по этой). Проверка на необходимость до расчета точки пересечения имхо обойдется дороже...

Автор: maxim1000 28.1.2005, 13:03
Цитата
Только все проще - в лоб считается точка пересечения 2 прямых (на которой луч и на которой отрезок) и делается контроль вхождения по одной из координат (если прямая не параллельна оси - пофиг по какой, а если параллельна - именно по этой). Проверка на необходимость до расчета точки пересечения имхо обойдется дороже...

предположим, что исследуемая точка - начало координат (иначе, можно поотнимать ее координаты от всех точек - получится около 2n операций -)
1. предварительный расчет: если (y1>0)==(y2>0), выкидываем ребро, иначе идем дальше
2. окончательный расчет: проверяем (x2*y1>x1*y2)==(y1>y2) получаем ответ (есть пересечение или нет)
я точно не знаю: последнее условие - это условие пересечения с лучом или непересечения, но это уже детали
количества операций (n - количество вершин, m - количество ребер, пересекающих ось x):
+: 0
-: 2n
*: 2m
/: 0
>: 2n+2m
==(для bool): n+m

если разбивать на треугольники, то их будет n-2, и для каждого из них нужно будет считать три определителя...а потом еще и делить...

P.S.
а при чем тут экран и то, помещается ли в него многоугольник?

Автор: Elfet 2.6.2007, 22:45
А вот что я нашёл: http://nature.web.ru/db/msg.html?mid=1159496&mode=2 
Цитата

Сумма расстояний от точки, лежащей внутри треугольника, до его вершин меньше периметра треугольника.

Пусть ABC - данный треугольник, и точка O лежит внутри него. Вначале покажем, что AO+BO<AC+BC. Продолжим отрезок AO за точку O до пересечения с отрезком BC в точке D. Из неравенства треугольника следует, что OB<OD+BD. Отсюда AO+OB<AO+OD+BD=AD+BD. Далее, из треугольника ACD по неравенству треугольника получим AD<AC+CD. Поэтому AO+OB<AD+BD<AC+CD+BD=AC+BC. Аналогично неравенству AO+BO<AC+BC докажем, что BO+CO<BA+CA, CO+AO<CB+AB. Сложим полученные 3 неравенства, получим: 2(AO+BO+CO)<2(AB+BC+CA). Сократив на 2, получаем требуемое.


Можно ли это использовать? 

Автор: Xenon 2.6.2007, 22:54
Я так узнавал "находится ли точка в треугольнике".
Код

#include <iostream>
#include <cmath>

using namespace std;

const int COUNT = 3;
//Координата
struct coord
{
    int x;
    int y;
};

struct triangle
{
    coord apexes[COUNT]; //Вершины треугольника
    double sides[COUNT]; //Длины сторон треугольника
};

//Поиск расстояния между двумя координатами
double leight(coord obj, coord obj2)
{
    return sqrt( static_cast<double>((obj.x - obj2.x) * (obj.x - obj2.x) + (obj.y - obj2.y) * (obj.y - obj2.y)) );
}

//Поиск площади по формуле Герона
double find_area(double side_a, double side_b, double side_c)
{
    //Полупериметр из формулы Герона
    double p = (side_a + side_b + side_c) / 2;
    //Вернем площадь треугольника
    return ( sqrt( static_cast<double>(p * (p - side_a) * (p - side_b) * (p - side_c)) ) );
}
int main(int argc, char* argv[])
{
    coord dote; //Наша точка
    triangle trig; //Треугольник
    cout << "Vvedite koordinati tochki:\nx: ";
    cin >> dote.x;
    cout << "y: ";
    cin >> dote.y;
    cout << "Vvedite koordinati vershin treugolnika:\n";
    for (int i = 0; i < COUNT; ++i)
    {
        cout << "x" << i + 1 << ": ";
        cin >> trig.apexes[i].x;
        cout << "y" << i + 1 << ": ";
        cin >> trig.apexes[i].y;
    }
    //Найдем длины сторон треугольника
    trig.sides[0] = leight(trig.apexes[0], trig.apexes[1]); 
    trig.sides[1] = leight(trig.apexes[1], trig.apexes[2]);
    trig.sides[2] = leight(trig.apexes[2], trig.apexes[0]);
    //Площадь изначальной фигуры
    double original_area = find_area(trig.sides[0], trig.sides[1], trig.sides[2]);
    //Массив с длинами новых треугольников, образованых при соединении отрезками заданной точки и вершин треугольника
    double new_sides[COUNT] = { leight(dote, trig.apexes[0]), leight(dote, trig.apexes[1]), leight(dote, trig.apexes[2]) };
    //Сумма площадь получившихся треугольников
    double new_area = find_area( new_sides[0], new_sides[1], trig.sides[0]) + find_area( new_sides[1], new_sides[2], trig.sides[1]) + find_area( new_sides[0], new_sides[2], trig.sides[2]);
    if (static_cast<int>(original_area) == static_cast<int>(new_area)) cout << "Tochka lezhit v treugolnike";
    else cout << "Net, tochka ne lezhit v treugolnike";
    cin.sync();
    cin.get();
    return 0;
}

Автор: maxim1000 2.6.2007, 23:50
Цитата(Elfet @  2.6.2007,  22:45 Найти цитируемый пост)
Сумма расстояний от точки, лежащей внутри треугольника, до его вершин меньше периметра треугольника.


Цитата(Elfet @  2.6.2007,  22:45 Найти цитируемый пост)
Можно ли это использовать?

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

Автор: Xenon 3.6.2007, 00:04
Ну по-моему самый нормальный вариант - образно точку соединить отрезками с вершинами квадрата, вычислить длины сторон по координатам точек, найти сумму площадей получившихся треугольников и сравнить ее с площадью квадрата. Если они одинаковы, значи точка в квадрате.

Автор: apook 3.6.2007, 01:42
Дарова! я двоишник
user posted image
Цитата

Таким образои если соблюдено условия
Ax < Ex < Dx
Ay < Ey < By
то точка в четырехугольнике точка C вообще не интересует

Автор: maxim1000 3.6.2007, 09:24
Цитата(apook @  3.6.2007,  01:42 Найти цитируемый пост)
Таким образои если соблюдено условия
Ax < Ex < Dx
Ay < Ey < By
то точка в четырехугольнике точка C вообще не интересует

ну если рассматривать только те четырёхугольники, которые являются прямоугольниками со сторонами, параллельными осям координат, то, конечно же, решение упрощается...

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)