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

@Gepar · Регистрация: 01.07.2009

Студворк — интернет-сервис помощи студентам

Нужен такой вот алгоритм (а ещё лучше функция

).Поиск по форуму не увенчался успехом (темы есть , но кода нет). Вершины многоугольника не пересекаются. Помогите пожалуйста.

@castaway · 12.05.2012, 13:11

В общем я себе представляю это так:
1. Объекты добавляются в односвязный список.
2. При добавлении объекта вычисляешь его bounding box который будет храниться в самом объекте.
3. Когда надо проверить все объекты на hit-test перебираешь список:
a) если точка не попадает в bounding box, переходишь к следующему
b) если попадает - проверяешь через belong, если и там попадает - вызываешь метод get_ID и получаешь ID объекта, затем переходишь к следующему

@Gepar · 12.05.2012, 13:21 **[ТС]**

Сообщение от lazybiz

вызываешь метод get_ID

у меня ID сделан public чтобы хоть на один вызов было меньше

В общем я вижу ты предлагаешь мне комбинацию моих двух предыдущих методов ... можно попробовать, но я не уверен будет ли так работать быстрее чем с проверкой на вхождение лишь левой и правой x координате и последующем вызове belong ... Тут суть в том чтобы работало это всё дело как можно быстрее, любые средства хороши чтобы ускорить это дело (кроме stl, ну почти кроме stl: подключены из stl лишь string ... потом ещё swap'ить можно объекты если очень хочется, остальное вроде сервер блокирует).

@castaway · 12.05.2012, 13:25

Сообщение от Gepar

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

Из одного в другое переделать минутное дело.

Сделай окончательный вариант а там посмотрим что можно оптимизировать.

@Gepar · 12.05.2012, 13:41 **[ТС]**

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

Добавлено через 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 · 12.05.2012, 13:46

Сообщение от 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 · 12.05.2012, 15:41 **[ТС]**

lazybiz, да то я пока не начал заполнять те координаты что-то сразу такое написал. Дальше понял что все 8 хранить смысла нет.

@castaway · 12.05.2012, 15:59

Можно в bbox добавить метод bool hit_test( int x, int y ), для проверки попадания точки в заданную область. В общем фантазии нет предела!

Новые блоги и статьи Все статьи Все блоги /
Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .	Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .

@Gepar 1186 / 543 / 78 Регистрация: 01.07.2009 Сообщений: 3,517

	Принадлежит ли точка многоугольнику 10.05.2012, 18:01. Показов 33798. Ответов 86 Метки нет (Все метки) Нужен такой вот алгоритм (а ещё лучше функция ).Поиск по форуму не увенчался успехом (темы есть , но кода нет). Вершины многоугольника не пересекаются. Помогите пожалуйста. 0

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,170 Записей в блоге: 10
	12.05.2012, 13:11
	В общем я себе представляю это так: 1. Объекты добавляются в односвязный список. 2. При добавлении объекта вычисляешь его bounding box который будет храниться в самом объекте. 3. Когда надо проверить все объекты на hit-test перебираешь список: a) если точка не попадает в bounding box, переходишь к следующему b) если попадает - проверяешь через belong, если и там попадает - вызываешь метод get_ID и получаешь ID объекта, затем переходишь к следующему 1

@Gepar 1186 / 543 / 78 Регистрация: 01.07.2009 Сообщений: 3,517
	12.05.2012, 15:41 [ТС]
	lazybiz, да то я пока не начал заполнять те координаты что-то сразу такое написал. Дальше понял что все 8 хранить смысла нет. 0

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,170 Записей в блоге: 10
	12.05.2012, 15:59
	Можно в bbox добавить метод bool hit_test( int x, int y ), для проверки попадания точки в заданную область. В общем фантазии нет предела! 0