1package compose23import (4 "fmt"5 "math"6 "sort"7 "strings"89 "github.com/FelineStateMachine/atlas/internal/generate/curation"10 "github.com/FelineStateMachine/atlas/internal/generate/doc"11 "github.com/FelineStateMachine/atlas/internal/generate/tiles"12)1314// Some publishers print several separate places on one sheet. A game rings its15// main map with district insets; another stacks three elevations of one ground16// side by side. In both the split is already in the data -- the world's17// top-level areas are the pieces, and every point names the area it stands on --18// so a sheet can be taken apart rather than shown whole.19//20// Which sheets those are is declared in curation and never detected. Plenty of21// worlds have fifteen or forty top-level areas that are districts of one22// continuous ground, and splitting one of those would shatter it. Nothing in a23// document separates the two cases, so guessing is not an option and a wrong24// guess divides a whole map into pieces nobody asked for.25//26// Nothing here knows a source. A piece is planned from the interchange27// document's own vocabulary -- area features, their parents, and the areas point28// features declare themselves members of -- so a second source describing the29// same sheet the same way splits the same way.3031// splitReach is how far a piece may grow into the empty space around it: far32// enough to reach a title banner printed beside the ground it names, short33// enough that an isolated piece does not swallow the sheet around it.34const splitReach = 2563536// piece is one part of a split sheet: the area that defines it, what belongs to37// it, and the window onto the sheet that draws it.38type piece struct {39 // Area is the top-level area feature the piece is cut around.40 Area composedFeature41 // Features is every feature id the piece keeps -- points by membership,42 // areas by ancestry.43 Points map[int64]bool44 Areas map[int64]bool45 // Bounds is the window onto the sheet, in world pixels, grown into the46 // space around the piece so a title printed beside it comes along.47 Bounds tiles.Box48 // Surface is the same box before it was grown: the ground the piece's areas49 // actually cover, without the margin the raster keeps.50 Surface tiles.Box51 Center doc.Position52}5354// splitWorld takes a curated sheet apart, and otherwise hands back the single55// world it was given.56//57// The two modes answer two different questions about a sheet. Pieces that are58// unrelated places sharing a sheet become worlds of their own, each in the59// picker; pieces that are the same ground at different heights stay one world60// and become lenses, so the view survives switching between them.61func splitWorld(w composedWorld, mode curation.ShardMode, grid surfaceGrid) ([]composedWorld, error) {62 if mode == curation.ShardNone {63 return []composedWorld{w}, nil64 }65 pieces, err := planPieces(w, grid, mode)66 if err != nil {67 return nil, err68 }69 if mode == curation.ShardIntoLenses {70 return []composedWorld{asLenses(w, pieces)}, nil71 }72 return asWorlds(w, pieces), nil73}7475// planPieces groups a world's areas and points under their top-level area.76//77// A piece is sized by the ground its areas cover, not by the points assigned to78// it. A handful of points sit outside the area that claims them -- forty on one79// sheet in the corpus -- and stretching a piece to reach them pulls the main map80// back over the very insets it is being split away from. Points are not clipped81// by these bounds, only the raster is, so a stray one stays reachable just82// beyond the edge of its map.83func planPieces(w composedWorld, grid surfaceGrid, mode curation.ShardMode) ([]piece, error) {84 areas := make(map[int64]composedFeature)85 for _, collection := range w.Collections {86 if collection.Kind != doc.KindArea {87 continue88 }89 for _, feature := range collection.Features {90 areas[feature.ID] = feature91 }92 }93 // rootOf walks an area up to the top of its family. A cycle stops where it94 // started rather than spinning: a malformed parent chain is somebody else's95 // data problem and not a reason to hang.96 rootOf := func(id int64) (int64, bool) {97 seen := make(map[int64]bool)98 for {99 area, held := areas[id]100 if !held {101 return 0, false102 }103 if area.Parent == 0 || seen[id] {104 return id, true105 }106 seen[id] = true107 id = area.Parent108 }109 }110111 byRoot := make(map[int64]*piece)112 take := func(id int64) *piece {113 if existing, held := byRoot[id]; held {114 return existing115 }116 created := &piece{117 Area: areas[id],118 Points: make(map[int64]bool),119 Areas: make(map[int64]bool),120 }121 byRoot[id] = created122 return created123 }124125 extents := make(map[int64]*[4]float64)126 grow := func(root int64, x, y float64) {127 box, held := extents[root]128 if !held {129 box = &[4]float64{math.Inf(1), math.Inf(1), math.Inf(-1), math.Inf(-1)}130 extents[root] = box131 }132 box[0], box[1] = math.Min(box[0], x), math.Min(box[1], y)133 box[2], box[3] = math.Max(box[2], x), math.Max(box[3], y)134 }135136 for _, collection := range w.Collections {137 if collection.Kind != doc.KindArea {138 continue139 }140 for _, area := range collection.Features {141 root, ok := rootOf(area.ID)142 if !ok {143 continue144 }145 part := take(root)146 part.Areas[area.ID] = true147 for _, geometry := range area.Geometry {148 for _, point := range flattenCoordinates(geometry.Coordinates) {149 grow(root, projectX(point[0], grid), projectY(point[1], grid))150 }151 }152 }153 }154155 var orphans int156 placed := make(map[int64][2]float64)157 for _, collection := range w.Collections {158 if collection.Kind != doc.KindPoint {159 continue160 }161 for _, point := range collection.Features {162 if point.Member == 0 || point.At == nil {163 orphans++164 continue165 }166 root, ok := rootOf(point.Member)167 if !ok {168 orphans++169 continue170 }171 take(root).Points[point.ID] = true172 placed[point.ID] = [2]float64{173 projectX(point.At.Lng, grid),174 projectY(point.At.Lat, grid),175 }176 }177 }178 if orphans > 0 {179 return nil, fmt.Errorf(180 "%d point features belong to no area, so they would vanish when the sheet is split", orphans)181 }182183 // Only a piece with ground under it can be cut out: an area family that184 // outlines nothing has no window to give.185 boxes := make([][4]float64, 0, len(byRoot))186 order := make([]int64, 0, len(byRoot))187 for _, collection := range w.Collections {188 if collection.Kind != doc.KindArea {189 continue190 }191 for _, area := range collection.Features {192 part, held := byRoot[area.ID]193 if !held || part.Area.ID != area.ID {194 continue195 }196 box := extents[area.ID]197 if box == nil || math.IsInf(box[0], 1) {198 continue199 }200 boxes = append(boxes, *box)201 order = append(order, area.ID)202 }203 }204 grown := growIntoGaps(boxes, float64(grid.Size))205206 pieces := make([]piece, 0, len(order))207 for index, root := range order {208 part := byRoot[root]209 left, top, right, bottom := grown[index][0], grown[index][1], grown[index][2], grown[index][3]210 // Bounds are measured down from the top of the world, matching how a211 // reader clips the raster.212 part.Bounds = tiles.Box{213 X: int(left),214 Y: int(top),215 Width: int(right - left),216 Height: int(bottom - top),217 }218 box := boxes[index]219 part.Surface = tiles.Box{220 X: int(box[0]),221 Y: int(box[1]),222 Width: int(box[2] - box[0]),223 Height: int(box[3] - box[1]),224 }225 part.Center = doc.Position{226 Lat: unprojectLat((top+bottom)/2, grid),227 Lng: unprojectLng((left+right)/2, grid),228 }229 pieces = append(pieces, *part)230 }231 rehomeStrays(pieces, placed)232 orderPieces(pieces, mode)233 if len(pieces) < 2 {234 return nil, fmt.Errorf("only %d top-level area, so there is nothing to split", len(pieces))235 }236 return pieces, nil237}238239// growIntoGaps widens each piece into the empty space around it, stopping240// halfway to whatever it would otherwise run into.241//242// An area outlines the ground it covers, not the art drawn around it. A sheet243// that titles each of its pieces with a banner sitting just above the outline244// gets the words sliced in half by a crop to the outline alone. Claiming the245// space between pieces takes the banner with the piece it names, while stopping246// at the midpoint keeps panels twenty pixels apart from showing a slice of their247// neighbour.248func growIntoGaps(boxes [][4]float64, world float64) [][4]float64 {249 grown := make([][4]float64, len(boxes))250 for index, box := range boxes {251 room := [4]float64{splitReach, splitReach, splitReach, splitReach}252 for other, rival := range boxes {253 if other == index {254 continue255 }256 // Only pieces sharing a span on the other axis can be run into.257 if spansOverlap(box[1], box[3], rival[1], rival[3]) {258 if rival[2] <= box[0] {259 room[0] = math.Min(room[0], (box[0]-rival[2])/2)260 }261 if rival[0] >= box[2] {262 room[2] = math.Min(room[2], (rival[0]-box[2])/2)263 }264 }265 if spansOverlap(box[0], box[2], rival[0], rival[2]) {266 if rival[3] <= box[1] {267 room[1] = math.Min(room[1], (box[1]-rival[3])/2)268 }269 if rival[1] >= box[3] {270 room[3] = math.Min(room[3], (rival[1]-box[3])/2)271 }272 }273 }274 grown[index] = [4]float64{275 math.Max(0, box[0]-room[0]),276 math.Max(0, box[1]-room[1]),277 math.Min(world, box[2]+room[2]),278 math.Min(world, box[3]+room[3]),279 }280 }281 separate(grown, boxes)282 return grown283}284285// separate undoes the growth where two pieces met in a corner. Pieces sharing no286// span on either axis do not hold each other back, so both can expand into the287// same diagonal space. Whichever way they now overlap least is the way they are288// eased apart.289//290// Only the growth is ever given back. Easing two pieces apart used to be free to291// cut into the ground a piece was cut for, which took the bottom border off a292// panel: the crop stopped inside the frame the panel is drawn with. Where two293// pieces genuinely cover the same ground they are left overlapping, because that294// is the sheet saying so, not the crop.295func separate(boxes, floors [][4]float64) {296 for pass := 0; pass < len(boxes); pass++ {297 clear := true298 for a := range boxes {299 for b := a + 1; b < len(boxes); b++ {300 across := math.Min(boxes[a][2], boxes[b][2]) - math.Max(boxes[a][0], boxes[b][0])301 down := math.Min(boxes[a][3], boxes[b][3]) - math.Max(boxes[a][1], boxes[b][1])302 if across <= 0 || down <= 0 {303 continue304 }305 clear = false306 if across <= down {307 give(&boxes[a], &boxes[b], across/2, 0)308 } else {309 give(&boxes[a], &boxes[b], down/2, 1)310 }311 hold(&boxes[a], floors[a])312 hold(&boxes[b], floors[b])313 }314 }315 if clear {316 return317 }318 }319}320321// hold keeps a box around the ground it was grown from.322func hold(box *[4]float64, floor [4]float64) {323 box[0] = math.Min(box[0], floor[0])324 box[1] = math.Min(box[1], floor[1])325 box[2] = math.Max(box[2], floor[2])326 box[3] = math.Max(box[3], floor[3])327}328329// give pulls two boxes back from each other along one axis, axis 0 across and330// axis 1 down.331func give(a, b *[4]float64, by float64, axis int) {332 low, high := axis, axis+2333 if a[low] < b[low] {334 a[high] -= by335 b[low] += by336 return337 }338 b[high] -= by339 a[low] += by340}341342func spansOverlap(lowA, highA, lowB, highB float64) bool {343 return lowA < highB && lowB < highA344}345346// rehomeStrays moves a point to the piece it is actually drawn on.347//348// Some points name an area they do not sit in: on one sheet in the corpus forty349// claim the main map while lying inside the panels around it. Trusting the claim350// left them floating in the dark beside the map they were split from, exactly351// where their panel used to be. Where a point sits is not in doubt, so position352// decides and the claim is treated as the mistake it is.353func rehomeStrays(pieces []piece, placed map[int64][2]float64) {354 inside := func(part piece, at [2]float64) bool {355 b := part.Bounds356 return at[0] >= float64(b.X) && at[0] <= float64(b.X+b.Width) &&357 at[1] >= float64(b.Y) && at[1] <= float64(b.Y+b.Height)358 }359 for index := range pieces {360 for id := range pieces[index].Points {361 at, known := placed[id]362 if !known || inside(pieces[index], at) {363 continue364 }365 hosts := make([]int, 0, 2)366 for other := range pieces {367 if other != index && inside(pieces[other], at) {368 hosts = append(hosts, other)369 }370 }371 // Only an unambiguous home is worth moving to: a point inside two372 // overlapping pieces has not told us anything the claim did not.373 if len(hosts) != 1 {374 continue375 }376 delete(pieces[index].Points, id)377 pieces[hosts[0]].Points[id] = true378 }379 }380}381382// orderPieces puts the pieces in the order they are offered. Lenses read down383// the way they are stacked, so the sky comes before the ground beneath it.384// Separate places lead with the largest, so a sheet's main map heads its insets.385func orderPieces(pieces []piece, mode curation.ShardMode) {386 sort.Slice(pieces, func(a, b int) bool {387 if mode == curation.ShardIntoLenses {388 if pieces[a].Bounds.Y != pieces[b].Bounds.Y {389 return pieces[a].Bounds.Y < pieces[b].Bounds.Y390 }391 return pieces[a].Area.Title < pieces[b].Area.Title392 }393 areaA := pieces[a].Bounds.Width * pieces[a].Bounds.Height394 areaB := pieces[b].Bounds.Width * pieces[b].Bounds.Height395 if areaA != areaB {396 return areaA > areaB397 }398 return pieces[a].Area.Title < pieces[b].Area.Title399 })400}401402// asWorlds gives each piece its own world. The largest keeps the sheet's name403// and leads; the rest are named after it so they sort together in the picker404// instead of scattering among the volume's standalone worlds.405func asWorlds(w composedWorld, pieces []piece) []composedWorld {406 out := make([]composedWorld, 0, len(pieces))407 for index, part := range pieces {408 copied := w409 copied.Collections = keepAreas(410 keepPoints(w.Collections, part.Points),411 part.Areas, part.Area.ID,412 )413 copied.Center = part.Center414 copied.Lenses = boundLenses(w.Lenses, part.Bounds, part.Surface, 0)415 if index > 0 {416 copied.ID = part.Area.ID417 copied.Title = w.Title + " — " + part.Area.Title418 copied.Slug = w.Slug + "-" + slugify(part.Area.Title)419 copied.Parent = w.Slug420 }421 out = append(out, copied)422 }423 return out424}425426// asLenses keeps one world and offers the pieces as lenses. Features carry the427// piece they belong to so a reader can show one at a time, and the view survives428// switching because the world itself never changes.429func asLenses(w composedWorld, pieces []piece) composedWorld {430 // The collections are rewritten in place, so they are copied first: a431 // document's features belong to the document, and marking one piece's must432 // not reach back into it.433 collections := make([]composedCollection, len(w.Collections))434 for index, collection := range w.Collections {435 collection.Features = append([]composedFeature(nil), collection.Features...)436 collections[index] = collection437 }438439 var lenses []lens440 // One pyramid draws every lens of a sharded world: the pieces are windows441 // onto the same sheet, so each piece repeats the world's whole tile-set442 // entry list and the two slices stay index for index.443 var pyramids []tiles.Pyramid444 var outlines []int64445 for _, part := range pieces {446 bound := boundLenses(w.Lenses, part.Bounds, part.Surface, part.Area.ID)447 for index := range bound {448 bound[index].Name = part.Area.Title449 }450 lenses = append(lenses, bound...)451 pyramids = append(pyramids, w.Pyramids...)452 for collectionIndex := range collections {453 collection := &collections[collectionIndex]454 claims := part.Areas455 if collection.Kind == doc.KindPoint {456 claims = part.Points457 }458 for featureIndex := range collection.Features {459 if claims[collection.Features[featureIndex].ID] {460 collection.Features[featureIndex].Shard = part.Area.ID461 }462 }463 }464 outlines = append(outlines, part.Area.ID)465 }466 w.Lenses = lenses467 w.Pyramids = pyramids468 w.Collections = keepAreas(collections, nil, outlines...)469 if len(pieces) > 0 {470 w.Center = pieces[0].Center471 }472 return w473}474475// boundLenses clips each raster to the piece. The tiles are the same pyramid476// either way; only the window onto it changes. The ground the piece covers477// travels alongside the window, because they are not the same rectangle and478// anything measuring the world rather than drawing it wants the ground.479func boundLenses(lenses []lens, bounds, surface tiles.Box, shard int64) []lens {480 // Easing two pieces apart can pull a window in past the ground it grew481 // from, and what a grid divides has to be drawn, so the ground is clipped to482 // the window rather than reaching beyond it.483 ground := intersectBox(surface, bounds)484 out := make([]lens, 0, len(lenses))485 for _, source := range lenses {486 clipped := source487 window := bounds488 clipped.Bounds = &window489 covered := ground490 clipped.Surface = &covered491 clipped.Shard = shard492 out = append(out, clipped)493 }494 return out495}496497// keepPoints pares each point collection down to the piece's own features. A498// collection left with none is dropped, which is also what empties a legend499// heading out of a piece's payload: no collection carries it any more.500func keepPoints(collections []composedCollection, wanted map[int64]bool) []composedCollection {501 out := make([]composedCollection, 0, len(collections))502 for _, collection := range collections {503 if collection.Kind != doc.KindPoint {504 out = append(out, collection)505 continue506 }507 kept := make([]composedFeature, 0, len(collection.Features))508 for _, point := range collection.Features {509 if wanted[point.ID] {510 kept = append(kept, point)511 }512 }513 if len(kept) == 0 {514 continue515 }516 collection.Features = kept517 out = append(out, collection)518 }519 return out520}521522// keepAreas drops the piece's own outline. Once an area has been used to cut a523// world or a lens out of a sheet, drawing it again just traces the edge of what524// the reader is already looking at.525func keepAreas(collections []composedCollection, wanted map[int64]bool, drop ...int64) []composedCollection {526 discard := make(map[int64]bool, len(drop))527 for _, id := range drop {528 discard[id] = true529 }530 out := make([]composedCollection, 0, len(collections))531 for _, collection := range collections {532 if collection.Kind == doc.KindPoint {533 out = append(out, collection)534 continue535 }536 kept := make([]composedFeature, 0, len(collection.Features))537 for _, shape := range collection.Features {538 if discard[shape.ID] || (wanted != nil && !wanted[shape.ID]) {539 continue540 }541 kept = append(kept, shape)542 }543 if len(kept) == 0 {544 continue545 }546 collection.Features = kept547 out = append(out, collection)548 }549 return out550}551552// slugify is how a piece's title becomes part of a world slug: lower case,553// everything that is not a letter or a digit run together as a hyphen.554func slugify(value string) string {555 return strings.Trim(strings.Map(func(r rune) rune {556 switch {557 case r >= 'a' && r <= 'z', r >= '0' && r <= '9':558 return r559 case r >= 'A' && r <= 'Z':560 return r + ('a' - 'A')561 default:562 return '-'563 }564 }, value), "-")565}566567func unprojectLng(x float64, grid surfaceGrid) float64 {568 worldTiles := math.Pow(2, float64(grid.SourceZoom))569 xTile := x/float64(grid.TileSize) + float64(grid.FirstTile)570 return (xTile/worldTiles)*360 - 180571}572573func unprojectLat(y float64, grid surfaceGrid) float64 {574 worldTiles := math.Pow(2, float64(grid.SourceZoom))575 yTile := y/float64(grid.TileSize) + float64(grid.FirstTile)576 return math.Atan(math.Sinh(math.Pi*(1-2*yTile/worldTiles))) * 180 / math.Pi577}