STRAIGHT LINE — HOW THIS MAP WAS BUILT A reproducible blueprint for "straight lines over a coastline" ===================================================================== WHAT THIS DOCUMENT IS A step-by-step recipe for building a project like Straight Line (https://line.vova.today): an interactive globe that draws every straight line from a country or a point, by sea until it touches land, by land until it reaches the sea, by air with nothing in the way, and finds the records: the longest line over water (32,065 km, Pakistan to Kamchatka), the longest over land (13,607 km, China to Liberia), the poles of inaccessibility, each country's farthest point. It is written for a capable coding assistant (or a person) to follow and produce a similar project from scratch. It describes WHAT the data is, WHERE to get it, HOW to trace the lines exactly, HOW to find the records and HOW to draw them, without the source code. The values given are the ones that worked, so you can start there and tune. The method generalises to any question of the form "how far can a straight line go across these polygons before it hits those": sea lanes, sight lines over land, radio paths, flight corridors over closed airspace. ----------------------------------------------------------------------------- 0. THE IDEA (read this first: it constrains every later choice) ----------------------------------------------------------------------------- A straight line on the Earth is a line that never turns left or right. On a sphere it is a great circle; on the real, slightly flattened Earth it is a geodesic on the ellipsoid. On a globe it looks straight; on any flat map it bends. The whole project exists to show that one thing and to measure it. Two rules follow, and everything downstream obeys them: 1. EXACT, NOT RASTER. A line counts only if it misses every bit of coast. A raster of land and water loses the thin straits and the small islands that decide the records. Every crossing of a line with a coastline is computed from the coastline's own edges. 2. THE SAME NUMBERS EVERYWHERE. The tables, the records, the story's text and the lines the browser traces live all come from the same coastline and the same model of the Earth, so a number on a card is the number a reader gets by clicking. ----------------------------------------------------------------------------- 1. DATA SOURCES (where everything comes from) ----------------------------------------------------------------------------- All of it is free and openly licensed. Credit the authors. a) COASTLINE — GSHHG 2.3.7 (Wessel & Smith), the full-resolution binary (gshhs_f.b). Its polygons are nested by level: 1 land, 2 lake, 3 island in a lake, 4 pond on that island, 5 Antarctica's ice front (take it as the coast), 6 Antarctica's grounding line (skip it). The full resolution is what the long computations use; the browser gets the high resolution. b) RIVERS — WDBII, shipped with GSHHG: the major permanent rivers as lines. c) COUNTRIES — Natural Earth 5.1.2: countries at 1:10m for the computations, 1:50m for drawing the map, admin-1 regions to move pieces of territory when a border needs it, and the names of islands and peninsulas. d) PUBLISHED FIGURES to compare with: Chabukswar and Mukherjee, "Longest straight line paths on water or land on the Earth" (2018, arXiv:1804.07389), and Point Nemo as Hrvoje Lukatela computed it (1992). e) For a single local check (the shores of a few islands near the Atlantic's pole of inaccessibility): OpenStreetMap's coastline. ----------------------------------------------------------------------------- 2. STEP ONE — ONE COASTLINE, OWNED BY COUNTRIES ----------------------------------------------------------------------------- GSHHG knows where land is but not whose it is; Natural Earth knows whose land is whose but draws coasts far more coarsely. Use each for what it is good at. - Land and water come from GSHHG only. The country of a stretch of GSHHG land is the Natural Earth polygon that covers it. A small island that Natural Earth lacks goes to the nearest country ON THE SAME LANDMASS. (Plain "nearest polygon" invents borders: a Swedish coast would end up named after a Danish island across the strait.) - Split each country into PARTS: polygons within 250 km of each other stay together (single linkage; seeds are the mainland and every exclave, so an island goes to the seed it is nearest). French Guiana, Alaska, Hawaii and Kaliningrad become parts of their own. A line starts from a part, and the tables are kept per part; the page folds parts back into countries. - GSHHG cuts the land at the Suez and Panama canals, so Africa and Asia are separate polygons. Fill the cuts with land and keep the canals as a separate layer. - Make obstacles SWITCHABLE layers instead of baking them in: lakes and reservoirs of 1,000 km² and more (plus the Dead Sea), the two canals, and the major rivers with their wide stretches and the lakes they run through. The sea and the Caspian always count as water. Every polygon keeps the switch it belongs to; a line over land is traced once per combination of switches the site offers. - Draw borders the way the site intends and say so in its methodology. This site follows Natural Earth with stated changes (the Donetsk, Luhansk, Zaporizhzhia and Kherson regions moved to Russia along Natural Earth's own admin-1 lines; Baykonur kept in Kazakhstan). ----------------------------------------------------------------------------- 3. STEP TWO — AN EXACT INDEX OF EDGES ----------------------------------------------------------------------------- Millions of lines against millions of coastline edges need an index that never approximates. - Use a CUBE-MAP grid: a point on the unit sphere belongs to the face of its largest coordinate and is projected gnomonically onto it. A gnomonic projection maps great circles to straight lines, so walking a great circle through the cells of a face is an exact 2D line walk (DDA), and taking each polygon edge as a great-circle arc puts it in exactly the cells it crosses. - The grid is ONLY an index. A line crosses an edge when the edge's two ends lie on opposite sides of the line's plane; the crossing point is computed from the edge itself and kept by the one cell it falls in, so an edge listed in several cells counts once. - Each cell also gets a class: open water with no edges, land with no edges, or mixed. An edge-free open-water cell is an "anchor": a line passing through it is known to be at sea there, which is where every sweep starts. ----------------------------------------------------------------------------- 4. STEP THREE — TRACE MILLIONS OF STRAIGHT LINES ----------------------------------------------------------------------------- THE FAMILY OF LINES. Every great circle has a pole; spread the poles evenly over a hemisphere on a Fibonacci lattice and the circles cover the sphere evenly. With 4 million circles, neighbours are about 8 km apart everywhere along their length. THE SWEEP. Walk a line through the index, collect its crossings sorted along it, and start at an anchor. Each crossing enters or leaves a polygon, and GSHHG's nesting depth says what the line is over: depth 0 sea, odd land, even lake. The Natural Earth polygon in the current set names the country. A run of sea between two shores is a line over water; a run of land between two coasts, with no switched-on obstacle inside, is a line over land. For every pair of country parts and every kind (sea, lake, land per switch combination) keep the longest and the shortest line found and how many were found. THE ELLIPSOID. The sphere is fine for drawing but off by up to about half a per cent in length. To count on WGS84: - Compute geodesics with Karney's method ("Algorithms for geodesics", J. Geodesy, 2013): a geodesic is a great circle on an auxiliary sphere, and distance and longitude come from two integrals. Both integrands are smooth and periodic, so their Fourier coefficients can be taken from a 32-point trapezoid rule instead of retyping the paper's series. Check against GeographicLib: random geodesics up to 40,000 km agreed to under a thousandth of a millimetre. - A geodesic on the ellipsoid does not close into a circle. Replace "one great circle per pole" with "one revolution per lattice member": a member is a node longitude and the azimuth there, taken from the same Fibonacci lattice, and its revolution runs from one northward equator crossing to the next. - Walk a geodesic in chunks of 100 km, each chunk the great-circle arc between two exact points of the geodesic. Such an arc strays from the geodesic by under a metre, so the cube index and the edge test work unchanged; a crossing's distance along the geodesic is interpolated within its chunk. - Trace a WINDOW per member: from its first anchor to one revolution later, then go on past the end until every run that started inside the window has closed. Each line then starts in exactly one window. The typical length barely moved (the median ratio to the sphere's is 1.0000); a single pair moved by a per cent or two where a different line won. The records kept their places: the longest line over water went from 32,084 km on the sphere to 32,065 km on WGS84. ----------------------------------------------------------------------------- 5. STEP FOUR — THE RECORDS ----------------------------------------------------------------------------- The lattice finds lines about 8 km apart; the true longest line from a country lies near one of them. - Take each part's three best lattice lines and refine each by local search: nudge the line (on the sphere its pole; on the ellipsoid a point on it and the azimuth there) in 8 directions, keep a move that lengthens the line through the same spot, halve the step when none does, down to centimetres. - Offer every refined line to BOTH of its parts. A line refined from either end may climb to a different local maximum, and the record of China to Liberia and that of Liberia to China must be one line. - Compare with the published figures and explain any difference. The 2018 paper gives 32,090 km over water and 11,241 km over land with the Suez Canal as water; ours are 32,065 and 11,266. It treated the Earth as a sphere and took land and water from a height map (ETOPO1) with a step of about 1.8 km. On a sphere, our method gives 32,084 and 11,246. ----------------------------------------------------------------------------- 6. STEP FIVE — POLES OF INACCESSIBILITY AND FARTHEST POINTS ----------------------------------------------------------------------------- POLES OF INACCESSIBILITY (the sea point farthest from any land): - Land is every vertex of the full-resolution coastline, islands and Antarctica's ice front included. Put them in a k-d tree. - Grid the sea at a quarter of a degree, cut it into oceans along the usual boundaries, take each ocean's farthest cell and refine it by local search, halving the step down to a metre. - On the ellipsoid, first find the point on the sphere (a few km off), then keep only the coastline vertices that may be nearest on WGS84 (within 1.5% of the sphere's distance), search again with a fast approximate ellipsoid distance, and measure the final distance exactly. - STEP ALONG THE RIDGE. The distance to the nearest shore has ridges where two shores are equally far, rising to the pole where three are. A search in fixed directions stalls on such a ridge. Try the ridge's own direction first: away from both nearest shores at once, -(uA + uB), where uA and uB are the unit directions to them; then the fixed ones. Start from several cells. - The land's pole of inaccessibility is the same search over land, against the sea's coast: 45.34° N, 88.25° E, 2,514 km from the sea, which agrees with Barnes (2019) to a few hundred metres. - A published point may beat your own data: GSHHG lacks Maher Island off Antarctica, so our search puts Point Nemo 17 km south of Lukatela's, 2,705 km from land. The site shows the official point and explains the difference. THE FARTHEST POINT FROM A COUNTRY (by straight line over water or land): - Pass 1, the field: for each part, a 1-degree grid holding, per cell, the shortest distance at which any traced line from that part reaches the cell. Each lattice line paints the cells it crosses. The farthest point is the cell whose shortest distance is the largest. - Pass 2, the lines: trace again and keep, for each part's farthest cell, the line that reaches it, measured exactly. - A lattice samples. When the only lines to a far place thread a narrow strait, the lattice can miss them all and the "farthest point" comes out absurdly near. Add every line known from elsewhere as an extra member: the table lines, the refined records, the answers of an earlier run. That brought the Guantanamo Bay base's farthest sea point from 1,435 km back to 6,262 km. THE POINT THAT SEES THE MOST COUNTRIES: a coarse grid with one ray per degree from each point, full fans round the best few, then a local search. At sea it is a point in the Atlantic whose lines reach 80 countries. ----------------------------------------------------------------------------- 7. STEP SIX — THE BROWSER ----------------------------------------------------------------------------- The heavy tables are precomputed; lines from a clicked point are traced live. - SHIP THE COASTLINE FOR LIVE TRACING as a compact binary: GSHHG's high resolution with coordinates rounded to 0.0001° (about 11 m), stored as zigzag varint deltas, gzipped: about 3.8 MB. A web worker decodes it and builds the same kind of cube index (about a second on a desktop), then traces geodesics in 250 km chunks. 100 km chunks gave the same line ends to 0.1 km and were slower. - A FAN FROM A POINT: one ray per degree; wherever two neighbouring rays end differently (one on another country, one shorter by far), split the gap in ten and repeat, down to a thousandth of a degree. Small islands that a one-degree fan misses are caught this way. - BY AIR nothing stops a line, so nothing is traced: between two countries the distance is the shortest line between their outlines, and the farthest point from a country is precomputed. - THE MAP is one WebGL scene (three.js): a globe that unfolds into a flat map by a single parameter from 0 to 1, so the viewer sees the same line straight on the globe and bent on the map. Everything that belongs to the map, the lines, the points and the labels too, is drawn in the canvas: labels are boxes drawn once into a texture atlas and placed as quads at their points, so they move with the map, hide behind the globe and never lag behind it. The page's DOM holds only cards and controls. - LABEL SETS: when a set of labels changes, keep the labels present in both sets as they are. Fade out only what left and fade in only what came; replacing the whole set makes every label blink. - DATA FILES: one JSON per family of tables (pairs by sea, by land per switch combination, pieces, records, poles, farthest points), from about 150 KB to 6 MB. ----------------------------------------------------------------------------- 8. STEP SEVEN — THE STORY ----------------------------------------------------------------------------- A scrolling story opens the site: cards pass over the map, and the map shows each card's scene (a line, a pole, a fan, a ride along a record). - The scroll never moves the camera directly. The scroll position gives the camera a TARGET, a pure function of the scroll, so any way of scrolling, a jump included, lands right; two critically damped springs per channel (longitude, latitude, zoom, side shift, fold) ease the camera to it. Two in a row start softly; one jolts. - The camera's path is one smooth monotone curve through every card's keyframes. A long turn pulls the zoom out to the whole globe halfway; a change between globe and flat map folds first and turns after (or turns first and unfolds after), overlapping a little so the camera never stops. - The cards scroll plainly over the map, like any page: nothing sticks, snaps or pins while the scenes change underneath. - On phones a card covers the map. A card's scene is in force from its top entering at the bottom of the screen until its bottom leaves at the top; the move to the next scene runs on a spring in time, along the same curve, not along the finger. - Each card can be exported as a picture to share: the live map framed with the card's few words. ----------------------------------------------------------------------------- 9. THINGS THAT DID NOT WORK (skip these; we already paid for them) ----------------------------------------------------------------------------- - A raster of land and water → thin straits and small islands decide the records, and a raster loses them. Trace against the vector edges. - Staying on the sphere → lengths off by up to half a per cent, and published figures that cannot be matched. Count on WGS84; keep the sphere as a check. - Treating a geodesic like a great circle → it does not close. Trace one revolution per member with a window, as in step three. - A local search in a few fixed directions on a max-min distance → it stalls on the ridge between two equally near shores (the land's pole came out 2,502.6 km instead of 2,513.7; the Indian Ocean's 1,936.3 instead of 1,941.6). Step along the ridge first. - Trusting a lattice for farthest points → it misses places reached only through narrow straits. Seed it with every line known from elsewhere. - Walking back along 45,000 extra lines in one thread to find where each one's window starts, all in memory → an hour of disk paging and no progress. Start each window a fixed distance back along the line, and let all threads share one set of fields. - Running at full speed on every core → the machine becomes unusable for hours. Four threads at below-normal priority. - Long runs that keep everything in memory → a run killed for lack of memory loses hours. Work in batches and write the whole state after each batch atomically (to a file beside it, then renamed), so a restart with the same arguments goes on from the next batch. - "Nearest Natural Earth polygon" as the owner of unnamed land → invented borders across straits. Nearest country on the same landmass. - Labels as DOM elements over the canvas → they lag and float above the globe. Draw them in the scene. - A long browser cache on data files whose names are not hashed → a returning visitor gets the new code with the old tables. Keep such files out of long caching, or hash their names. ----------------------------------------------------------------------------- 10. RUNNING IT ----------------------------------------------------------------------------- - Python with NumPy and Numba for the pipeline; a k-d tree (SciPy) for the nearest-coast searches; TypeScript for the browser's tracer, run in Node for the precomputed records the page shows. - The order: the country set, its parts and the edge index → the tables (4 million lines) → pieces → records → poles → farthest points → export. Each step writes its output and is skipped if the output is there. - The farthest-point step is the long one: about three hours on four threads. The rest take minutes to tens of minutes each. ----------------------------------------------------------------------------- 11. DEPLOY ----------------------------------------------------------------------------- - Nuxt 3 (Vue), SSR on, statically generated from an explicit route list: /, /en, /ru and /[lang]/[mode] for the three modes (water, land, air). Flat .html files, so Cloudflare Pages serves the URL without a trailing slash directly. - Cloudflare Pages, deployed by a git push. - Social share images: a pre-rendered picture of the real map per mode and language. ----------------------------------------------------------------------------- 12. AT A GLANCE — the whole pipeline in one breath ----------------------------------------------------------------------------- GSHHG full-resolution coastline + Natural Earth countries → land from GSHHG, owners from Natural Earth, canals filled, lakes / canals / rivers as switchable layers, countries split into parts → exact edge index on a cube-map grid (gnomonic faces, exact crossings) → 4 million evenly spread straight lines: great circles, then WGS84 geodesics (Karney) walked in 100 km chunks, a window per revolution → per pair of parts and per kind: longest, shortest, count → records by local search, mirrored to both ends → poles of inaccessibility (coastline vertices, ridge-aware search) and farthest points (a field pass, a lines pass, seeded with known lines) → JSON tables + a compact coastline binary for live tracing in a worker → one WebGL scene: a globe that unfolds into a map, labels in the scene → a scrolling story on springs, then the free map → static Nuxt build → Cloudflare Pages Data: GSHHG 2.3.7 (coastline, lakes, WDBII rivers), Natural Earth 5.1.2 (countries, borders, names), OpenStreetMap (a local check). All open. Credit them. Live map: https://line.vova.today Write-up: https://vova.today/en/works/line (in Russian: https://vova.today/ru/works/line)