1package basemap23// box is an axis-aligned window in world pixels.4type box struct {5 minX, minY, maxX, maxY float646}78func (b box) contains(p [2]float64) bool {9 return p[0] >= b.minX && p[0] <= b.maxX && p[1] >= b.minY && p[1] <= b.maxY10}1112func (b box) overlaps(o box) bool {13 return b.minX <= o.maxX && o.minX <= b.maxX && b.minY <= o.maxY && o.minY <= b.maxY14}1516// bounds measures a set of rings or lines.17func bounds(paths [][][2]float64) box {18 out := box{minX: 1e18, minY: 1e18, maxX: -1e18, maxY: -1e18}19 for _, path := range paths {20 for _, p := range path {21 out.minX = min(out.minX, p[0])22 out.minY = min(out.minY, p[1])23 out.maxX = max(out.maxX, p[0])24 out.maxY = max(out.maxY, p[1])25 }26 }27 return out28}2930// clipRing cuts a polygon ring to a window, Sutherland–Hodgman: one pass31// per edge, each keeping the inside and splicing in the crossings. The32// window carries bleed beyond the visible tile, so the cut edges land33// outside the picture and adjacent tiles continue the shape exactly.34func clipRing(ring [][2]float64, window box) [][2]float64 {35 type edge func(p [2]float64) bool36 inside := []edge{37 func(p [2]float64) bool { return p[0] >= window.minX },38 func(p [2]float64) bool { return p[0] <= window.maxX },39 func(p [2]float64) bool { return p[1] >= window.minY },40 func(p [2]float64) bool { return p[1] <= window.maxY },41 }42 cross := []func(a, b [2]float64) [2]float64{43 func(a, b [2]float64) [2]float64 { return lerpX(a, b, window.minX) },44 func(a, b [2]float64) [2]float64 { return lerpX(a, b, window.maxX) },45 func(a, b [2]float64) [2]float64 { return lerpY(a, b, window.minY) },46 func(a, b [2]float64) [2]float64 { return lerpY(a, b, window.maxY) },47 }48 current := ring49 for at := range inside {50 if len(current) == 0 {51 return nil52 }53 next := make([][2]float64, 0, len(current)+4)54 for i := range current {55 a := current[(i+len(current)-1)%len(current)]56 b := current[i]57 aIn, bIn := inside[at](a), inside[at](b)58 switch {59 case aIn && bIn:60 next = append(next, b)61 case aIn && !bIn:62 next = append(next, cross[at](a, b))63 case !aIn && bIn:64 next = append(next, cross[at](a, b), b)65 }66 }67 current = next68 }69 if len(current) < 3 {70 return nil71 }72 return current73}7475func lerpX(a, b [2]float64, x float64) [2]float64 {76 t := (x - a[0]) / (b[0] - a[0])77 return [2]float64{x, a[1] + t*(b[1]-a[1])}78}7980func lerpY(a, b [2]float64, y float64) [2]float64 {81 t := (y - a[1]) / (b[1] - a[1])82 return [2]float64{a[0] + t*(b[0]-a[0]), y}83}8485// clipSegment cuts one segment to a window, Liang–Barsky, reporting whether86// anything survives.87func clipSegment(a, b [2]float64, window box) ([2]float64, [2]float64, bool) {88 t0, t1 := 0.0, 1.089 dx, dy := b[0]-a[0], b[1]-a[1]90 clip := func(p, q float64) bool {91 if p == 0 {92 return q >= 093 }94 t := q / p95 if p < 0 {96 if t > t1 {97 return false98 }99 if t > t0 {100 t0 = t101 }102 } else {103 if t < t0 {104 return false105 }106 if t < t1 {107 t1 = t108 }109 }110 return true111 }112 if !clip(-dx, a[0]-window.minX) || !clip(dx, window.maxX-a[0]) ||113 !clip(-dy, a[1]-window.minY) || !clip(dy, window.maxY-a[1]) {114 return a, b, false115 }116 from := [2]float64{a[0] + t0*dx, a[1] + t0*dy}117 to := [2]float64{a[0] + t1*dx, a[1] + t1*dy}118 return from, to, true119}120121// signedArea is a ring's area with the sign of its winding, in the y-down122// pixel plane: positive is clockwise on the screen.123func signedArea(ring [][2]float64) float64 {124 area := 0.0125 for i := range ring {126 j := (i + 1) % len(ring)127 area += ring[i][0]*ring[j][1] - ring[j][0]*ring[i][1]128 }129 return area / 2130}131132// reverse flips a ring's winding in place.133func reverse(ring [][2]float64) {134 for i, j := 0, len(ring)-1; i < j; i, j = i+1, j-1 {135 ring[i], ring[j] = ring[j], ring[i]136 }137}