Выскажите, пожалуйста, свои мысли по поводу моего задания =)

← →
Malder (2002-03-24 21:07) [0]

У меня такое задание. Написать программу построения так называемых Графов. Обьясняю, что это такое.
Вообщем на неком холсте (я выбрал канву компонента TPanel) нужно рисовать точки (vertex) и соединяющие их линии (line). Точки можно переносить по плоскости мышкой как угодно, при этом линии, идущие к этой точке, естественно, должны перерисовываться. Все это надо реализовывать с помощью объектов. Причем, желательно несколькими объектами. И все это надо объединить в главном объекте TGraph.
Я вот размышляю. Вроде как Vertex надо сделать объектом. Но с другой стороны - а зачем ? Кроме координаты x,y в нем ничего не будет. Значит, это обычная запись. Linе - тоже самое. Только у ТGraph будет несколько методов: перерисовка картинки, сохранение/загрузка текущего состояния в файл и т.д.
Ну да ладно. А вот теперь основное, что хочу спросить. Как запоминать, между какими точками проложены линии ? Если точку перенесут, то все линии идущие к ней нужно переместить к новому положению точки. То есть, надо узнать все линии, идущие к этой точке. Как это легкче сделать ? Просто перебирать все Line, а там хранить к какой точке она привязана ?
Как бы трудностей для выполнения никаких, но хотелось бы сделать наиболее изящно, эффективно и просто. Может у кого было похожее задание... поделитесь опытом.

← →
cypher (2002-03-24 22:04) [1]

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

← →
Malder (2002-03-24 22:22) [2]

cypher, согласен. Только если линия не привязана... Ведь если точку будут двигать, то и линия идущая в эту точку должна двигаться, правильно ? То есть ты предлагаешь перебирать все линии на предмет того, идут они к этой точке или нет ?

И еще. А нафига тогда реализовывать Vertex и Line как объекты ?

← →
Doom (2002-03-24 22:31) [3]

В каждом объекте "точка должен быть массив указателей на объеты связанных с ней точек".
Просто и красиво.
И не надо линий.
Двигаешь одну точку и по ссылке, зная координиты связанных с ней точек, перерисовываешь эти линии. И все!
Если что неправильно, не ругай, я только что придумал но по-моему идея классная!

← →
Malder (2002-03-24 22:54) [4]

угу. Идея хорошая. Но есть претензия - дублирование данных. Допустим, есть пара связанных точек. Что в той, что в этой точке нужно будет писать ссылку на другую. А для прорисовки линии достаточно только ссылки "с одной стороны".
И вот еще =). Если точка будет удалена - придется перебирать все другие точки на предмет удаления из них ссылок на эту точку...
блин... вот задача простая, а все равно гемморой...

← →
Бурундук (2002-03-24 23:02) [5]

>Malder ©
Перебирать все не придётся - ведь каждая точка знает,
в каких точках есть на неё ссылки

← →
Malder (2002-03-24 23:21) [6]

Бурундук, черт побери ! Гениально =)

так и сделаю...

P.S. Может еще кто чем поделится ?

← →
Лёша (2002-03-25 00:26) [7]

Правильно говорит Бурундук: Хранить указатели присоединённых Vertex внутри самой Vertex.
Что-то типа:

PVertex = ^TVertex; TVertex = record Point: TPoint; ArrOfLink: array of PVertex; end;

Это удобно, когда надо перерисовывать одну вершину.
А если надо перестроить/перерисовать более одной или все точки, то можно в запись добавить флаг, например: Calculated: boolean. И когда вцикле будешь рисовать линии, легко проверишь - рисовалась ли она.

Вообще, в инете должны быть теории по хранению и отображению графов. Попробуй порыться в курсовых.

← →
Бурундук (2002-03-25 01:06) [8]

флаг Calculated придётся добавлять в список ссылок, т.к. это параметр, характеризующий не одну вершину,
а пару вершин (линию).

TVertex = class
FPoint: TPoint;
FLinks: TList;
FCalculated: TList; // ради простоты можно в списке хранить вместо указателей Boolean (несколько некрасиво, правда)
// но можно в FLinks хранить нечто вроде
// TLink = class
// FLink: TVertex;
// Calculated: Boolean;
// end;
// тогда просто нужно
// будет написать свой поиск по списку (ведь искать ты будешь
// TVertex, а не TLink)

procedure Draw(Canvas; TCanvas);
end;

TVertex.Draw(Canvas: TCanvas);
var
i, SelfIndex: Intger;
Link: TVertex;
begin
for i := 0 to FLinks.Count-1
begin
Link := TVertex(FLinks[i]);
if not Boolean(FCalculated[i]) then
begin
Canvas.MoveTo(FPoint.X, FPoint.Y);
Canvas.LineTo(Link.FPoint.X, Link.FPoint.Y);
SelfIndex := Link.FLinks.IndexOf(Self);
// if SelfIndex = -1 then Error;
Link.Calculated[SelfIndex] := Pointer(True); // когда
// очередь дойдёт до вершины, на которую ссылаетя Link,
// она уже не будет повторно рисовать эту линию
Calculated[i] := Pointer(True); //
end;
end;
end;

← →
Бурундук (2002-03-25 01:18) [9]

Хотя это я уже торможу, пора спать.
Лёша © был прав, Одного
Calculated достаточно.
Если вершина нарисована, то все ведущие к ней линии нарисованы.

Выскажите, пожалуйста, свои мысли по поводу моего задания =) Найти похожие ветки