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

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

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

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

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

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

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

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

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

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

86
castaway
Эксперт С++
4926 / 3033 / 453
Регистрация: 10.11.2010
Сообщений: 11,089
Записей в блоге: 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
Эксперт С++
4926 / 3033 / 453
Регистрация: 10.11.2010
Сообщений: 11,089
Записей в блоге: 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
Эксперт С++
4926 / 3033 / 453
Регистрация: 10.11.2010
Сообщений: 11,089
Записей в блоге: 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
Эксперт С++
4926 / 3033 / 453
Регистрация: 10.11.2010
Сообщений: 11,089
Записей в блоге: 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 и...

Принадлежит ли точка прямоугольнику?
Даны координаты (x1, y1), (x2, y2), (x3, y3), (x4, y4) - вершины...

Принадлежит ли точка области.
Даны действительные числа x, y. Определить, принадлежит ли точка с координатами...


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

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

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