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. Lists

Shortest Path

Shortest path from one point to another

PreviousShadow AreaNextSolar Analysis

Last updated 4 years ago

//Shortest Path
def ner(st,en,dr,cr:var[]..[])
{
	c1 = List.FilterByBoolMask(cr,st.DistanceTo(cr)==0)["in"];
	e1 = List.Flatten(List.SetDifference(List.Transpose([c1.StartPoint,c1.EndPoint])<1>,st),-1);
	c2 = List.SortByKey(c1, e1.DistanceTo(en))["sorted list"];
	e2 = List.SortByKey(e1, e1.DistanceTo(en))["sorted list"];
	d2 = c2.TangentAtParameter(c2.ParameterAtPoint(e2));

	b2 = Vector.ByTwoPoints(c2.StartPoint,c2.EndPoint).IsParallel(dr);
	c3 = List.IsEmpty(List.FilterByBoolMask(c2,b2)["in"]) ? c2[0] : List.FilterByBoolMask(c2,b2)["in"][0];
	e3 = List.IsEmpty(List.FilterByBoolMask(e2,b2)["in"]) ? e2[0] : List.FilterByBoolMask(e2,b2)["in"][0];
	d3 = c3.TangentAtParameter(c3.ParameterAtPoint(e3));

	return [[c2[0],e2[0],d2[0]],[c3,e3,d3]];
};

def shPh1 (st,en,crvs:var[]..[])
{
	dr = Vector.ByTwoPoints(st,en);
	ds = st.DistanceTo(en);
	shPth1 = [Imperative]
	{
		ph = [];
		ct = 0;
		while (ds > 0)
		{
			cr = ner(st,en,dr,crvs)[0];
			ph[ct] = cr[0];
			st = cr[1];
			dr = cr[2];
			crvs = List.SetDifference(crvs,ph);
			ds = st.DistanceTo(en);
			ct = ct + 1;
		}
		return ph;
	}
	return shPth1;
};

def shPh2 (en1,en2,en,crvs:var[]..[])
{
	cv1 = Math.Sum(shPh1 (en1,en,crvs).Length);
	cv2 = Math.Sum(shPh1 (en2,en,crvs).Length);
	return cv1 >= cv2 ? 1 : 0;
};

def shPh3 (st1,en1,cvs:var[]..[])
{
	return = [Imperative]
	{
		cv1 = ner(st1,en1,Vector.ByTwoPoints(st1,en1),cvs);
		ne1 = cv1[shPh2 (cv1[0][1],cv1[1][1],en1,cvs)];
		ph = [ne1[0]];
		st = ne1[1];
		dr = ne1[2];
		ds = st.DistanceTo(en1);
		ct = 1;

		while (ds > 0)
		{
			cs = List.SetDifference(cvs,ph);
			cr = ner(st,en1,dr,cs);
			ne = cr[shPh2 (cr[0][1],cr[1][1],en1,cs)];
			ph[ct] = ne[0];
			st = ne[1];
			dr = ne[2];
			ds = st.DistanceTo(en1);
			ct = ct + 1;
		}
		return ph;
	}
};

//Sample Grid
a = 0..100..10;
p1 = Point.ByCoordinates(a<1>,a<2>);
p2 = List.Transpose(p1);
p3 = List.DropItems(List.Sublists(p1<1>,0..1,1)<1>,-1);
p4 = List.DropItems(List.Sublists(p2<1>,0..1,1)<1>,-1);
l1 = Line.ByBestFitThroughPoints(List.Flatten([p3,p4],2));

r1 = Rectangle.ByCornerPoints(Point.ByCoordinates([0,0,100,100],[0,100,100,0]));
r2 = Rectangle.ByCornerPoints(Point.ByCoordinates([30,30,70,70],[10,70,70,10]));
s1 = r1.Patch().TrimWithEdgeLoops([r1,r2]);
l2 = List.RemoveIfNot(List.Flatten(l1.Intersect(s1),-1),"Line");
3KB
shrtPth-20191029.zip
archive
Shortest path from one point to another minimizing bends along a grid of curves
Shortest Path without optimizing for bends reduction
Shortest path of specified gradient along topography