Repository navigation
Expand file tree
/
Copy pathpath.go
More file actions
137 lines (118 loc) · 3.88 KB
/
Copy pathpath.go
File metadata and controls
137 lines (118 loc) · 3.88 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
package layout
import (
"iter"
"math"
"slices"
"github.com/loov/layout/internal/draw"
)
// flattenPath approximates the rounded corners drawn by the writers
// (curves cut the given radius from the vertex) with two extra points per
// corner, the middle one where the curve crosses the bisector.
func flattenPath(path Path, radius, maxDeviation Length) Path {
return appendFlatPath(nil, path, radius, maxDeviation)
}
// flatLen returns the length of the path flattenPath returns
func flatLen(path Path) int {
if len(path) < 3 {
return len(path)
}
return 3*len(path) - 4
}
// appendFlatPath appends the flattened path to out, see flattenPath; a
// path without corners is returned as it is
func appendFlatPath(out, path Path, radius, maxDeviation Length) Path {
if len(path) < 3 {
return path
}
towards := func(a, b Vector, d Length) Vector {
l := b.Sub(a).Len()
if l == 0 {
return a
}
return Vector{X: a.X + (b.X-a.X)*d/l, Y: a.Y + (b.Y-a.Y)*d/l}
}
out = append(out, path[0])
for i := 1; i+1 < len(path); i++ {
prev, p, next := path[i-1], path[i], path[i+1]
r := Length(draw.CornerRadius(drawPoint(prev), drawPoint(p), drawPoint(next), float64(radius), float64(maxDeviation)))
in, exit := towards(p, prev, r), towards(p, next, r)
mid := Vector{X: (in.X + 2*p.X + exit.X) / 4, Y: (in.Y + 2*p.Y + exit.Y) / 4}
out = append(out, in, mid, exit)
}
return append(out, path[len(path)-1])
}
// drawPoint converts v for the draw package
func drawPoint(v Vector) draw.Point { return draw.Point{X: float64(v.X), Y: float64(v.Y)} }
// offsetPath shifts the path sideways by dx and re-clips the ends to the
// nodes; a straight edge between neighbors along a rank, along, runs
// across x, so it moves across that, in y
func offsetPath(path Path, dx Length, from, to *lnode, along bool) Path {
out := make(Path, len(path))
for i, p := range path {
out[i] = Vector{X: p.X + dx, Y: p.Y}
if along {
out[i] = Vector{X: p.X, Y: p.Y + dx}
}
}
switch {
case along:
// straight across, at its own height on both
out[0] = from.sideAt(out[0].Y, to.Center.X)
out[1] = to.sideAt(out[1].Y, from.Center.X)
case len(out) >= 2:
out[0] = from.Boundary(out[1])
out[len(out)-1] = to.Boundary(out[len(out)-2])
}
return out
}
// reversed returns the path in reverse order
func (path Path) reversed() Path {
rs := make(Path, 0, len(path))
for _, p := range slices.Backward(path) {
rs = append(rs, p)
}
return rs
}
// Path is a polyline, from its first point to its last.
type Path []Vector
// Segments yields the ends of every segment of path, in order.
func (path Path) Segments() iter.Seq2[Vector, Vector] {
return func(yield func(a, b Vector) bool) {
for i := 0; i+1 < len(path); i++ {
if !yield(path[i], path[i+1]) {
return
}
}
}
}
// Length returns the length of path along its segments.
func (path Path) Length() (length Length) {
for a, b := range path.Segments() {
length += b.Sub(a).Len()
}
return length
}
// middle returns the middle point of path, or the midpoint of the two
// middle points of a path with an even number of them
func (path Path) middle() Vector { return midpoint(path[(len(path)-1)/2], path[len(path)/2]) }
// projection returns how far along the segment from a to b the point
// of it nearest p is, from 0 to 1, and the segment's dx and dy
func projection(p, a, b Vector) (t, dx, dy float64) {
dx, dy = float64(b.X-a.X), float64(b.Y-a.Y)
if l := dx*dx + dy*dy; l > 0 {
t = math.Max(0, math.Min(1, (float64(p.X-a.X)*dx+float64(p.Y-a.Y)*dy)/l))
}
return t, dx, dy
}
// nearest returns the point of path closest to p
func (path Path) nearest(p Vector) (Vector, bool) {
best, bestDist := Vector{}, math.Inf(1)
for a, b := range path.Segments() {
t, dx, dy := projection(p, a, b)
q := Vector{a.X + Length(t*dx), a.Y + Length(t*dy)}
if d := float64(p.Sub(q).Len()); d < bestDist {
best, bestDist = q, d
}
}
return best, bestDist < math.Inf(1)
}