1package basemap23// Clipping, and the winding convention the fills stand on.4//5// A tile draws against a window bled a little past its own edge, so every cut6// the clipper makes lands outside the picture. That is what lets neighbouring7// tiles be drawn independently and still continue each other exactly: the seam8// is drawn twice, from the same numbers, and never falls on a pixel either tile9// keeps.1011// box is an axis-aligned rectangle in world pixels.12type box struct {13 minX, minY, maxX, maxY float6414}1516// span measures a set of rings or lines. An empty set comes back inverted --17// minimum above maximum -- which is how a caller tells "nothing here" from a18// rectangle of zero size.19func span(paths [][][2]float64) box {20 out := box{minX: 1e18, minY: 1e18, maxX: -1e18, maxY: -1e18}21 for _, path := range paths {22 for _, at := range path {23 out.minX = min(out.minX, at[0])24 out.minY = min(out.minY, at[1])25 out.maxX = max(out.maxX, at[0])26 out.maxY = max(out.maxY, at[1])27 }28 }29 return out30}3132func (b box) empty() bool { return b.minX > b.maxX }3334// join is the rectangle covering both, used to reach one feature's rings and35// lines with a single measurement.36func (b box) join(o box) box {37 if b.empty() {38 return o39 }40 if o.empty() {41 return b42 }43 return box{44 minX: min(b.minX, o.minX), minY: min(b.minY, o.minY),45 maxX: max(b.maxX, o.maxX), maxY: max(b.maxY, o.maxY),46 }47}4849// clipRing cuts a polygon ring to a window by Sutherland--Hodgman: four50// passes, one per window edge, each keeping what is inside and splicing in the51// crossings. A ring that comes out with fewer than three corners encloses52// nothing and is dropped.53func clipRing(ring [][2]float64, window box) [][2]float64 {54 inside := [4]func([2]float64) bool{55 func(p [2]float64) bool { return p[0] >= window.minX },56 func(p [2]float64) bool { return p[0] <= window.maxX },57 func(p [2]float64) bool { return p[1] >= window.minY },58 func(p [2]float64) bool { return p[1] <= window.maxY },59 }60 crossing := [4]func(a, b [2]float64) [2]float64{61 func(a, b [2]float64) [2]float64 { return atX(a, b, window.minX) },62 func(a, b [2]float64) [2]float64 { return atX(a, b, window.maxX) },63 func(a, b [2]float64) [2]float64 { return atY(a, b, window.minY) },64 func(a, b [2]float64) [2]float64 { return atY(a, b, window.maxY) },65 }6667 current := ring68 for edge := range inside {69 if len(current) == 0 {70 return nil71 }72 next := make([][2]float64, 0, len(current)+4)73 for i := range current {74 from := current[(i+len(current)-1)%len(current)]75 to := current[i]76 fromIn, toIn := inside[edge](from), inside[edge](to)77 switch {78 case fromIn && toIn:79 next = append(next, to)80 case fromIn:81 next = append(next, crossing[edge](from, to))82 case toIn:83 next = append(next, crossing[edge](from, to), to)84 }85 }86 current = next87 }88 if len(current) < 3 {89 return nil90 }91 return current92}9394// atX and atY are the point where a segment meets a vertical or horizontal95// line. Both are only ever called for a segment that actually crosses it, so96// the denominator cannot be zero.97func atX(a, b [2]float64, x float64) [2]float64 {98 t := (x - a[0]) / (b[0] - a[0])99 return [2]float64{x, a[1] + t*(b[1]-a[1])}100}101102func atY(a, b [2]float64, y float64) [2]float64 {103 t := (y - a[1]) / (b[1] - a[1])104 return [2]float64{a[0] + t*(b[0]-a[0]), y}105}106107// clipSegment cuts one segment to a window by Liang--Barsky, reporting whether108// any of it survives. A polyline is clipped a segment at a time rather than as109// a whole, because a stroke's dash rhythm has to keep riding the original path110// however much of it is off the tile.111func clipSegment(a, b [2]float64, window box) ([2]float64, [2]float64, bool) {112 enter, leave := 0.0, 1.0113 dx, dy := b[0]-a[0], b[1]-a[1]114115 // narrow tightens the surviving interval against one boundary, stated as116 // the usual p/q pair: p is the segment's motion across it, q the distance117 // to it. A segment parallel to the boundary survives only if it starts on118 // the inside of it.119 narrow := func(p, q float64) bool {120 if p == 0 {121 return q >= 0122 }123 t := q / p124 switch {125 case p < 0:126 if t > leave {127 return false128 }129 enter = max(enter, t)130 default:131 if t < enter {132 return false133 }134 leave = min(leave, t)135 }136 return true137 }138139 if !narrow(-dx, a[0]-window.minX) || !narrow(dx, window.maxX-a[0]) ||140 !narrow(-dy, a[1]-window.minY) || !narrow(dy, window.maxY-a[1]) {141 return a, b, false142 }143 return [2]float64{a[0] + enter*dx, a[1] + enter*dy},144 [2]float64{a[0] + leave*dx, a[1] + leave*dy}, true145}146147// normalizeWinding forces a polygon's rings into the convention the fills148// stand on: the first ring is ground and winds one way, every ring after it is149// a hole and winds the other, whatever the publisher said. Real exports do not150// reliably follow the GeoJSON rule, and a hole wound the wrong way fills itself151// in rather than cutting out.152func normalizeWinding(rings [][][2]float64) {153 for at, ring := range rings {154 if len(ring) < 3 {155 continue156 }157 // A ring whose signed area is exactly zero encloses nothing either158 // way round, and is left exactly as it came: flipping it would change159 // the winding a self-crossing ring contributes without changing the160 // area that made it look degenerate.161 switch area := signedArea(ring); {162 case at == 0 && area < 0, at > 0 && area > 0:163 reverse(ring)164 }165 }166}167168// signedArea is a ring's area carrying the sign of its winding, measured in the169// y-down pixel plane where positive reads as clockwise on the screen.170func signedArea(ring [][2]float64) float64 {171 total := 0.0172 for i := range ring {173 j := (i + 1) % len(ring)174 total += ring[i][0]*ring[j][1] - ring[j][0]*ring[i][1]175 }176 return total / 2177}178179// reverse flips a ring's winding where it lies.180func reverse(ring [][2]float64) {181 for i, j := 0, len(ring)-1; i < j; i, j = i+1, j-1 {182 ring[i], ring[j] = ring[j], ring[i]183 }184}