Travelling Salesman Problem

1
// Check for Self Intersection
2
def pgnInt (pts:var[]..[],pnt:var)
3
{
4
	//Edges with existing points
5
	pg01 = Polygon.ByPoints(pts).Explode();
6
	in01 = 1..List.Count(pg01);
7
	//Distance to New point
8
	ds01 = pnt.DistanceTo(pg01);
9
	//Index of closest edge to new point
10
	in02 = List.SortByKey(in01,ds01)["sortedList"];
11
	//Shift indices of points list
12
	pt01 = List.ShiftIndices(pts,List.FirstItem(-in02));
13
​
14
​
15
	return [Imperative]
16
	{
17
		bl01 = true;
18
		n = 0;
19
		pt11 = [];
20
​
21
		while (bl01)
22
		{
23
			// Shift insertion index
24
			pt10 = List.ShiftIndices(pt01,n);
25
			//Add new point to top of list
26
			pt11 = List.AddItemToFront(pnt,pt10);
27
			pg11 = Polygon.ByPoints(pt11);
28
			//Check Self Intersection
29
			it11 = pg11.SelfIntersections();
30
			n = n + 1;
31
			bl01 = List.Count(it11) != 0;
32
		}
33
		return pt11;
34
	}
35
};
36
​
37
// Add Closest Neighbour
38
def clsNgh (pnt:var[]..[])
39
{
40
	occ = pnt[0];
41
	avl = pnt[1];
42
	pg01 = Polygon.ByPoints(occ);
43
	ds01 = pg01.DistanceTo(avl);
44
	pt01 = List.SortByKey(avl,ds01)["sortedList"];
45
	pt02 = List.FirstItem(pt01);
46
	pt03 = List.RestOfItems(pt01);
47
	pt04 = pgnInt (occ,pt02);
48
	return [pt04,pt03];
49
};
50
​
51
// Repeat until all points are included
52
def tsp (pt01:var[]..[])
53
{
54
	ds01 = List.FirstItem(pt01).DistanceTo(pt01);
55
	pt02 = List.SortByKey(pt01,ds01)["sortedList"];
56
	pt11 = [List.TakeItems(pt02,3),List.DropItems(pt02,3)];
57
	return [Imperative]
58
	{
59
		a = [];
60
		c = List.Count(pt11[1]);
61
		while (c > 0)
62
		{
63
			a = clsNgh (pt11);
64
			pt11 = a;
65
			c = c - 1;
66
		}
67
		return a[0];
68
};
69
};
70
​
71
​
72
// Implementation on lists of Random points
73
n = [25,50,75,100];
74
​
75
pt01 = Point.ByCoordinates
76
(Math.RandomList(n)*8000,Math.RandomList(n)*6000);
77
​
78
pt02 =tsp(pt01<1>);
79
[pt02[0],GeometryColor.ByGeometryColor
80
(Polygon.ByPoints(pt02[0]),Color.ByARGB(255,255,0,0))];
81
[pt02[1],GeometryColor.ByGeometryColor
82
(Polygon.ByPoints(pt02[1]),Color.ByARGB(255,0,255,0))];
83
[pt02[2],GeometryColor.ByGeometryColor
84
(Polygon.ByPoints(pt02[2]),Color.ByARGB(255,0,0,255))];
85
[pt02[3],GeometryColor.ByGeometryColor
86
(Polygon.ByPoints(pt02[3]),Color.ByARGB(255,255,0,250))];
Copied!

Geometry - Previous

Tangential Circle through Point

Next - Geometry

Unaligned Bounding Box

Last modified 8mo ago

Copy link