1package arcgismap23// Clipping for national datasets. A watershed intersecting a city's window4// may extend a hundred windows past it, and the synthetic projection is5// linear in the window's own terms: a vertex far outside would land on an6// absurd longitude and wrap the viewer's world. City data never needs this7// -- a hub publishes ground near its own city -- so only features fetched by8// window are cut down to it, at capture time, where the trimmed shape rides9// the content addressing like any other fact about the day.10//11// The window rectangle is cut in plain degrees. Its edges are lines of12// constant longitude and latitude, and both the Mercator forward and the13// synthetic spelling are monotone per axis, so the degree rectangle and the14// projected square bound exactly the same ground.1516// ClipRings cuts MultiPolygon-nested rings to the window, ring by ring with17// Sutherland–Hodgman. A polygon whose outer ring is cut to nothing is18// dropped whole; a hole cut to nothing drops alone. Introduced vertices are19// rounded like every captured coordinate, and output rings close on their20// first position.21func ClipRings(w Window, polygons [][][][]float64) [][][][]float64 {22 var out [][][][]float6423 for _, polygon := range polygons {24 var kept [][][]float6425 for at, ring := range polygon {26 clipped := clipRing(w, ring)27 if clipped == nil {28 if at == 0 {29 kept = nil30 break31 }32 continue33 }34 kept = append(kept, clipped)35 }36 if len(kept) > 0 {37 out = append(out, kept)38 }39 }40 return out41}4243// ClipLines cuts MultiLineString-nested lines to the window. A line that44// leaves and returns splits into one part per crossing, and parts too short45// to draw are dropped.46func ClipLines(w Window, lines [][][]float64) [][][]float64 {47 var out [][][]float6448 var part [][]float6449 flush := func() {50 if len(part) >= 2 {51 out = append(out, part)52 }53 part = nil54 }55 for _, line := range lines {56 for at := 0; at+1 < len(line); at++ {57 a, b := line[at], line[at+1]58 if len(a) < 2 || len(b) < 2 {59 flush()60 continue61 }62 enter, exit, held := clipSegment(w, a[0], a[1], b[0], b[1])63 if !held {64 flush()65 continue66 }67 if len(part) == 0 || part[len(part)-1][0] != enter[0] || part[len(part)-1][1] != enter[1] {68 flush()69 part = [][]float64{enter}70 }71 part = append(part, exit)72 if exit[0] != Round7(b[0]) || exit[1] != Round7(b[1]) {73 flush()74 }75 }76 flush()77 }78 return out79}8081// edge is one of the window's four half-planes.82type edge struct {83 axis int // 0 clips longitude, 1 latitude84 bound float6485 keep float64 // +1 keeps values >= bound, -1 keeps values <= bound86}8788func (w Window) edges() [4]edge {89 return [4]edge{90 {0, w.West, 1},91 {0, w.East, -1},92 {1, w.South, 1},93 {1, w.North, -1},94 }95}9697func (e edge) inside(p []float64) bool {98 return (p[e.axis]-e.bound)*e.keep >= 099}100101// cross lands on the edge along the segment from a to b, rounded the way102// every captured coordinate is.103func (e edge) cross(a, b []float64) []float64 {104 t := (e.bound - a[e.axis]) / (b[e.axis] - a[e.axis])105 p := []float64{106 Round7(a[0] + t*(b[0]-a[0])),107 Round7(a[1] + t*(b[1]-a[1])),108 }109 p[e.axis] = e.bound110 return p111}112113// clipRing is Sutherland–Hodgman against the window's four edges. The ring114// arrives closed and leaves closed; nil means nothing of it remains.115func clipRing(w Window, ring [][]float64) [][]float64 {116 open := ring117 if len(open) > 1 && open[0][0] == open[len(open)-1][0] && open[0][1] == open[len(open)-1][1] {118 open = open[:len(open)-1]119 }120 current := make([][]float64, 0, len(open))121 for _, p := range open {122 if len(p) >= 2 {123 current = append(current, p)124 }125 }126 for _, e := range w.edges() {127 if len(current) == 0 {128 return nil129 }130 next := make([][]float64, 0, len(current)+4)131 for at, point := range current {132 previous := current[(at+len(current)-1)%len(current)]133 switch {134 case e.inside(point) && e.inside(previous):135 next = append(next, point)136 case e.inside(point):137 next = append(next, e.cross(previous, point), point)138 case e.inside(previous):139 next = append(next, e.cross(previous, point))140 }141 }142 current = dedupe(next)143 }144 if len(current) < 3 {145 return nil146 }147 return append(current, current[0])148}149150// dedupe drops consecutive repeats, which clipping at a corner introduces151// and rounding can too.152func dedupe(points [][]float64) [][]float64 {153 out := points[:0]154 for _, p := range points {155 if len(out) > 0 && out[len(out)-1][0] == p[0] && out[len(out)-1][1] == p[1] {156 continue157 }158 out = append(out, p)159 }160 if len(out) > 1 && out[0][0] == out[len(out)-1][0] && out[0][1] == out[len(out)-1][1] {161 out = out[:len(out)-1]162 }163 return out164}165166// clipSegment cuts one segment to the window, answering the kept piece's two167// ends rounded, or nothing when the segment misses the window entirely.168func clipSegment(w Window, ax, ay, bx, by float64) (enter, exit []float64, held bool) {169 t0, t1 := 0.0, 1.0170 clip := func(delta, room float64) bool {171 if delta == 0 {172 return room >= 0173 }174 t := room / delta175 if delta < 0 {176 if t > t1 {177 return false178 }179 if t > t0 {180 t0 = t181 }182 return true183 }184 if t < t0 {185 return false186 }187 if t < t1 {188 t1 = t189 }190 return true191 }192 dx, dy := bx-ax, by-ay193 if !clip(-dx, ax-w.West) || !clip(dx, w.East-ax) ||194 !clip(-dy, ay-w.South) || !clip(dy, w.North-ay) {195 return nil, nil, false196 }197 enter = []float64{Round7(ax + t0*dx), Round7(ay + t0*dy)}198 exit = []float64{Round7(ax + t1*dx), Round7(ay + t1*dy)}199 if enter[0] == exit[0] && enter[1] == exit[1] {200 return nil, nil, false201 }202 return enter, exit, true203}