/**========================================================================
=== Fichier : DisplayTsp.java
=== Fonction : Affichage du résultat du problème du voyageur de commerce
=== Version : 0.37
=== Ecrit le : 28/12/2002 (derniere mise a jour)
=== Auteurs : Alexandre AUPETIT et Xavier CLARIST
=== Licence : GPL (logiciel libre)
=========================================================================*/
import java.applet.Applet;
import java.awt.Graphics;
import java.awt.event.*;
import java.net.URL; // pour la recuperation des parametres
import java.awt.*;
import java.util.StringTokenizer;
import java.util.NoSuchElementException;
/*========================================================================
Classe : Affichage d'un problème du voyageur de commerce
==========================================================================*/
public class DisplayTsp extends java.applet.Applet
{
int iMaxX;
int iMaxY;
double fPasX;
double fPasY;
double fXMinFen,fXMaxFen,fYMinFen,fYMaxFen;
int iXClick;
int iYClick;
double fXCentreEcran, fYCentreEcran;
double dernierXCentreEcran, dernierYCentreEcran;
double lfFacteurZoom;
double diff;
double diffX;
double diffY;
double dernierZoom;
boolean bZoom;
double CitiesPosX[];
double CitiesPosY[];
int Parcours[];
int Parcours2[];
int Parcours3[];
boolean bParcours2AAfficher;
boolean bParcours3AAfficher;
boolean bShowCityNumber;
double distance;
double distance2;
double distance3;
int iNbCities;
double d;
int mode, nbmode;
int iType;
double fMinParcours, fMaxParcours;
/*========================================================================
Fonction : Initialisation de l'applet et récupération des paramètres
==========================================================================*/
public void init()
{
int i;
String sParam;
String sCityPosX;
String sCityPosY;
System.out.println(getAppletInfo());
iMaxX = size().width;
iMaxY = size().height;
// type de problème : tsplib (int) ou alex (double)
sParam = getParameter("ProblemType");
iType=0;
try {
if ( sParam.equals("tsplib") || sParam.equals("int") || sParam.equals("TSPlib") ) {
iType=1;
}
} catch (Exception e) {
iType=0;
}
//
sParam = getParameter("ShowCityNumber");
bShowCityNumber=false;
try {
if ( sParam.equals("true") || sParam.equals("TRUE") ) {
bShowCityNumber=true;
}
} catch (Exception e) {
bShowCityNumber=false;
}
// Problème personnalisé (Nb de villes et postitions paramétrables)
sParam = getParameter("Problem");
if (sParam.equals("custom"))
{
sParam = getParameter("NbCities");
iNbCities = (Integer.valueOf(sParam)).intValue();
System.out.println("NbCities=" + iNbCities);
sCityPosX = getParameter("CitiesPosX");
sCityPosY = getParameter("CitiesPosY");
}
// Problème par défaut de 250 villes
else
{
iNbCities = 250;
sCityPosX = "0.22312;0.44756;0.56937;0.47492;0.95404;0.15392;0.18974;0.62258;0.08402;0.96130;0.77813;0.79242;0.43972;0.82812;0.73679;0.84150;0.46119;0.45252;0.76285;0.06421;0.88594;0.97797;0.57890;0.24255;0.19040;0.87224;0.70068;0.91345;0.16925;0.03785;0.98596;0.86594;0.16841;0.47770;0.24590;0.64814;0.76005;0.20752;0.22667;0.00188;0.65393;0.38558;0.53878;0.49500;0.04061;0.61406;0.41220;0.47372;0.79846;0.51186;0.49334;0.17619;0.78612;0.59234;0.83379;0.42984;0.46834;0.84232;0.11446;0.71516;0.87016;0.18163;0.80922;0.86296;0.60678;0.65203;0.53483;0.35351;0.21194;0.33372;0.54007;0.53345;0.57899;0.01553;0.71309;0.84852;0.05991;0.86561;0.68550;0.47681;0.10340;0.39240;0.95707;0.95916;0.69176;0.21475;0.05645;0.24024;0.12397;0.32890;0.98646;0.42031;0.20756;0.91550;0.01449;0.18534;0.52115;0.75611;0.32366;0.64723;0.00816;0.24724;0.61018;0.70006;0.74325;0.57121;0.20636;0.77607;0.27743;0.30699;0.08388;0.40981;0.07008;0.08325;0.88119;0.40915;0.59247;0.95396;0.14387;0.93680;0.68297;0.61682;0.49952;0.30326;0.08447;0.06887;0.10258;0.77338;0.64459;0.56639;0.58712;0.41512;0.63192;0.38224;0.02310;0.66290;0.82705;0.59540;0.67261;0.10352;0.50891;0.92542;0.65106;0.78415;0.55544;0.82142;0.32606;0.32214;0.60563;0.73377;0.02341;0.33479;0.67638;0.17703;0.82886;0.10607;0.45293;0.94926;0.73029;0.39964;0.08394;0.42828;0.45761;0.36799;0.45480;0.69195;0.49842;0.32867;0.95694;0.52380;0.78624;0.12358;0.66135;0.34316;0.80625;0.67737;0.96386;0.30019;0.85607;0.48470;0.76993;0.78908;0.20340;0.44316;0.62345;0.94615;0.59683;0.64887;0.14256;0.64982;0.73483;0.83900;0.43285;0.12016;0.80736;0.59979;0.78151;0.84565;0.50662;0.14525;0.25578;0.53977;0.16112;0.11079;0.18067;0.25249;0.08780;0.61420;0.23068;0.80957;0.33922;0.61534;0.79823;0.10564;0.74981;0.43492;0.34229;0.85820;0.16333;0.80710;0.72960;0.25950;0.15108;0.33805;0.60806;0.41980;0.55698;0.06802;0.49613;0.66005;0.42456;0.25154;0.06966;0.27027;0.07873;0.57699;0.13695;0.62573;0.71019;0.66978;0.11141;0.26554;0.12472;0.02360;0.50723;0.86680;0.77863;0.69864;0.22808;0.08128;";
sCityPosY = "0.21680;0.49262;0.47379;0.03366;0.95850;0.26108;0.36078;0.16687;0.58984;0.20932;0.49682;0.94493;0.50458;0.89746;0.24439;0.95990;0.28906;0.03055;0.92744;0.71689;0.21813;0.07568;0.60055;0.66293;0.20385;0.96852;0.66466;0.14039;0.74157;0.90603;0.87935;0.44715;0.31846;0.93126;0.54192;0.13184;0.62611;0.33895;0.45007;0.41706;0.87412;0.35460;0.29903;0.70803;0.53285;0.02657;0.48000;0.58060;0.95142;0.04436;0.16000;0.25339;0.38372;0.01278;0.59422;0.48772;0.81543;0.00713;0.33732;0.15506;0.32922;0.28236;0.65535;0.60768;0.37482;0.10012;0.82823;0.32094;0.94585;0.04573;0.76357;0.00841;0.37577;0.69345;0.73069;0.58325;0.03015;0.86913;0.72857;0.29228;0.12884;0.63822;0.74591;0.16901;0.29289;0.23183;0.74820;0.63544;0.25577;0.83706;0.17741;0.04637;0.28592;0.89306;0.39231;0.11789;0.57774;0.47822;0.71527;0.01542;0.86198;0.06461;0.48748;0.73415;0.02895;0.72971;0.99151;0.41392;0.69157;0.29192;0.49233;0.60503;0.16591;0.39373;0.73049;0.88935;0.65639;0.20265;0.65402;0.88711;0.50801;0.88934;0.39289;0.77695;0.61025;0.16835;0.47867;0.17265;0.85663;0.52578;0.97553;0.17959;0.36908;0.77579;0.31904;0.70607;0.27972;0.32657;0.89866;0.75707;0.17239;0.61149;0.69880;0.29565;0.35053;0.14255;0.23654;0.95798;0.70438;0.62872;0.39667;0.85046;0.93020;0.34899;0.28054;0.33777;0.03149;0.10399;0.73341;0.28573;0.22106;0.41000;0.75042;0.06323;0.10176;0.47821;0.02675;0.17481;0.50570;0.78580;0.62986;0.23917;0.07284;0.39164;0.74280;0.89019;0.10565;0.42147;0.66818;0.31087;0.17665;0.26836;0.11775;0.16034;0.96696;0.40970;0.06972;0.25818;0.99203;0.94881;0.32719;0.69869;0.13919;0.28892;0.60486;0.57730;0.38887;0.98491;0.28882;0.13007;0.09140;0.85261;0.18864;0.30368;0.76061;0.91551;0.09149;0.52065;0.73436;0.03804;0.40936;0.12073;0.46099;0.30485;0.25090;0.00559;0.97469;0.50341;0.96899;0.34400;0.05959;0.81740;0.87370;0.38176;0.14762;0.94729;0.03514;0.35521;0.17366;0.24595;0.09497;0.76685;0.10974;0.23299;0.07736;0.80833;0.83649;0.28803;0.96379;0.31826;0.08958;0.66839;0.33356;0.62085;0.68365;0.93179;0.11834;0.84829;0.96891;0.30682;";
}
// Position des villes
CitiesPosX = new double[iNbCities];
CitiesPosY = new double[iNbCities];
StringTokenizer stPosX = new StringTokenizer(sCityPosX, ";");
for (i=0; i<iNbCities; i++)
{
CitiesPosX[i] = (Double.valueOf(stPosX.nextToken())).doubleValue();
}
StringTokenizer stPosY = new StringTokenizer(sCityPosY, ";");
for (i=0; i<iNbCities; i++)
{
CitiesPosY[i] = (Double.valueOf(stPosY.nextToken())).doubleValue();
}
// Parcours (trajet) entre les villes
sParam = getParameter("Parcours");
Parcours = new int[iNbCities];
StringTokenizer stParcours = new StringTokenizer(sParam, "-");
try {
for (i=0; i<iNbCities; i++)
{
Parcours[i] = (Integer.valueOf(stParcours.nextToken())).intValue();
}
// si le parcours n'est pas complet
} catch (NoSuchElementException e0) {
for (; i<iNbCities; i++)
{
Parcours[i] = Parcours[i-1];
}
}
nbmode=1;
sParam = getParameter("Parcours2");
try
{
bParcours2AAfficher = !(sParam.equals(""));
if (bParcours2AAfficher)
{
nbmode=2;
Parcours2 = new int[iNbCities];
StringTokenizer stParcours2 = new StringTokenizer(sParam, "-");
for (i=0; i<iNbCities; i++)
{
Parcours2[i] = (Integer.valueOf(stParcours2.nextToken())).intValue();
}
}
}
catch (Exception e)
{
bParcours2AAfficher = false;
}
sParam = getParameter("Parcours3");
try
{
bParcours3AAfficher = !(sParam.equals(""));
if (bParcours3AAfficher)
{
nbmode=3;
Parcours3 = new int[iNbCities];
StringTokenizer stParcours3 = new StringTokenizer(sParam, "-");
for (i=0; i<iNbCities; i++)
{
Parcours3[i] = (Integer.valueOf(stParcours3.nextToken())).intValue();
}
}
}
catch (Exception e)
{
bParcours3AAfficher = false;
}
CalculeDistance();
CalculeFenetre();
System.out.println("Fenetre : " + fMinParcours + " " + fMaxParcours + " " + fMinParcours + " " + fMaxParcours);
DefFenetre(fMinParcours, fMinParcours, fMaxParcours, fMaxParcours);
fXCentreEcran = (fMinParcours + fMaxParcours)/2;
fYCentreEcran = fXCentreEcran;
dernierXCentreEcran = fXCentreEcran;
dernierYCentreEcran = fYCentreEcran;
lfFacteurZoom = (fMaxParcours - fMinParcours)/2;
dernierZoom = lfFacteurZoom;
bZoom = false;
}
/*========================================================================
Fonction : Définition de la résolution la fenêtre d'affichage
==========================================================================*/
public void DefFenetre(double x0, double y0, double x1, double y1)
{
fXMinFen = x0;
fXMaxFen = x1;
fYMinFen = y0;
fYMaxFen = y1;
fPasX = (double)Math.abs(fXMinFen-fXMaxFen)/(double)iMaxX;
fPasY = (double)Math.abs(fYMinFen-fYMaxFen)/(double)iMaxY;
}
/*========================================================================
Fonction : Dessine un "point" de 2x2 pixels
==========================================================================*/
public void TracePoint(Graphics g, double x, double y, int i)
{
int x0, y0, x1, y1;
x0 = (int)((x-fXMinFen)/(fXMaxFen-fXMinFen)*iMaxX);
y0 = (int)(iMaxY-(y-fYMinFen)/(fYMaxFen-fYMinFen)*iMaxY);
g.fillRect(x0-1, y0-1, 2, 2);
if (bShowCityNumber) {
// TSPLIB
if (iType == 1) {
g.drawString(""+i+1, x0+2, y0-2);
} else { // Alex
g.drawString(""+i, x0+2, y0-2);
}
}
}
/*========================================================================
Fonction : Dessine une ligne entre deux points
==========================================================================*/
public void TraceLigne(Graphics g, double x0, double y0, double x, double y)
{
if ( (x0 != x) || (y0 != y) ) {
g.drawLine( (int)((x0-fXMinFen)/(fXMaxFen-fXMinFen)*iMaxX),(int)(iMaxY-(y0-fYMinFen)/(fYMaxFen-fYMinFen)*iMaxY),
(int)((x-fXMinFen)/(fXMaxFen-fXMinFen)*iMaxX),(int)(iMaxY-(y-fYMinFen)/(fYMaxFen-fYMinFen)*iMaxY));
}
}
/*========================================================================
Fonction : Affichage de l'applet
==========================================================================*/
public void paint(Graphics g)
{
int i;
//g.setBackground(Color.white);
// Tracé du contour de l'applet
g.setColor(Color.black);
g.drawRect(0, 0, iMaxX-1, iMaxY-1);
// Tracé du parcours (trajet) entre les villes
if ( (bParcours3AAfficher) && ((mode==0) || (mode==3)) )
{
if (mode == 0)
{
g.setColor(Color.magenta);
}
else
{
g.setColor(Color.blue);
}
for (i=0; i<iNbCities - 1; i++)
{
TraceLigne(g, CitiesPosX[Parcours3[i]], CitiesPosY[Parcours3[i]],
CitiesPosX[Parcours3[i+1]], CitiesPosY[Parcours3[i+1]] );
}
TraceLigne(g, CitiesPosX[Parcours3[iNbCities-1]], CitiesPosY[Parcours3[iNbCities-1]],
CitiesPosX[Parcours3[0]], CitiesPosY[Parcours3[0]] );
}
if ( (bParcours2AAfficher) && ((mode==0) || (mode==2)) )
{
if (mode == 0)
{
g.setColor(Color.green);
}
else
{
g.setColor(Color.blue);
}
for (i=0; i<iNbCities - 1; i++)
{
TraceLigne(g, CitiesPosX[Parcours2[i]], CitiesPosY[Parcours2[i]],
CitiesPosX[Parcours2[i+1]], CitiesPosY[Parcours2[i+1]] );
}
TraceLigne(g, CitiesPosX[Parcours2[iNbCities-1]], CitiesPosY[Parcours2[iNbCities-1]],
CitiesPosX[Parcours2[0]], CitiesPosY[Parcours2[0]] );
}
if ( (mode==0) || (mode==1) )
{
g.setColor(Color.blue);
for (i=0; i<iNbCities - 1; i++)
{
TraceLigne(g, CitiesPosX[Parcours[i]], CitiesPosY[Parcours[i]],
CitiesPosX[Parcours[i+1]], CitiesPosY[Parcours[i+1]] );
}
TraceLigne(g, CitiesPosX[Parcours[iNbCities-1]], CitiesPosY[Parcours[iNbCities-1]],
CitiesPosX[Parcours[0]], CitiesPosY[Parcours[0]] );
}
if (!bZoom)
{
// Tracé des villes
g.setColor(Color.red);
for (i=0; i<iNbCities; i++)
{
TracePoint(g, CitiesPosX[i], CitiesPosY[i], i);
}
// Distance totale
g.setColor(Color.black);
if ( (bParcours3AAfficher) && (mode==3) ) {
g.drawString("d = " + distance3, 5, iMaxY - 10);
}
if ( (bParcours2AAfficher) && (mode==2) ) {
g.drawString("d = " + distance2, 5, iMaxY - 10);
}
if ( (mode==0) || (mode==1) ) {
g.drawString("d = " + distance, 5, iMaxY - 10);
}
}
// tracé du "X" de zoom
if (bZoom)
{
if (diff < 0)
{
g.setColor(Color.red);
}
TraceLigne(g, fXCentreEcran-diff/5, fYCentreEcran-diff/5, fXCentreEcran+diff/5, fYCentreEcran+diff/5);
TraceLigne(g, fXCentreEcran+diff/5, fYCentreEcran-diff/5, fXCentreEcran-diff/5, fYCentreEcran+diff/5);
// Debug
//g.setColor(Color.black);
//g.drawString("diff=" + diff + " diffX=" + diffX + " Z=" + lfFacteurZoom, 5, iMaxY - 10);
}
}
/*========================================================================
Fonction : Calcul de la distance totale
==========================================================================*/
public void CalculeDistance()
{
distance = CalcDist(Parcours);
if (bParcours2AAfficher) {
distance2 = CalcDist(Parcours2);
}
if (bParcours3AAfficher) {
distance3 = CalcDist(Parcours3);
}
}
/*========================================================================
Fonction : Calcul de la distance totale
==========================================================================*/
public double CalcDist(int MonParcours[])
{
int i;
long l;
d = 0;
for (i=0; i<iNbCities-1; i++)
{
if (iType == 0) {
d += Math.sqrt( (CitiesPosX[MonParcours[i]]-CitiesPosX[MonParcours[i+1]])*(CitiesPosX[MonParcours[i]]-CitiesPosX[MonParcours[i+1]])
+ (CitiesPosY[MonParcours[i]]-CitiesPosY[MonParcours[i+1]])*(CitiesPosY[MonParcours[i]]-CitiesPosY[MonParcours[i+1]]) );
} else {
d += (double) (int) (Math.sqrt( (CitiesPosX[MonParcours[i]]-CitiesPosX[MonParcours[i+1]])*(CitiesPosX[MonParcours[i]]-CitiesPosX[MonParcours[i+1]])
+ (CitiesPosY[MonParcours[i]]-CitiesPosY[MonParcours[i+1]])*(CitiesPosY[MonParcours[i]]-CitiesPosY[MonParcours[i+1]]) ) +0.5);
}
}
if (iType == 0) {
d += Math.sqrt( (CitiesPosX[MonParcours[iNbCities-1]]-CitiesPosX[MonParcours[0]])*(CitiesPosX[MonParcours[iNbCities-1]]-CitiesPosX[MonParcours[0]])
+ (CitiesPosY[MonParcours[iNbCities-1]]-CitiesPosY[MonParcours[0]])*(CitiesPosY[MonParcours[iNbCities-1]]-CitiesPosY[MonParcours[0]]) );
} else {
d += (double) (int) (Math.sqrt( (CitiesPosX[MonParcours[iNbCities-1]]-CitiesPosX[MonParcours[0]])*(CitiesPosX[MonParcours[iNbCities-1]]-CitiesPosX[MonParcours[0]])
+ (CitiesPosY[MonParcours[iNbCities-1]]-CitiesPosY[MonParcours[0]])*(CitiesPosY[MonParcours[iNbCities-1]]-CitiesPosY[MonParcours[0]]) ) +0.5);
}
//arrondi
l = (long) (d * 10000);
return (double)( (double)(l) / (double)10000 );
}
/*========================================================================
Fonction : Calcul les bords de la fenêtre initiale par rapport à la position des points
==========================================================================*/
public void CalculeFenetre()
{
int i;
fMinParcours = CitiesPosX[0];
fMaxParcours = CitiesPosX[0];
for (i=0; i<iNbCities-1; i++)
{
if (CitiesPosX[i] > fMaxParcours)
{
fMaxParcours = CitiesPosX[i];
}
if (CitiesPosY[i] > fMaxParcours)
{
fMaxParcours = CitiesPosY[i];
}
if (CitiesPosX[i] < fMinParcours)
{
fMinParcours = CitiesPosX[i];
}
if (CitiesPosY[i] < fMinParcours)
{
fMinParcours = CitiesPosY[i];
}
}
fMinParcours -= (fMaxParcours - fMinParcours)/25;
fMaxParcours += (fMaxParcours - fMinParcours)/25;
}
/*========================================================================
Fonction :
==========================================================================*/
public boolean mouseDown(Event event, int x, int y)
{
if (!bZoom)
{
iXClick = x;
iYClick = y;
}
return false;
}
/*========================================================================
Fonction :
==========================================================================*/
public boolean mouseDrag(Event event, int x, int y)
{
// si clic droit
bZoom = (event.modifiers == event.META_MASK);
boolean bOk = true;
diffX = ((double)(x-iXClick)/(double)(iMaxX));
diffY = ((double)(y-iYClick)/(double)(iMaxY));
if ( (Math.abs(x-iXClick) < iMaxX) )
{
if (bZoom)
{
diff = diffX*dernierZoom*2;
if ((dernierZoom - diff > 0.1*lfFacteurZoom) && (dernierZoom - diff <10*lfFacteurZoom))
{
lfFacteurZoom = dernierZoom - diff;
}
else
{
bOk = false;
}
}
else
{
fXCentreEcran = dernierXCentreEcran - diffX*(double)Math.abs(fXMinFen-fXMaxFen);
fYCentreEcran = dernierYCentreEcran + diffY*(double)Math.abs(fYMinFen-fYMaxFen);
}
if (bOk)
{
DefFenetre(fXCentreEcran-lfFacteurZoom, fYCentreEcran-lfFacteurZoom, fXCentreEcran+lfFacteurZoom, fYCentreEcran+lfFacteurZoom );
repaint();
}
}
return false;
}
/*========================================================================
Fonction :
==========================================================================*/
public boolean mouseUp(Event evt, int x, int y)
{
mode++;
if (mode > nbmode)
{
mode=0;
}
dernierZoom = lfFacteurZoom;
bZoom = false;
dernierXCentreEcran = fXCentreEcran;
dernierYCentreEcran = fYCentreEcran;
DefFenetre(fXCentreEcran-lfFacteurZoom, fYCentreEcran-lfFacteurZoom, fXCentreEcran+lfFacteurZoom, fYCentreEcran+lfFacteurZoom );
repaint();
return false;
}
/*========================================================================
Fonction : Info sur l'applet
==========================================================================*/
public String getAppletInfo()
{
return "DisplayTsp v 0.37 - Affichage d'un parcours pour le problème du voyageur du commerce - Alexandre Aupetit et Xavier Clarist, décembre 2003 - Logiciel libre sous licence GPL";
}
/*========================================================================
=== Fonction : Info sur les parametres de l'applet
=========================================================================*/
public String[][] getParameterInfo()
{
String[][] aasArgs =
{
{"Problem", "String", "default = problème par défaut de 250 villes, custom = autres problèmes"},
{"CitiesPosX", "String", "Position en X des villes. Exemple : 0.21679;0.49261;... "},
{"CitiesPosX", "String", "Position en Y des villes. Exemple : 0.21679;0.49261;... "},
{"Parcours", "String", "liste des villes visitées"},
};
return aasArgs;
}
}