Testing Waters
  • Scrapbook
  • Projects
    • Bamiyan Cultural Center
    • Bauhaus Museum
    • Better Hebbal
    • Bicycle Station
    • Cross Laminated Timber
    • Facade
    • Flowing Fabrication
    • Form from Images
    • Guggenheim Helsinki
    • National War Museum
    • National War Memorial
    • Indflorescence
    • Rectangular Compartments
    • Retail Space Layout
    • Noise Barrier : Swedevia Airport
    • Walden
    • Wilson Garden
  • Patterns
    • Area Graph
    • Array along Curve
    • Fibbonacci and Factorial
    • Gyroid
    • Hexagonal Pattern From Image
    • Hexagonal Grid
    • Koch Star
    • Mandelbrot Set
    • Pattern
    • Pattern
    • Pattern
    • Phyllotaxis
    • Random Strip Widths
    • Skewed Surface
    • Staggered Checkerboard
    • Triangle subdivision
    • Vector Field
    • Voronoi
    • Waves
    • Weave
  • Geometry
    • Boundary Curve
    • Bridging parallel curves
    • British Museum Great Court
    • Catenary
    • Delete Adjacent
    • Geodesic Sphere
    • Group Branching Curves
    • Group Circles
    • Group curves
    • K Mean
    • Nurbs Surface Irregular
    • Overlapping Petals
    • Pair Nearest
    • Parametric Shapes
    • Platonic Solids
    • Polyline to PolyArc
    • Roman Surface
    • Sagrada Familia Schools Roof
    • Sine Curve
    • Sine Ribbon
    • Spherical Transformations
    • Split Rectangle
    • Tangential Circle through Point
    • Travelling Salesman Problem
    • Unaligned Bounding Box
  • Lists
    • Alter by Boolean Sequence
    • Color by distance
    • Consecutive Points
    • Distancing
    • Divide Equally
    • Geometry from Image
    • Image based Point Density
    • Isovists
    • Reduce Color Palette
    • Replace Consecutive
    • Replace Multiple
    • Replace Recurring
    • Shadow Area
    • Shortest Path
    • Solar Analysis
    • Topography Analysis
  • Motion
    • Adjacency
    • Animate Sphere
    • Cellular Automation
    • Cloth
    • Hypotrochoid
    • Manakin
    • Rolling Spiral
    • Tan Curve
    • Trammel of Archemedes
    • Image to Integer
  • Articles
    • A Conceptual Approach to Integrating Computational Methods in Early Stage Design
    • Design Script's ambiguous and versatile Replication Guides <1>
    • Design Script's ambiguous and versatile Replication Guides <2>
Powered by GitBook
On this page
  1. Geometry

Travelling Salesman Problem

Connecting a list of points without self intersections

PreviousTangential Circle through PointNextUnaligned Bounding Box

Last updated 3 years ago

// 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))];