Travelling Salesman Problem
Connecting a list of points without self intersections
// Check for Self Intersection
def pgnInt (pts:var[]..[],pnt:var)
{
//Edges with existing points
pg01 = Polygon.ByPoints(pts).Explode();
in01 = 1..List.Count(pg01);
//Distance to New point
ds01 = pnt.DistanceTo(pg01);
//Index of closest edge to new point
in02 = List.SortByKey(in01,ds01)["sortedList"];
//Shift indices of points list
pt01 = List.ShiftIndices(pts,List.FirstItem(-in02));
return [Imperative]
{
bl01 = true;
n = 0;
pt11 = [];
while (bl01)
{
// Shift insertion index
pt10 = List.ShiftIndices(pt01,n);
//Add new point to top of list
pt11 = List.AddItemToFront(pnt,pt10);
pg11 = Polygon.ByPoints(pt11);
//Check Self Intersection
it11 = pg11.SelfIntersections();
n = n + 1;
bl01 = List.Count(it11) != 0;
}
return pt11;
}
};
// Add Closest Neighbour
def clsNgh (pnt:var[]..[])
{
occ = pnt[0];
avl = pnt[1];
pg01 = Polygon.ByPoints(occ);
ds01 = pg01.DistanceTo(avl);
pt01 = List.SortByKey(avl,ds01)["sortedList"];
pt02 = List.FirstItem(pt01);
pt03 = List.RestOfItems(pt01);
pt04 = pgnInt (occ,pt02);
return [pt04,pt03];
};
// Repeat until all points are included
def tsp (pt01:var[]..[])
{
ds01 = List.FirstItem(pt01).DistanceTo(pt01);
pt02 = List.SortByKey(pt01,ds01)["sortedList"];
pt11 = [List.TakeItems(pt02,3),List.DropItems(pt02,3)];
return [Imperative]
{
a = [];
c = List.Count(pt11[1]);
while (c > 0)
{
a = clsNgh (pt11);
pt11 = a;
c = c - 1;
}
return a[0];
};
};
// Implementation on lists of Random points
n = [25,50,75,100];
pt01 = Point.ByCoordinates
(Math.RandomList(n)*8000,Math.RandomList(n)*6000);
pt02 =tsp(pt01<1>);
[pt02[0],GeometryColor.ByGeometryColor
(Polygon.ByPoints(pt02[0]),Color.ByARGB(255,255,0,0))];
[pt02[1],GeometryColor.ByGeometryColor
(Polygon.ByPoints(pt02[1]),Color.ByARGB(255,0,255,0))];
[pt02[2],GeometryColor.ByGeometryColor
(Polygon.ByPoints(pt02[2]),Color.ByARGB(255,0,0,255))];
[pt02[3],GeometryColor.ByGeometryColor
(Polygon.ByPoints(pt02[3]),Color.ByARGB(255,255,0,250))];