Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 72, средняя оценка - 4.69
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
10.05.2012, 18:01     Принадлежит ли точка многоугольнику #1
Нужен такой вот алгоритм (а ещё лучше функция ).Поиск по форуму не увенчался успехом (темы есть , но кода нет). Вершины многоугольника не пересекаются. Помогите пожалуйста.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 10
Завершенные тесты: 1
12.05.2012, 13:11     Принадлежит ли точка многоугольнику #81
В общем я себе представляю это так:
1. Объекты добавляются в односвязный список.
2. При добавлении объекта вычисляешь его bounding box который будет храниться в самом объекте.
3. Когда надо проверить все объекты на hit-test перебираешь список:
a) если точка не попадает в bounding box, переходишь к следующему
b) если попадает - проверяешь через belong, если и там попадает - вызываешь метод get_ID и получаешь ID объекта, затем переходишь к следующему
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
12.05.2012, 13:21  [ТС]     Принадлежит ли точка многоугольнику #82
Цитата Сообщение от lazybiz Посмотреть сообщение
вызываешь метод get_ID
у меня ID сделан public чтобы хоть на один вызов было меньше
В общем я вижу ты предлагаешь мне комбинацию моих двух предыдущих методов ... можно попробовать, но я не уверен будет ли так работать быстрее чем с проверкой на вхождение лишь левой и правой x координате и последующем вызове belong ... Тут суть в том чтобы работало это всё дело как можно быстрее, любые средства хороши чтобы ускорить это дело (кроме stl, ну почти кроме stl: подключены из stl лишь string ... потом ещё swap'ить можно объекты если очень хочется, остальное вроде сервер блокирует).
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 10
Завершенные тесты: 1
12.05.2012, 13:25     Принадлежит ли точка многоугольнику #83
Цитата Сообщение от Gepar Посмотреть сообщение
... можно попробовать, но я не уверен будет ли так работать быстрее чем с проверкой на вхождение лишь левой и правой x координате и последующем вызове belong ...
Из одного в другое переделать минутное дело.

Сделай окончательный вариант а там посмотрим что можно оптимизировать.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
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;
};
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 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;
    ...
};
и все будет красиво.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
12.05.2012, 15:41  [ТС]     Принадлежит ли точка многоугольнику #86
lazybiz, да то я пока не начал заполнять те координаты что-то сразу такое написал. Дальше понял что все 8 хранить смысла нет.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.05.2012, 15:59     Принадлежит ли точка многоугольнику
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 10
Завершенные тесты: 1
12.05.2012, 15:59     Принадлежит ли точка многоугольнику #87
Можно в bbox добавить метод bool hit_test( int x, int y ), для проверки попадания точки в заданную область. В общем фантазии нет предела!
Yandex
Объявления
12.05.2012, 15:59     Принадлежит ли точка многоугольнику
Ответ Создать тему
Опции темы

Текущее время: 09:28. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru