Реализация алгоритма удаления ребра графа мышью

Задача: удалить ребро графа, лежащее под курсором мыши (Рис. 3.2).

Рисунок 3.2 - Мышь находится рядом с ребром графа, который требуется удалить.

Решение:

Поскольку определять пересечение курсора мыши с линией не удобно, так как при тонкой линии требуется точное позиционирование мыши, по двум точкам строятся два треугольника, которые вместе образуют прямоугольник, который делит пополам ребро графа (рисунок 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;

if (sa > 0.0)

return PointPlace.LEFT;

if (sa < 0.0)

return PointPlace.RIGHT;

if ((a.X * b.X < 0.0) || (a.Y * b.Y < 0.0))

return PointPlace.BEHIND;

if (Math.Sqrt(a.X * a.X + a.Y * a.Y) < Math.Sqrt(b.X * b.X + b.Y * b.Y))

return PointPlace.BEYOND;

if (point == origin)

return PointPlace.ORIGIN;

if (point == dest)

return PointPlace.DESTINATION;

return PointPlace.BETWEEN;

}

Далее достаточно определить лежит ли точка в области, образованной ребрами треугольника. Эту задачу выполняет метод pointInTriangle, который принимает координаты треугольников и точку, принадлежность треугольникам которой следует проверить. Метод возвращает true, если точка принадлежит треугольнику и false в противном случае.

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

bool pointInTriangle(PointF p, PointF a, PointF b, PointF c)

{

return ((pointClassify(p, a, b) != PointPlace.LEFT) &&

(pointClassify(p, b, c) != PointPlace.LEFT) &&

(pointClassify(p, c, a) != PointPlace.LEFT));

}

Более подробное описание алгоритмов можно найти по следующим ссылкам:

1. http://algolist.manual.ru/maths/geom/belong/poly2d.php

2. http://algolist.manual.ru/maths/geom/datastruct.php