Модераторы: Poseidon

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Геометрия] Находится ли точка , в данном четырёхугольнике? 
:(
    Опции темы
gepard
  Дата 27.1.2005, 05:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 2477
Регистрация: 29.2.2004

Репутация: 2
Всего: 40
В пространстве есть точка, лежащая в плоскости четырёхугольника. Четырёхугольник задан 4 вершинами, координаты точки и вершин известны. Как мне узнать: лежит ли эта точка в данном четырёхугольнике?


--------------------
Когда начинаются цифровые войны, а траффик разносит моё сознание по бесконечным просторам инета, подобно ветру, разносящему листву по полям, тогда и только тогда я чувствую себя свободным!
© Я, Берсерк, что значит - Неистовый. 
PM MAIL WWW ICQ   Вверх
Akina
Дата 27.1.2005, 09:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 17
Всего: 454
Делим четырехугольник на 2 треугольника (2 варианта, пробуем оба - на всякий случай). Проверка того что точка лежит внутри треугольника - тривиальна.


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.
PM MAIL WWW ICQ Jabber   Вверх
Alx
Дата 27.1.2005, 18:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Ajaxy
****


Профиль
Группа: Комодератор
Сообщений: 2903
Регистрация: 26.11.2003
Где: Cutopia

Репутация: нет
Всего: 78
gepard
Модератор: Ну язык-то можно указать? smile smile


--------------------
© сам придумал.

. the world's most misunderstood programming language .
PM MAIL WWW ICQ   Вверх
GoodBoy
Дата 27.1.2005, 18:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Главный джедай
****


Профиль
Группа: Модератор
Сообщений: 3886
Регистрация: 8.1.2003
Где: КМВ

Репутация: нет
Всего: 83
Alx
А какая разница!!!! Тут алгоритм только и нужен! :-))))


--------------------
Чем дальше в лес, тем толще партизаны...

Цитата(igorold @  1.5.2016,  17:40 Найти цитируемый пост)
Индейцы не обратили внимания на поток беженцев из Европы… Теперь они живут в резервациях. 
PM MAIL   Вверх
Alx
Дата 27.1.2005, 18:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Ajaxy
****


Профиль
Группа: Комодератор
Сообщений: 2903
Регистрация: 26.11.2003
Где: Cutopia

Репутация: нет
Всего: 78
GoodBoy
т.е. мне на JS ответить, да? smile


--------------------
© сам придумал.

. the world's most misunderstood programming language .
PM MAIL WWW ICQ   Вверх
GoodBoy
Дата 27.1.2005, 18:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Главный джедай
****


Профиль
Группа: Модератор
Сообщений: 3886
Регистрация: 8.1.2003
Где: КМВ

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


--------------------
Чем дальше в лес, тем толще партизаны...

Цитата(igorold @  1.5.2016,  17:40 Найти цитируемый пост)
Индейцы не обратили внимания на поток беженцев из Европы… Теперь они живут в резервациях. 
PM MAIL   Вверх
maxim1000
Дата 27.1.2005, 18:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 24
Всего: 110
о, нашел все-таки...
http://forum.vingrad.ru/index.php?showtopic=25198&hl=точка#


--------------------
qqq
PM WWW   Вверх
Akina
Дата 27.1.2005, 19:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

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

А вот тут правильно - Проверка принадлежности точки многоугольнику - особенно см. примечание trurl.


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.
PM MAIL WWW ICQ Jabber   Вверх
maxim1000
Дата 27.1.2005, 19:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 24
Всего: 110
Цитата
Представь четырехугольник с вершинами (0,0) (0,5) (5,-5) (-5,-5) и точку (1,1) - она лежит справа от одних сторон и слева от других...

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

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


--------------------
qqq
PM WWW   Вверх
gepard
Дата 28.1.2005, 05:48 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 2477
Регистрация: 29.2.2004

Репутация: 2
Всего: 40
Цитата
Модератор: Ну язык-то можно указать?

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


--------------------
Когда начинаются цифровые войны, а траффик разносит моё сознание по бесконечным просторам инета, подобно ветру, разносящему листву по полям, тогда и только тогда я чувствую себя свободным!
© Я, Берсерк, что значит - Неистовый. 
PM MAIL WWW ICQ   Вверх
Akina
Дата 28.1.2005, 10:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 17
Всего: 454
Цитата(maxim1000 @ 27.1.2005, 20:22)
это означает, что она находится снаружи многоугольника

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


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

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


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.
PM MAIL WWW ICQ Jabber   Вверх
maxim1000
Дата 28.1.2005, 11:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 24
Всего: 110
Цитата
Ты карандашик-то в руки возьми...

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

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


--------------------
qqq
PM WWW   Вверх
Akina
Дата 28.1.2005, 11:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

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

угу.


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.
PM MAIL WWW ICQ Jabber   Вверх
maxim1000
Дата 28.1.2005, 11:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

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


--------------------
qqq
PM WWW   Вверх
Akina
Дата 28.1.2005, 12:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

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


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.
PM MAIL WWW ICQ Jabber   Вверх
maxim1000
Дата 28.1.2005, 13:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 24
Всего: 110
Цитата
Только все проще - в лоб считается точка пересечения 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.
а при чем тут экран и то, помещается ли в него многоугольник?


--------------------
qqq
PM WWW   Вверх
Elfet
  Дата 2.6.2007, 22:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Белый и Пушистый
****


Профиль
Группа: Awaiting Authorisation
Сообщений: 3776
Регистрация: 2.4.2003

Репутация: нет
Всего: 16
А вот что я нашёл: 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, получаем требуемое.


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

Это сообщение отредактировал(а) Elfet - 2.6.2007, 22:46


--------------------
PHP Чат Скрипт
PM MAIL WWW Skype   Вверх
Xenon
Дата 2.6.2007, 22:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Участник Клуба
Сообщений: 1529
Регистрация: 12.4.2006

Репутация: 19
Всего: 50
Я так узнавал "находится ли точка в треугольнике".
Код

#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;
}



--------------------
user posted image  
PM MAIL   Вверх
maxim1000
Дата 2.6.2007, 23:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

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


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

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


--------------------
qqq
PM WWW   Вверх
Xenon
Дата 3.6.2007, 00:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Участник Клуба
Сообщений: 1529
Регистрация: 12.4.2006

Репутация: 19
Всего: 50
Ну по-моему самый нормальный вариант - образно точку соединить отрезками с вершинами квадрата, вычислить длины сторон по координатам точек, найти сумму площадей получившихся треугольников и сравнить ее с площадью квадрата. Если они одинаковы, значи точка в квадрате.


--------------------
user posted image  
PM MAIL   Вверх
apook
Дата 3.6.2007, 01:42 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 794
Регистрация: 12.7.2006

Репутация: 10
Всего: 23
Дарова! я двоишник
user posted image
Цитата

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



--------------------
Мои руки из дуба, голова из свинца ну и пусть ...
PM MAIL   Вверх
maxim1000
Дата 3.6.2007, 09:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

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

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



--------------------
qqq
PM WWW   Вверх
Страницы: (2) [Все] 1 2 
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1126 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.