* Estructura del proyecto:
Para añadir un nuevo package al proyecto, botón derecho del mouse sobre "Source Packages" - New - Java Package - Package Name: Utilidades.
Código (Ruta.java):
package Tsp;
import Utilidades.Mostrar;
import Utilidades.BuscarRuta;
public class Ruta {
public static void main(String[] args) {
Mostrar m = new Mostrar();
BuscarRuta br = new BuscarRuta();
//Coordenadas cartesianas (x,y)
double[][] coordenadas_XY = {
{20, 18, 22, 13, 3, 18, 30, 5, 14, 26, 23}, // X
{3, 26, 27, 31, 32, 37, 35, 42, 52, 45, 12}}; // Y
int nodos = coordenadas_XY[0].length;
double[] ruta = new double[nodos];
//Ruta
for (int i = 0; i < br.getRuta(coordenadas_XY).size(); i++) {
if (!br.getRuta(coordenadas_XY).contains(ruta[i])) {
ruta[i] = br.getRuta(coordenadas_XY).get(i);
}
}
//Muestreos
m.mostrarCoordenadas(coordenadas_XY);
m.mostrarRuta(ruta, "\nRuta:\n");
}
}
Código (Angulo.java):
package Utilidades;
public class Angulo {
public double getAngle(double x, double y, double x2, double y2, double px, double py, double px2, double py2) {
double pendent1, pendent2, radians, graus;
pendent1 = (y2 - y) / (x2 - x);
pendent2 = (py2 - py) / (px2 - px);
radians = Math.atan((pendent2 - pendent1) / (1 + (pendent2 * pendent1)));
graus = (180 * radians) / Math.PI;
//cuadrante4
if (px2 >= x && py2 <= y) {
graus = 360 + graus;
if (px2 == x) {
graus = 270;
}
if (py2 == y) {
graus = 360;
}
}
//cuadrante3
if (px2 <= x && py2 <= y) {
graus = 180 + graus;
if (px2 == x) {
graus = 270;
}
if (py2 == y) {
graus = 180;
}
}
//cuadrante2
if (px2 <= x && py2 >= y) {
graus = 180 + graus;
if (px2 == x) {
graus = 90;
}
if (py2 == y) {
graus = 180;
}
}
//cuadrante1
if (px2 >= x && py2 >= y) {
if (px2 == x) {
graus = 90;
}
if (py2 == y) {
graus = 0;
}
}
return graus;
}
}
Código (BuscarRuta.java):
package Utilidades;
import java.util.ArrayList;
import java.util.List;
public class BuscarRuta {
public List<Integer> getRuta(double[][] xy) {
Ordenar orden = new Ordenar();
double[] base;
double[][] tg = new double[xy.length][xy[0].length];
double graus = 1;
int id;
base = BuscarMinY(xy);
List<Integer> lista = new ArrayList<>();
lista.add((int) base[2]);
Angulo grau = new Angulo();
while (true) {
for (int i = 0; i < xy[0].length; i++) {
tg[0][i] = i;
tg[1][i] = grau.getAngle(
base[0], base[1], base[0] + 1, base[1], //base
base[0], base[1], xy[0][i], xy[1][i]);
}
//descarta angulos inferiores
for (int i = 0; i < tg[0].length; i++) {
if (tg[1][i] < graus) {
tg[1][i] = 999;
}
}
tg = orden.getOrdenacio(tg);
graus = tg[1][0];
if (graus >= 999) {
break;
}
id = (int) tg[0][0];
lista.add(id);
base[0] = xy[0][id];
base[1] = xy[1][id];
}
return lista;
}
public double[] BuscarMinY(double[][] xy) {
double[] pos_max = new double[3];
double max = 9999;
for (int i = 0; i < xy[0].length; i++) {
if (xy[1][i] < max) {
max = xy[1][i];
pos_max[0] = xy[0][i];
pos_max[1] = xy[1][i];
pos_max[2] = i;
}
}
return pos_max;
}
}
Código (Mostrar.java):
package Utilidades;
public class Mostrar {
public String nodos = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
public void mostrarCoordenadas(double[][] t1) {
char nodo;
int x, y;
System.out.println("Coordenadas nodos (x,y):");
for (int i = 0; i < t1[0].length; i++) {
nodo = nodos.charAt(i);
x = (int) t1[0][i];
y = (int) t1[1][i];
System.out.println(nodo + " [" + x + ", " + y + "]");
}
}
public void mostrarRuta(double[] az, String msg) {
String aux = "";
String aux2;
for (int i = 0; i < az.length; i++) {
aux2 = "" + nodos.charAt((int) az[i]);
//evitar nodos repetidos
if (!aux.contains(aux2)) {
aux += " ? " + aux2;
}
}
System.out.println(msg + aux + " ?");
}
}
Código (Ordenar.java):
package Utilidades;
public class Ordenar {
public double[][] getOrdenacio(double[][] xy) {
double [][] t = xy;
//ordenar de menor a mayor
int cont = 0;
double aux;
while (cont < t[0].length) {
for (int i = 0; i < t[0].length - 1; i++) {
if (t[1][i] > t[1][i + 1]) {
aux = t[1][i];
t[1][i] = t[1][i + 1];
t[1][i + 1] = aux;
aux = t[0][i];
t[0][i] = t[0][i + 1];
t[0][i + 1] = aux;
cont = 1;
}
cont++;
}
}
return t;
}
}
Resultado:
run:
Coordenadas nodos (x,y):
A [20, 3]
B [18, 26]
C [22, 27]
D [13, 31]
E [3, 32]
F [18, 37]
G [30, 35]
H [5, 42]
I [14, 52]
J [26, 45]
K [23, 12]
Ruta:
? A ? K ? G ? J ? I ? H ? E ?
BUILD SUCCESSFUL (total time: 0 seconds)
