He preferido que esta quinta entrega cerrara el título “Experimentos, reflexiones y otros artefactos”, y despedir estos mini artículos o mini serie, si es que se pueden llamar así, con un ejemplo un tanto más avanzado, pero en la linea de los anteriores. Así que me habeis tenido aperreado toda la semana, dándole vueltas a la cabeza sobre cómo iba a finalizar estas entradas. 🙂
No. No creais que es sencillo elegir el “experimento” ya que debe cumplir a priori algunas condiciones en cuanto a la extensión, a su complejidad, al uso de componentes que puedan ser compatibles en varias versiones y casi siempre en cuanto a que sea verdaderamente didáctico. Por lo que no vale cualquier idea que te venga a la cabeza, sino que tienes que pelearte con ella y ver si realmente te vale. Y os confieso cuando uno llega a casa tras la jornada diaria quedan pocas ganas de pelearse con nada (os pasará tambien a vosotros casi con seguridad). 🙂
En fin… Yo creo que sí que vale la pena el esfuerzo, y creo muchos de vosotros lo agradecereis.
¿Teneis ganas de trabajar un rato?
Venga, vamos allá.
Este era el ejemplo que se me ocurrió: Imaginaba que pudieramos tener la necesidad de calcular el modo más óptimo de recorrer una cantidad de puntos indefinido, eso sí, recorriendolos todos, desde un origen cualquiera hasta un destino cualquiera. Esa era la primera idea que me me vino a la mente. La idea además era vistosa, porque podíamos dibujar los puntos y las lineas sobre el formulario, lo cual no era demasiado difícil. Además, nos permitía seguir abordando el uso de clases muy básicas como las listas de punteros (TList), que muchos compañeros que dan sus primeros pasos pudieran no estar demasiado familiarizados.
El problema es que tras esa idea, existe una complejidad inherente que puede ser tan grande como uno quiera, por lo que decidí intentar abordarlo de una forma sencilla, aun a pesar de que pueda no ser optima. Y el criterio que se sigue para ordenar el camino que nos conduce desde el nodo (rojo) hasta el nodo (azul) sigue una pauta que se rige en calcular la menor distancia con respecto al nodo anterior, una vez ordenado el vector.
De hecho, si os fijais he puesto lineas mas arriba “¿Teneis ganas de trabajar un rato?” y lo he hecho porque os dejo para vosotros si quereis adaptarlo para que no considere todos los nodos sino el camino mínimo (fijado previamente una numero de puntos por los que haya que pasar) y no considere en la ruta todos, sino esa cantidad.
Al crearse el formulario, recrea una cantidad de nodos (he puesto 10 por poner una cifra) en puntos aleaotorios de un recuadro del formulario. El punto rojo es la salida (es otro nodo pero no es del vector). El punto azul el destino(tambien otro nodo que no existe en el vector). Ambos puntos, se enlazan a cada uno de los nodos del vector simplemente para que se pudiera ver una idea que voy a comentar posteriormente (*).
Esta es un imagen del formulario:
Asi que, como comentaba en lineas anteriores, vamos a recorrer el vector de nodos y reordenarlo sucesivamente hasta que se cumpla la precondición, que es que la ruta quede ordenada en función de la distacia al nodo que nos sirve de pivote, que va recorriendo la ruta que parte desde el punto de origen. Iniciamos en el punto de salida y buscamos el nodo mas cercano. Luego el más cercano a este. Y asi sucesivamente hasta llegar al punto de destino. En la imagen que figura tras el código se puede apreciar bastante bien.
Vamos a ver el módulo que hemos escrito para expresar esta idea:
unit UNodo;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, ExtCtrls, Math;
type
TNodo = class;
TLinea = class;
TOrdenacion = procedure(Sender: TObject; ANodo:TNodo) of Object;
TMalla = Class(TObject)
private
FPivote: TNodo;
FLineas: TList;
FNodos: TList;
FZona: TForm;
FSalida: TNodo;
FDestino: TNodo;
procedure SetSalida(const Value: TNodo);
function GetLineas(Indice: Integer): TLinea;
function GetNodos(Indice: Integer): TNodo;
procedure InternalOrdenaNodos(Sender: TObject; ANodo: TNodo);
procedure VaciarLineas;
procedure VaciarNodos;
procedure DibujaRuta;
function CalculaMetricaRuta: Double;
protected
procedure DoOrdenaNodos(ANodo: TNodo; AOrdenacion: TOrdenacion); virtual;
procedure DoDibujarMalla; virtual;
procedure OrdenarNodos(ANodo: TNodo; ADestino: TNodo);overload; virtual;
public
FCambios: TStrings;
Constructor Create(AForm: TForm); virtual;
Destructor Destroy; override;
procedure InicializarMalla;
procedure OrdenarNodos; overload;
Function CountLineas: Integer;
Function CountNodos: Integer;
procedure ActualizarMalla;
function AddNodo: Integer;
function AddLinea: Integer;
function GenerarRuta: Double;
property Salida : TNodo read FSalida;
property Destino: TNodo read FDestino;
property Lineas[Indice: Integer]: TLinea read GetLineas;
property Nodos[Indice: Integer]: TNodo read GetNodos;
End;
TLinea = Class(TObject)
private
FMalla: TMalla;
FAlfa: TNodo;
FOmega: TNodo;
FDistancia: Double;
FIndice: Integer;
procedure SetAlfa(const Value: TNodo);
procedure SetOmega(const Value: TNodo);
procedure SetIndice(const Value: Integer);
protected
public
function GetDistancia: Double;
Constructor Create(AMalla: TMalla); virtual;
Destructor Destroy; override;
procedure Enlaza(AAlfa,AOmega: TNodo); overload;
procedure DibujarLinea;
property Alfa: TNodo read FAlfa write SetAlfa;
property Omega: TNodo read FOmega write SetOmega;
property Indice: Integer read FIndice write SetIndice;
End;
TNodo = Class(TObject)
private
FMalla: TMalla;
FShape: TShape;
FPoint: TPoint;
FPeso: Integer;
FTag: Integer;
function GetX: Integer;
procedure SetX(const Value: Integer);
function GetY: Integer;
procedure SetY(const Value: Integer);
procedure SetPeso(const Value: Integer);
procedure SetTag(const Value: Integer);
protected
public
function GetDistancia: Double;
function GetIndice: Integer;
function AddLinea(ANodoTarget: TNodo): Integer;
Constructor Create(AMalla: TMalla); virtual;
Destructor Destroy; override;
procedure DibujarNodo;
property X: Integer read GetX write SetX;
property Y: Integer read GetY write SetY;
property Peso: Integer read FPeso write SetPeso;
property Distancia: Double read GetDistancia;
property Tag: Integer read FTag write SetTag;
End;
implementation
function CalcularDistanciaNodos(AAlfa, AOmega: TNodo): Double;
//Necesitamos dos puntos (x1,y1) (x2,y2)
// [x1,y1] [x2,y2]
// Formula Raiz de ( ((x2-x1) al cuadrado) + ((y2-y1) al cuadrado) )
function CalcularDistancia(X1, Y1, X2, Y2: Integer): Double;
begin
Result:= SQrt(Power((X2-X1), 2) + Power((Y2-Y1), 2));
end;
begin
if (AAlfa = Nil) or (AOmega = Nil) then Result:= 0
else Result:= CalcularDistancia(AAlfa.X, AAlfa.Y, AOmega.X, AOmega.Y);
end;
{ TMalla }
procedure TMalla.ActualizarMalla;
begin
DoDibujarMalla;
end;
function TMalla.AddLinea: Integer;
begin
Result:= FLineas.Add(TLinea.Create(Self));
TLinea(FLineas[Result]).Indice:= Result;
end;
function TMalla.AddNodo: Integer;
begin
Result:= FNodos.Add(TNodo.Create(Self));
end;
constructor TMalla.Create(AForm: TForm);
begin
if AForm = Nil then
Raise Exception.Create('Atención: La referencia no es valida');
FZona:= AForm;
FSalida:= TNodo.Create(Self);
FDestino:= TNodo.Create(Self);
FNodos:= TList.Create;
FLineas:= TList.Create;
end;
destructor TMalla.Destroy;
begin
//limpiamos la lista de nodos
VaciarNodos;
FreeAndNil(FNodos);
//limpiamos la lista de lineas
VaciarLineas;
FreeAndNil(FLineas);
//nos desvinculamos del objeto padre
//sobre el que nos mostramos
FZona:= Nil;
FreeAndNil(FSalida);
FreeAndNil(FDestino);
inherited Destroy;
end;
procedure TMalla.DibujaRuta;
var
i: Integer;
FNodo: TNodo;
begin
VaciarLineas;
fNodo:= Nil;
for i := 0 to CountNodos - 1 do begin
if FNodo <> Nil then begin
FNodo.AddLinea(Nodos[i]);
end
else FSalida.AddLinea(Nodos[i]);
FNodo:= Nodos[i];
end;
FNodo.AddLinea(FDestino);
end;
procedure TMalla.DoDibujarMalla;
var
i: Integer;
begin
if Assigned(FZona) then begin
for i := 0 to CountLineas - 1 do Lineas[i].DibujarLinea;
for i := 0 to FNodos.Count - 1 do Nodos[i].DibujarNodo;
Salida.DibujarNodo;
Destino.DibujarNodo;
end;
end;
procedure TMalla.DoOrdenaNodos(ANodo: TNodo; AOrdenacion: TOrdenacion);
begin
AOrdenacion(Self, ANodo);
end;
function TMalla.GenerarRuta: Double;
begin
if (CountNodos = 0) or (FSalida = Nil) or (FDestino = Nil) then
Raise Exception.Create('Error: No existe suficente información en la ruta a generar');
OrdenarNodos;
DibujaRuta;
Result:= CalculaMetricaRuta;
end;
function TMalla.GetLineas(Indice: Integer): TLinea;
begin
if (Indice < 0) or (Indice > FLineas.Count-1) then
Raise Exception.Create('Error en el valor del indice de la matriz');
Result:= FLineas[Indice];
end;
function TMalla.GetNodos(Indice: Integer): TNodo;
begin
if (Indice < 0) or (Indice > FNodos.Count-1) then
Raise Exception.Create('Error en el valor del indice de la matriz');
Result:= FNodos[Indice];
end;
procedure TMalla.InicializarMalla;
begin
VaciarLineas;
VaciarNodos;
FPivote:= Nil;
end;
procedure TMalla.InternalOrdenaNodos(Sender: TObject; ANodo: TNodo);
procedure OrdenaQuickSort(L,R: Integer);
var
i,j: Integer;
piv, aux: TNodo;
begin
i:= L;
j:= R;
piv:= Nodos[(L+R) div 2]; //pivote
Repeat
while (Nodos[i].GetDistancia < piv.GetDistancia) do Inc(i);
while (piv.GetDistancia < Nodos[j].GetDistancia) do Dec(j);
if i<= j then begin
Aux:= Nodos[i];
FNodos.Exchange(i,j);
FNodos[j]:= Aux;
Inc(i);
Dec(j);
end;
if L<j then OrdenaQuickSort(L,j);
if i<R then OrdenaQuickSort(i,R);
Until i>j;
end;
begin
OrdenaQuickSort(ANodo.GetIndice, CountNodos-1);
end;
procedure TMalla.OrdenarNodos;
var
i: Integer;
begin
FPivote:= FSalida;
for i := 0 to CountNodos - 1 do
OrdenarNodos(Nodos[i], FDestino);
end;
procedure TMalla.OrdenarNodos(ANodo: TNodo; ADestino: TNodo);
var
i: Integer;
begin
//guardamos el indice del vector para que calcule la distancia
//correctamente ya que el pivote debe avancar
i:= ANodo.GetIndice;
DoOrdenaNodos(ANodo, InternalOrdenaNodos);
//en este punto el nodo puede haber cambiado
FPivote:= Nodos[i];
end;
procedure TMalla.SetSalida(const Value: TNodo);
begin
if FSalida = nil then
FSalida := Value;
end;
procedure TMalla.VaciarLineas;
var
i: Integer;
begin
for i := 0 to CountLineas - 1 do begin
TLinea(FLineas[i]).Free;
FLineas[i]:= Nil;
end;
FLineas.Clear;
end;
procedure TMalla.VaciarNodos;
var
i: Integer;
begin
for i := 0 to CountNodos - 1 do begin
TNodo(FNodos[i]).Free;
FNodos[i]:= Nil;
end;
FNodos.Clear;
end;
function TMalla.CalculaMetricaRuta: Double;
var
i: Integer;
begin
Result:= 0;
for i := 0 to CountLineas - 1 do begin
Result:= Result + TLinea(FLineas[i]).GetDistancia;
end;
end;
function TMalla.CountLineas: Integer;
begin
Result:= FLineas.Count;
end;
function TMalla.CountNodos: Integer;
begin
Result:= FNodos.Count;
end;
{TNodo}
procedure TNodo.DibujarNodo;
begin
if not Assigned(Self) then Exit;
if (Self = FMalla.Salida) or
(Self = FMalla.FDestino) then begin
if (Self = FMalla.Salida) then begin
FShape.Brush.Color:= clRed;
FShape.Pen.Color:= clRed;
end
else begin
FShape.Brush.Color:= clBlue;
FShape.Pen.Color:= clBlue;
end;
end
else begin
FShape.Brush.Color:= clLime;
FShape.Pen.Color:= clGreen;
FMalla.FZona.Canvas.Font.Size:= 7;
FMalla.FZona.Canvas.TextOut(X-12,Y-12,'('+InTToStr(GetIndice)+')')
end;
end;
function TNodo.AddLinea(ANodoTarget: TNodo): Integer;
var
fLin: TLinea;
begin
if ANodoTarget = Nil then
Raise Exception.Create('Atención: La referencia al nodo no es valida');
Result:= FMalla.AddLinea;
if Result >= 0 then
FMalla.Lineas[Result].Enlaza(Self, ANodoTarget);
end;
constructor TNodo.Create(AMalla: TMalla);
begin
if AMalla = Nil then
Raise Exception.Create('Atención: La referencia no es valida');
FMalla:= AMalla;
FShape:= TShape.Create(Nil);
FShape.Parent:= AMalla.FZona;
FShape.Shape:= stCircle;
FShape.Height:= 8;
FShape.Width:= 8;
if Self = FMalla.Salida then begin
FShape.Brush.Color:= clRed;
FShape.Pen.Color:= clRed;
end
else begin
FShape.Brush.Color:= clLime;
FShape.Pen.Color:= clGreen;
end;
FPeso:= 0;
x:= 0;
y:= 0;
end;
destructor TNodo.Destroy;
begin
FMalla:= Nil;
FreeAndNil(FShape);
inherited;
end;
function TNodo.GetDistancia: Double;
begin
Result:= CalcularDistanciaNodos(FMalla.FPivote, Self);
end;
function TNodo.GetIndice: Integer;
var
i: Integer;
begin
i:= 0;
while i < FMalla.CountNodos do begin
if FMalla.Nodos[i] = Self then begin
Result:= i;
Exit;
end;
Inc(i);
end;
Result:= -1;
end;
function TNodo.GetX: Integer;
begin
Result:= FPoint.X;
end;
procedure TNodo.SetTag(const Value: Integer);
begin
FTag := Value;
end;
procedure TNodo.SetPeso(const Value: Integer);
begin
FPeso := Value;
end;
procedure TNodo.SetX(const Value: Integer);
begin
FPoint.X := Value;
FShape.Left:= FPoint.X;
end;
function TNodo.GetY: Integer;
begin
Result:= FPoint.Y;
end;
procedure TNodo.SetY(const Value: Integer);
begin
FPoint.Y := Value;
FShape.Top:= FPoint.Y;
end;
{ TLinea }
constructor TLinea.Create(AMalla: TMalla);
begin
FMalla:= AMalla;
FAlfa:= Nil;
FOmega:= Nil;
end;
destructor TLinea.Destroy;
begin
FMalla:= Nil;
inherited;
end;
procedure TLinea.DibujarLinea;
begin
if Assigned(FMalla) then begin
FMalla.FZona.Canvas.MoveTo(FAlfa.X, FAlfa.Y);
FMalla.FZona.Canvas.LineTo(FOmega.X, FOmega.Y);
end;
end;
function TLinea.GetDistancia: Double;
begin
Result:= FDistancia;
end;
procedure TLinea.Enlaza(AAlfa, AOmega: TNodo);
begin
if AAlfa = AOmega then
Raise Exception.Create('No se pueden enlazar dos nodos iguales');
if AAlfa <> FAlfa then FAlfa:= AAlfa;
if AOmega <> FOmega then FOmega:= AOmega;
FDistancia:= CalcularDistanciaNodos(FAlfa, FOmega);
end;
procedure TLinea.SetAlfa(const Value: TNodo);
begin
if Value <> FOmega then FAlfa := Value;
FDistancia:= CalcularDistanciaNodos(FAlfa, FOmega);
end;
procedure TLinea.SetIndice(const Value: Integer);
begin
FIndice := Value;
end;
procedure TLinea.SetOmega(const Value: TNodo);
begin
if Value <> FAlfa then FOmega := Value;
FDistancia:= CalcularDistanciaNodos(FAlfa, FOmega);
end;
end.
Y esta es la imagen, una vez generada la ruta:
El asterisco (*) venía a cuento cuando comentaba que podíais modificar facilmente el ejemplo para que calculara la ruta no en función de recorrer todos los nodos sino aquellos que pudieran hacer menor la distancia. Para ello, quizás bastaría modificar el calculo de la distancia, sobrescribiendo la función virtual
DoOrdenaNodos(ANodo: TNodo; AOrdenacion: TOrdenacion); virtual;
Y entregando como parámetro una nueva función que ademas, tuviera en cuenta no solo la distancia de los dos nodos sino también el calculo con respecto al punto de destino. Y una vez obtenido ese recalculo, compararlo en cada uno de los avances del vecto con el punto final. Podría ser una idea.
Como hicimos en la entrada anterior vamos a intentar destacar algunas ideas importantes que os pueden servir de guia:
* Este es un ejemplo y no deja de serlo aunque calcule un resultado. Os comento ésto porque este resultado puede ser correcto para mi, en el dominio de una aplicación concreta y no ser para otros requerimientos, puesto que no existe realmente una optimización al generar la ruta, ni existen caminos que precondicionen optar por una ruta o por otra. Aqui hemos cogido puntos al azar y nos hemos imaginado la forma de recorrerlos todos.
* Otro punto que parece interesante y por eso lo he incluido así, es el paso de una función como parámetro, que nos permite reutilizar el metodo ante la necesidad de tener en cuenta nuevas condiciones. Para ello, nos basta sobrescribir el método, que es algo realmente sencillo. En este caso concreto, el método tiene un tipo declarado en el interfaz de la unidad UNodos.pas (TOrdenacion = procedure(Sender: TObject; ANodo:TNodo) of Object;)
* Y puede seros de curiosidad, por ejemplo el algoritmo QuickSort, que necesité modificar un tanto para que se reordenara en función de la distancia, como he explicado en lineas anteriores.
* El tratamiento de las listas de punteros (TList) y de las listas de cadenas y como podemos valernos de estas clases para almacenar y manipular referencias a objetos. Es un punto que se reitera continuamente en buena parte del código que podais encontrar, ya que son clases muy básicas.
* Y como siempre, teniendo en cuenta la reutilización. Aunque no lo he comentado, creo que incluso podríamos haber hecho uso del generador de códigos (visto en la entrada anterior), haciendo una ligera modificiación para que nos pudiera calcular distintas combinaciones de nodos y ofrecer a nuestro usuario, la posibilidad de elegir entre varias rutas alternativas.
Con un poco de imaginación quizás no hablariamos de distancia. Es una de las razones que me han hecho añadir la propiedad Peso en el Nodo, aunque luego no le he dado ninguna utilidad. ¿Una combinación de factores, distancia y peso y otros que pudieramos considerar? ¡Hay tantas posibilidades que en nuestro pequeño ejemplo nos hemos intentado quedar con la más didáctica y no enrevesar el código con mayor complejidad que no nos iba a aporatar realmente nada.
Yo creo que podemos dejarlo en este punto. La idea era compartir con vosotros las ventajas de razonar en términos de clases, de intentar en la medida que nos sea posible abstraernos y hacer que nuestro código sea lo mas reutilizable posible. Si bien es cierto que a corto plazo puede ser un inconveniente porque implica un mayor esfuerzo, a largo plazo es rentable, tanto a nivel de reusabilidad como de adaptabilidad a nuevos requerimientos.
Espero que os puedan ayudar estas lineas.
Muy inteesante (como siempre, por otra parte) la entrada Salvador.
Además de las explicaciones, el código resulta muy claro.
Esta entrada es de las que interesa conservar, porque antes o después llega este problema (o relacionado). Hace unos meses, salió en mi empresa un tema relacionado con el cálculo de rutas para repartos (camioneros); Estoy seguro que antes o depués volverá a salir… ;-D
Un saludo.
Gracias Germán.
🙂
Me alegra que se pueda encontrar interesante lo que voy añadiendo al blog. Todos aportamos nuestro granito de arena a esta comunidad.
Un saludo,
Salvador