Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.55/65: Рейтинг темы: голосов - 65, средняя оценка - 4.55
Gepar
1181 / 537 / 77
Регистрация: 01.07.2009
Сообщений: 3,517
1

Принадлежит ли точка многоугольнику

10.05.2012, 18:01. Просмотров 12036. Ответов 86
Метки нет (Все метки)

Нужен такой вот алгоритм (а ещё лучше функция ).Поиск по форуму не увенчался успехом (темы есть , но кода нет). Вершины многоугольника не пересекаются. Помогите пожалуйста.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.05.2012, 18:01
Ответы с готовыми решениями:

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

Дана точка М(x, y). Присвоить z = 1, если точка принадлежит окружности с радиусом R и центром в точке (a, b) и z = 0 в противном случае.
Дана точка М(x, y). Присвоить z = 1, если точка принадлежит окружности с...

Даны отрезки [a, b] и [c, d] и точка A с координатой х. Определить, принадлежит ли данная точка одному из этих отрезков, обоим или лежит вне их
Даны отрезки и и точка A с координатой х. Определить, принадлежит ли данная...

Определить принадлежит точка точка координатам
Такая задача даны действительные числа x y определить принадлежит точка ...

Принадлежит ли точка четырехугольнику?
Подскажите пожалуйста, как можно по проще проверить лежит ли заданная точка (x,...

86
castaway
Эксперт С++
4930 / 3037 / 453
Регистрация: 10.11.2010
Сообщений: 11,117
Записей в блоге: 10
Завершенные тесты: 1
12.05.2012, 13:11 81
В общем я себе представляю это так:
1. Объекты добавляются в односвязный список.
2. При добавлении объекта вычисляешь его bounding box который будет храниться в самом объекте.
3. Когда надо проверить все объекты на hit-test перебираешь список:
a) если точка не попадает в bounding box, переходишь к следующему
b) если попадает - проверяешь через belong, если и там попадает - вызываешь метод get_ID и получаешь ID объекта, затем переходишь к следующему
1
Gepar
1181 / 537 / 77
Регистрация: 01.07.2009
Сообщений: 3,517
12.05.2012, 13:21  [ТС] 82
Цитата Сообщение от lazybiz Посмотреть сообщение
вызываешь метод get_ID
у меня ID сделан public чтобы хоть на один вызов было меньше
В общем я вижу ты предлагаешь мне комбинацию моих двух предыдущих методов ... можно попробовать, но я не уверен будет ли так работать быстрее чем с проверкой на вхождение лишь левой и правой x координате и последующем вызове belong ... Тут суть в том чтобы работало это всё дело как можно быстрее, любые средства хороши чтобы ускорить это дело (кроме stl, ну почти кроме stl: подключены из stl лишь string ... потом ещё swap'ить можно объекты если очень хочется, остальное вроде сервер блокирует).
0
castaway
Эксперт С++
4930 / 3037 / 453
Регистрация: 10.11.2010
Сообщений: 11,117
Записей в блоге: 10
Завершенные тесты: 1
12.05.2012, 13:25 83
Цитата Сообщение от Gepar Посмотреть сообщение
... можно попробовать, но я не уверен будет ли так работать быстрее чем с проверкой на вхождение лишь левой и правой x координате и последующем вызове belong ...
Из одного в другое переделать минутное дело.

Сделай окончательный вариант а там посмотрим что можно оптимизировать.
0
Gepar
1181 / 537 / 77
Регистрация: 01.07.2009
Сообщений: 3,517
12.05.2012, 13:41  [ТС] 84
Поразмышлял: наверное сделаю как вы пишете с прямоугольником обрамляющим.

Добавлено через 2 минуты
Правда с этим обрамляющим прямоугольником жутковато выглядит родительский класс:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class CObject
{
public:
    CObject(int _id)
    :ID(_id) {}
 
    virtual CObject* clone() const =0;
    virtual bool belong(int px, int py) const=0;
    virtual int leftX() const =0;
    virtual int rightX() const =0;
 
    int ID;
    //bounding box
    int bx1;
    int by1;
    int bx2;
    int by2;
    int bx3;
    int by3;
    int bx4;
    int by4;
};
0
castaway
Эксперт С++
4930 / 3037 / 453
Регистрация: 10.11.2010
Сообщений: 11,117
Записей в блоге: 10
Завершенные тесты: 1
12.05.2012, 13:46 85
Цитата Сообщение от Gepar Посмотреть сообщение
C
1
2
3
4
5
6
7
8
9
//bounding box
* * int bx1;
* * int by1;
* * int bx2;
* * int by2;
* * int bx3;
* * int by3;
* * int bx4;
* * int by4;
o_O Зачем?

Сделай так:
C
1
2
3
4
5
6
7
8
9
10
11
typedef struct {
    int x0, y0;    // левый верхний
    int x1, y1;    // правый нижний
} bbox;
 
class CObject
{
    ...
    bbox    bb;
    ...
};
и все будет красиво.
0
Gepar
1181 / 537 / 77
Регистрация: 01.07.2009
Сообщений: 3,517
12.05.2012, 15:41  [ТС] 86
lazybiz, да то я пока не начал заполнять те координаты что-то сразу такое написал. Дальше понял что все 8 хранить смысла нет.
0
castaway
Эксперт С++
4930 / 3037 / 453
Регистрация: 10.11.2010
Сообщений: 11,117
Записей в блоге: 10
Завершенные тесты: 1
12.05.2012, 15:59 87
Можно в bbox добавить метод bool hit_test( int x, int y ), для проверки попадания точки в заданную область. В общем фантазии нет предела!
0
12.05.2012, 15:59
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.05.2012, 15:59

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

Принадлежит ли точка четырехугольнику.
Надеюсь на помощь форумчан: Задача следующяя: задана коодинатами точек...

Принадлежит ли точка фигуре
Определить принадлежность точки областям, обозначенным прописными буквами A и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
87
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru