Shortest Path
Shortest path from one point to another
Shortest path from one point to another minimizing bends along a grid of curves
shrtPth-20191029.zip
3KB
Binary
Shortest Path without optimizing for bends reduction
1
//Shortest Path
2
def ner(st,en,dr,cr:var[]..[])
3
{
4
c1 = List.FilterByBoolMask(cr,st.DistanceTo(cr)==0)["in"];
5
e1 = List.Flatten(List.SetDifference(List.Transpose([c1.StartPoint,c1.EndPoint])<1>,st),-1);
6
c2 = List.SortByKey(c1, e1.DistanceTo(en))["sorted list"];
7
e2 = List.SortByKey(e1, e1.DistanceTo(en))["sorted list"];
8
d2 = c2.TangentAtParameter(c2.ParameterAtPoint(e2));
9
10
b2 = Vector.ByTwoPoints(c2.StartPoint,c2.EndPoint).IsParallel(dr);
11
c3 = List.IsEmpty(List.FilterByBoolMask(c2,b2)["in"]) ? c2[0] : List.FilterByBoolMask(c2,b2)["in"][0];
12
e3 = List.IsEmpty(List.FilterByBoolMask(e2,b2)["in"]) ? e2[0] : List.FilterByBoolMask(e2,b2)["in"][0];
13
d3 = c3.TangentAtParameter(c3.ParameterAtPoint(e3));
14
15
return [[c2[0],e2[0],d2[0]],[c3,e3,d3]];
16
};
17
18
def shPh1 (st,en,crvs:var[]..[])
19
{
20
dr = Vector.ByTwoPoints(st,en);
21
ds = st.DistanceTo(en);
22
shPth1 = [Imperative]
23
{
24
ph = [];
25
ct = 0;
26
while (ds > 0)
27
{
28
cr = ner(st,en,dr,crvs)[0];
29
ph[ct] = cr[0];
30
st = cr[1];
31
dr = cr[2];
32
crvs = List.SetDifference(crvs,ph);
33
ds = st.DistanceTo(en);
34
ct = ct + 1;
35
}
36
return ph;
37
}
38
return shPth1;
39
};
40
41
def shPh2 (en1,en2,en,crvs:var[]..[])
42
{
43
cv1 = Math.Sum(shPh1 (en1,en,crvs).Length);
44
cv2 = Math.Sum(shPh1 (en2,en,crvs).Length);
45
return cv1 >= cv2 ? 1 : 0;
46
};
47
48
def shPh3 (st1,en1,cvs:var[]..[])
49
{
50
return = [Imperative]
51
{
52
cv1 = ner(st1,en1,Vector.ByTwoPoints(st1,en1),cvs);
53
ne1 = cv1[shPh2 (cv1[0][1],cv1[1][1],en1,cvs)];
54
ph = [ne1[0]];
55
st = ne1[1];
56
dr = ne1[2];
57
ds = st.DistanceTo(en1);
58
ct = 1;
59
60
while (ds > 0)
61
{
62
cs = List.SetDifference(cvs,ph);
63
cr = ner(st,en1,dr,cs);
64
ne = cr[shPh2 (cr[0][1],cr[1][1],en1,cs)];
65
ph[ct] = ne[0];
66
st = ne[1];
67
dr = ne[2];
68
ds = st.DistanceTo(en1);
69
ct = ct + 1;
70
}
71
return ph;
72
}
73
};
74
75
//Sample Grid
76
a = 0..100..10;
77
p1 = Point.ByCoordinates(a<1>,a<2>);
78
p2 = List.Transpose(p1);
79
p3 = List.DropItems(List.Sublists(p1<1>,0..1,1)<1>,-1);
80
p4 = List.DropItems(List.Sublists(p2<1>,0..1,1)<1>,-1);
81
l1 = Line.ByBestFitThroughPoints(List.Flatten([p3,p4],2));
82
83
r1 = Rectangle.ByCornerPoints(Point.ByCoordinates([0,0,100,100],[0,100,100,0]));
84
r2 = Rectangle.ByCornerPoints(Point.ByCoordinates([30,30,70,70],[10,70,70,10]));
85
s1 = r1.Patch().TrimWithEdgeLoops([r1,r2]);
86
l2 = List.RemoveIfNot(List.Flatten(l1.Intersect(s1),-1),"Line");
Copied!
Shortest path of specified gradient along topography
Copy link