VPF::[Геометрия] Находится ли точка

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

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 Чат Скрипт

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

--------------------

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

Xenon

Дата 3.6.2007, 00:04 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 19
Всего: 50

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

--------------------

apook

Дата 3.6.2007, 01:42 (ссылка)

(голосов:1)

Загрузка ...

Опытный

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

Репутация: 10
Всего: 23

Дарова! я двоишник
user posted image

Цитата

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

--------------------

Мои руки из дуба, голова из свинца ну и пусть ...

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

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »