Интерфейс Пример работы с программой

Шаг 1.

Двойным щелчком левой клавиши мыши расставляем по полю точки (функция продублирована в меню Правка->Вставить точку).

Точки можно перемещать, удалять как через меню Правка так и с помощью мыши и горячих клавиш (CTRL-INS, CTRL-DEL)

Шаг 2.

Осуществляем предобработку: пункт меню Алгоритм->Запустить.

Или осуществляем алгоритм по шагам (Алгоритм->Предобработка Начать/След шаг). При этом на экране выводится текущий локус с цифрой в углу, показывающий число доминирования

Предобработку можно в любой момент повторить.

При щелчке мышкой по полю в правом нижнем углу формы показывается текущий локус.

Шаг 3.

Выделяем область для регионального поиска: нажимаем и держим клавишу SHIFT, двигаем мышкой с нажатой левой клавишей. Чтобы узнать, сколько точек попало в нашу область, необходимо выполнить алгоритм Алгоритм->Запустить. Или выполнить по шагам Алгоритм-> Начать/След шаг. При этом если после предобработки были внесены изменения на поле (вставлена, удалена, перемещена точка), то сначала выполнится предобработка.

Интерфейс.

Удалить все точки — Правка->Очистить поле

Сгенерировать N точек — Правка->Генерация точек

Изменить масштаб — Визуализация->Увеличить / Уменьшить

Реализация алгоритмов Выбор и определение структур данных

#define INFINITY 10000000

#define INFINITY_POINT TPoint(INFINITY, INFINITY)

#define INFINITY_MYPOINT MyPoint(INFINITY_POINT, INFINITY)

#define NULL_POINT TPoint(-111,-111)

#define NULL_MYPOINT MyPoint(NULL_POINT, -1)

#define NULL_MYRECT MyRect(NULL_POINT, NULL_POINT)

#define NULL_LOCUS TLocus(NULL_POINT, NULL_POINT, 0)

Описание точки на плоскости (координаты и ее порядковый номер)

struct MyPoint {

MyPoint(const TPoint& pntPoint = NULL_POINT, int iNumber = -1)

int number;

TPoint point;

};

Описание прямоугольника на плоскости

struct MyRect {

MyRect(const TPoint& point1, const TPoint& point2);

MyRect(int left, int top, int right, int bottom);

const RECT& getRect()

RECT rect;

};

Список точек на плоскости инкапсулирует stl-класс list. В список _array_points в конец заносятся новые точк. Также есть еще два списка _array_x_sorted и _array_y_sorted, в которых хранятся эти точки отсортированные по соответствующим осям. Выбор именно списка (а не вектора и т.д.) обусловлен быстротой работы (вставки и удаления) элементов в середину контейнера.

Описание множества точек на плоскости

typedef list<MyPoint*>::const_iterator TPointListConstIterator;

class TPointList {

public:

TPointList()

MyPoint addPoint(const TPoint&); добавление точки

void deletePoint(const MyPoint&); удаление точки

void deletePoint(int);

void deletePoints();

MyPoint movePoint(const MyPoint&, TPoint); перенос точки

MyPoint getPoint(int);

int getPointCount() const;

MyPoint getPointInArea(const TPoint&, int);

TPointListConstIterator begin();

TPointListConstIterator end();

void clear();

protected:

typedef list<MyPoint*> TObjectList;

typedef list<MyPoint*>::iterator TObjectListIterator;

TObjectList _array_points;

TObjectList _array_x_sorted;

TObjectList _array_y_sorted;

private:

MyPoint addPoint(const TPoint&, int);

int _elemCount;

};

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

Описание локуса точек на плоскости

struct TLocus : public MyRect {

TLocus( const TPoint& point1, const TPoint& point2, int dom);

TLocus( int left, int top, int right, int bottom, int dom);

int domination;

};

Класс “региональный поиск” представляет собой все тот же набор точек. Но новый класс должен уметь по заданным точкам строить набор локусов и отвечать на вопрос “сколько точек содержится в заданном прямоугольнике”. Поэтому мы наследуем класс TPointList , доопределяем методы работы с точками (addPoint, deletePoint, movePoint) и добавляем член _locus_list, хранящий вектор (для бинарного поиска) локусов, упорядоченных по xy оси (см. рис. 2.3).

Описание конечного класса алгоритма

class TRegionalSearch : public TPointList {

typedef vector<TLocus> TObjectList;

typedef vector<TLocus>::iterator TObjectListIterator;

public:

TRegionalSearch();

MyPoint addPoint(const TPoint&);

void deletePoint(const MyPoint&);

MyPoint movePoint(const MyPoint&, TPoint);

void clear();

возвращает число точек в заданной области и возвращает 4 локуса (см. теорию)

int getPointCountInRect(const MyRect&, TLocus&,TLocus&,TLocus&,TLocus&);

public:

сделать предоработку полностью или 1 шаг

TLocus preprocessing();

TLocus preprocessingStep(int);

private:

TPointList::TObjectListIterator ix, iy;

struct preprocessingSearchStruct {

TPoint pred_x, pred_y;

TLocus locus_x, locus_y;

TObjectListIterator ilocusy;

int ixpoints, iypoints;

void init() {

pred_x = TPoint(0, 0);

pred_y = TPoint(0, 0);

locus_x= NULL_LOCUS;

locus_y= NULL_LOCUS;

}

} pps;

MyPoint pointInfinity;

TObjectList _locus_list;

int isModified;

};