Курсовая работа: Разработка программы нахождения всех полных подграфов (клик) данного графа

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

Рисунок 3.3 - Прямоугольник, образованный двумя треугольниками, делит пополам ребро графа. Координаты мыши принадлежат одному из треугольников.

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

Рассмотрим алгоритм определения принадлежности точки к одному треугольнику. Для начала необходимо узнать, к какой области принадлежит точка (Рис. 3.4).

Рисунок 3.4. Области, в которых может лежать точка относительно линии.

Этим в классе Graph занимается частный метод pointClassify(Point source, Point dest), который возвращает один из элементов перечисления PointPlace, которое определяет область нахождения точки.

Перечисление PointPlace:

enum PointPlace : int

{

LEFT = 0,

RIGHT = 1,

BEYOND = 3,

BEHIND = 4,

BETWEEN = 5,

ORIGIN = 6,

DESTINATION = 7,

}

Листинг 3.4 – Метод pointClassify класса Graph.

PointPlace pointClassify(PointF point, PointF origin, PointF dest)

{

PointF a = dest;

a.X -= origin.X;

a.Y -= origin.Y;

PointF b = point;

b.X -= origin.X;

b.Y -= origin.Y;

double sa = a.X * b.Y - b.X * a.Y;