Skip to content

armgit / Aleph

Public Imported from GitHub
0

Give satellite imagery, terrain data, buildings, streetview photos to your LLM

16.0 KB
Raw Blame
"""Spherical road geometry and Web Mercator tile grids. Points are (lat, lon)."""

import math
from bisect import bisect_right
from collections import defaultdict
from itertools import pairwise

import numpy as np

from .common import number, positive

RADIUS = 6_371_008.8
MERCATOR_RADIUS = 6_378_137
MAX_LATITUDE = 85.0511287798066
MAX_VERTICES = 1000
DETAILED_GRID = 64  # Rows and columns up to which lines() draws every tile.


def clamp(value, low, high):
    return max(low, min(high, value))


def ring_contains(ring, point):
    x, y = point
    inside = False
    for (ax, ay), (bx, by) in pairwise(ring):
        if (ay > y) != (by > y) and x < ax + (y - ay) * (bx - ax) / (by - ay):
            inside = not inside
    return inside


def signed_area(ring):
    return sum(a[0] * b[1] - b[0] * a[1] for a, b in pairwise(ring)) / 2


def extent(points):
    """Bounding box in south/west/north/east order, including degenerate boxes."""
    latitudes, longitudes = zip(*points)
    return min(latitudes), min(longitudes), max(latitudes), max(longitudes)


def distance(a, b):
    lat1, lat2 = map(math.radians, (a[0], b[0]))
    delta = math.radians(b[1] - a[1])
    h = math.sin((lat2 - lat1) / 2) ** 2 + math.cos(lat1) * math.cos(lat2) * math.sin(delta / 2) ** 2
    return 2 * RADIUS * math.asin(math.sqrt(min(1, h)))


def bearing(a, b):
    lat1, lat2 = map(math.radians, (a[0], b[0]))
    delta = math.radians(b[1] - a[1])
    y = math.sin(delta) * math.cos(lat2)
    x = math.cos(lat1) * math.sin(lat2) - math.sin(lat1) * math.cos(lat2) * math.cos(delta)
    return math.degrees(math.atan2(y, x)) % 360


def destination(point, heading, meters):
    lat, lon = map(math.radians, point)
    angle, heading = meters / RADIUS, math.radians(heading)
    end = math.asin(clamp(math.sin(lat) * math.cos(angle) + math.cos(lat) * math.sin(angle) * math.cos(heading), -1, 1))
    delta = math.atan2(math.sin(heading) * math.sin(angle) * math.cos(lat),
                       math.cos(angle) - math.sin(lat) * math.sin(end))
    return math.degrees(end), (math.degrees(lon + delta) + 180) % 360 - 180


def point(values):
    lat, lon = values
    return number(lat, "latitude", -90, 90), number(lon, "longitude", -180, 180)


def bounds(values, *, minimum=1):
    lat1, lon1, lat2, lon2 = values
    if not all(math.isfinite(v) for v in values):
        raise ValueError("Coordinates must be finite numbers.")
    south, north = sorted((lat1, lat2))
    west, east = sorted((lon1, lon2))
    if not (-90 <= south <= north <= 90 and -180 <= west <= east <= 180):
        raise ValueError("Use latitude −90…90 and longitude −180…180.")
    if east - west > 180:
        raise ValueError("Split areas crossing the date line in two.")
    middle = (south + north) / 2
    size = min(distance((middle, west), (middle, east)), distance((south, west), (north, west)))
    if size <= 0 or size < minimum:
        raise ValueError(f"The area must be nonempty and at least {minimum} meter(s) wide and high.")
    return south, west, north, east


def corners(area):
    """A rectangle as a polygon, counterclockwise from its southwest corner."""
    south, west, north, east = area
    return [(south, west), (south, east), (north, east), (north, west)]


def crosses(a, b, c, d):
    """Whether segments a–b and c–d cross at a point inside both."""
    def side(p, q, r):
        return (q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0])

    return side(a, b, c) * side(a, b, d) < 0 and side(c, d, a) * side(c, d, b) < 0


def vertices(values, *, minimum=1):
    """A simple polygon of (lat, lon) points, without repeating the first one at the end."""
    polygon = []
    for value in values:
        vertex = point(value)
        if not polygon or vertex != polygon[-1]:
            polygon.append(vertex)
    if len(polygon) > 1 and polygon[0] == polygon[-1]:
        polygon.pop()
    if not 3 <= len(polygon) <= MAX_VERTICES:
        raise ValueError(f"A polygon needs 3 to {MAX_VERTICES} distinct points.")
    bounds(extent(polygon), minimum=minimum)
    ring = [*polygon, polygon[0]]
    sides = list(pairwise(ring))
    for i, (a, b) in enumerate(sides):
        # Neighbors share a point, including the last and first sides.
        for c, d in sides[i + 2:len(sides) - (i == 0)]:
            if crosses(a, b, c, d):
                raise ValueError("The polygon's edges must not cross.")
    if not signed_area(ring):
        raise ValueError("The polygon must enclose an area.")
    return polygon


def within(polygon, lats, lons):
    """ring_contains for arrays of latitudes and longitudes."""
    inside = np.zeros(np.shape(lats), bool)
    for (alat, alon), (blat, blon) in pairwise([*polygon, polygon[0]]):
        if alat != blat:
            inside ^= ((alat > lats) != (blat > lats)) & (lons < alon + (lats - alat) * (blon - alon) / (blat - alat))
    return inside


def pieces(a, b, polygon):
    """Parts of segment a–b inside the polygon, in order from a."""
    ring = [*polygon, polygon[0]]
    dlat, dlon = b[0] - a[0], b[1] - a[1]
    cuts = [0, 1]
    for c, d in pairwise(ring):
        elat, elon = d[0] - c[0], d[1] - c[1]
        if denominator := dlat * elon - dlon * elat:
            t = ((c[0] - a[0]) * elon - (c[1] - a[1]) * elat) / denominator
            u = ((c[0] - a[0]) * dlon - (c[1] - a[1]) * dlat) / denominator
            if 0 < t < 1 and 0 <= u <= 1:
                cuts.append(t)

    def at(t):
        return a if t == 0 else b if t == 1 else (a[0] + t * dlat, a[1] + t * dlon)

    parts = []
    for start, end in pairwise(sorted(cuts)):
        if start < end and ring_contains(ring, at((start + end) / 2)):
            if parts and parts[-1][1] == start:
                parts[-1][1] = end
            else:
                parts.append([start, end])
    return [(at(start), at(end)) for start, end in parts if distance(at(start), at(end)) > 0.01]


def offset(point, origin):
    """Meters east and north of a nearby origin, on a plane."""
    scale = math.radians(RADIUS)
    return (((point[1] - origin[1] + 180) % 360 - 180) * scale * math.cos(math.radians(origin[0])),
            (point[0] - origin[0]) * scale)


def near(polygon, point, meters):
    """Whether a point lies inside the polygon or within a short distance of its edges."""
    ring = [*polygon, polygon[0]]
    if ring_contains(ring, point):
        return True
    for (ax, ay), (bx, by) in pairwise([offset(p, point) for p in ring]):
        dx, dy = bx - ax, by - ay
        t = clamp(-(ax * dx + ay * dy) / (dx * dx + dy * dy), 0, 1) if dx or dy else 0
        if math.hypot(ax + t * dx, ay + t * dy) <= meters:
            return True
    return False


def measure(polygon):
    """Approximate ground area in square meters and perimeter in meters."""
    origin = sum(p[0] for p in polygon) / len(polygon), polygon[0][1]
    ring = [offset(p, origin) for p in [*polygon, polygon[0]]]
    return abs(signed_area(ring)), sum(math.dist(a, b) for a, b in pairwise(ring))


def around(center, size):
    """A square in ground meters, returned in south/west/north/east order."""
    lat, lon = point(center)
    positive(size, "size")
    dy = math.degrees(size / (2 * RADIUS))
    if abs(lat) + dy >= 90:
        raise ValueError("The area cannot cross a pole.")
    dx = dy / math.cos(math.radians(lat))
    if lon - dx < -180 or lon + dx > 180:
        raise ValueError("Split areas crossing the date line into two rectangles.")
    return bounds((lat - dy, lon - dx, lat + dy, lon + dx), minimum=0)


def clip(a, b, area):
    """Liang–Barsky clipping also retains segments with both ends outside."""
    south, west, north, east = area
    dy, dx = b[0] - a[0], b[1] - a[1]
    enter, leave = 0, 1
    for p, q in ((-dx, a[1] - west), (dx, east - a[1]), (-dy, a[0] - south), (dy, north - a[0])):
        if p == 0:
            if q < 0:
                return None
        elif p < 0:
            enter = max(enter, q / p)
        else:
            leave = min(leave, q / p)
        if enter > leave:
            return None
    start, end = [(clamp(a[0] + t * dy, south, north), clamp(a[1] + t * dx, west, east)) for t in (enter, leave)]
    return (start, end) if distance(start, end) > 0.01 else None


class Line:
    def __init__(self, points):
        self.points = points
        self.cumulative = [0]
        self.headings = []
        for a, b in pairwise(points):
            self.cumulative.append(self.cumulative[-1] + distance(a, b))
            self.headings.append(bearing(a, b))
        self.length = self.cumulative[-1]

    def at(self, meters):
        meters = clamp(meters, 0, self.length)
        i = min(bisect_right(self.cumulative, meters) - 1, len(self.headings) - 1)
        return destination(self.points[i], self.headings[i], meters - self.cumulative[i])

    def heading(self, meters, spacing):
        window = min(5, spacing / 4, self.length / 4)
        before, after = self.at(meters - window), self.at(meters + window)
        if distance(before, after) < 0.01:
            before = self.at(meters)
        return bearing(before, after)

    def project(self, point, segments=None):
        nearest = None
        for i in range(len(self.headings)) if segments is None else sorted(segments):
            angle = distance(self.points[i], point) / RADIUS
            delta = math.radians(bearing(self.points[i], point) - self.headings[i])
            offset = RADIUS * math.atan2(math.sin(angle) * math.cos(delta), math.cos(angle))
            meters = clamp(self.cumulative[i] + offset, self.cumulative[i], self.cumulative[i + 1])
            separation = distance(self.at(meters), point)
            if (nearest is None or separation < nearest[1] - 0.1
                    or (abs(separation - nearest[1]) <= 0.1 and meters < nearest[0])):
                nearest = meters, separation
        return nearest


class RoadIndex:
    """A small spatial grid; long segments live in a separate overflow list."""

    def __init__(self, lines, radius=30):
        self.size = math.degrees(max(50, radius) / RADIUS)
        self.cells = defaultdict(list)
        self.wide = []
        for road, line in enumerate(lines):
            for segment, heading in enumerate(line.headings):
                length = line.cumulative[segment + 1] - line.cumulative[segment]
                lat, lon = destination(line.points[segment], heading, length / 2)
                angle = (length / 2 + radius + 0.2) / RADIUS
                dy = math.degrees(angle)
                dx = 180 if abs(lat) + dy >= 90 else math.degrees(
                    math.asin(clamp(math.sin(angle) / math.cos(math.radians(lat)), -1, 1)))
                x0, x1 = (math.floor(x / self.size) for x in (lon - dx, lon + dx))
                y0, y1 = (math.floor(y / self.size) for y in (lat - dy, lat + dy))
                entry = road, segment
                if (x1 - x0 + 1) * (y1 - y0 + 1) > 256 or lon - dx < -180 or lon + dx > 180:
                    self.wide.append(entry)
                else:
                    for x in range(x0, x1 + 1):
                        for y in range(y0, y1 + 1):
                            self.cells[x, y].append(entry)

    def near(self, point):
        key = math.floor(point[1] / self.size), math.floor(point[0] / self.size)
        groups = defaultdict(list)
        for road, segment in self.cells.get(key, []) + self.wide:
            groups[road].append(segment)
        return groups


def pixel(point, zoom):
    size = 256 * 2**zoom
    latitude = math.radians(clamp(point[0], -MAX_LATITUDE, MAX_LATITUDE))
    return (point[1] + 180) / 360 * size, clamp((1 - math.asinh(math.tan(latitude)) / math.pi) / 2 * size, 0, size)


def coordinate(x, y, zoom):
    size = 256 * 2**zoom
    return math.degrees(math.atan(math.sinh(math.pi * (1 - 2 * y / size)))), x / size * 360 - 180


def grid(polygon, zoom):
    """Tiles meeting the polygon and the pixels enclosing it; a rectangle meets every tile of its grid.

    Spans list those tiles in download order: [row, first column, column after the last, tiles in earlier spans].
    """
    south, west, north, east = extent(polygon)
    if south < -MAX_LATITUDE or north > MAX_LATITUDE:
        raise ValueError("Imagery areas must stay within latitudes −85.0511…85.0511.")

    # Projection roundoff grows with the world pixel size at high zooms.
    tolerance = max(1e-7, 8 * math.ulp(256 * 2**zoom))

    def snap(value):
        return round(value) if abs(value - round(value)) < tolerance else value

    left, top = (math.floor(snap(v)) for v in pixel((north, west), zoom))
    right, bottom = (math.ceil(snap(v)) for v in pixel((south, east), zoom))
    x0, y0 = left // 256, top // 256
    columns, rows = math.ceil(right / 256) - x0, math.ceil(bottom / 256) - y0
    points = [tuple(snap(v) / 256 - origin for v, origin in zip(pixel(p, zoom), (x0, y0))) for p in polygon]
    spans, count = [], 0
    for row in range(rows):
        for start, end in meeting(points, row, columns):
            spans.append([row, start, end, count])
            count += end - start
    return dict(zoom=zoom, left=left, top=top, width=right - left, height=bottom - top,
                x0=x0, y0=y0, columns=columns, rows=rows, spans=spans, count=count)


def meeting(points, row, columns):
    """Column ranges of a row's tiles that meet a polygon in tile units, ignoring touches along tile edges."""
    ranges, crossings = [], []
    for (ax, ay), (bx, by) in pairwise([*points, points[0]]):
        # Part of the edge within the row.
        if ay == by:
            if row < ay < row + 1:
                ranges.append((min(ax, bx), max(ax, bx)))
            continue
        low, high = sorted(((row - ay) / (by - ay), (row + 1 - ay) / (by - ay)))
        low, high = max(low, 0), min(high, 1)
        if low < high:
            ranges.append(tuple(sorted((ax + low * (bx - ax), ax + high * (bx - ax)))))
        # Tiles with no edges inside lie between edges crossing the row's middle.
        if (ay > row + 0.5) != (by > row + 0.5):
            crossings.append(ax + (row + 0.5 - ay) * (bx - ax) / (by - ay))
    crossings.sort()
    ranges += zip(crossings[::2], crossings[1::2])
    runs = []
    for start, end in sorted((max(math.floor(low), 0), min(math.ceil(high), columns)) for low, high in ranges):
        if start >= end:
            continue
        if runs and start <= runs[-1][1]:
            runs[-1] = runs[-1][0], max(end, runs[-1][1])
        else:
            runs.append((start, end))
    return runs


def tiles(grid):
    for row, start, end, _ in grid["spans"]:
        for column in range(start, end):
            yield dict(x=grid["x0"] + column, y=grid["y0"] + row, zoom=grid["zoom"], row=row, column=column)


def lines(grid):
    """Edges of a grid's tiles as ((x, y), (x, y)) in tile units, or just their outline for large grids."""
    detailed = grid["rows"] <= DETAILED_GRID and grid["columns"] <= DETAILED_GRID
    x0, y0 = grid["x0"], grid["y0"]
    rows = [[] for _ in range(grid["rows"] + 2)]  # Empty rows above and below.
    segments = []
    for row, start, end, _ in grid["spans"]:
        rows[row + 1].append((start, end))
        for column in range(start, end + 1) if detailed else (start, end):
            segments.append(((x0 + column, y0 + row), (x0 + column, y0 + row + 1)))
    for row, (above, below) in enumerate(pairwise(rows)):
        # Every tile's top and bottom, or only where coverage changes between rows.
        ends = sorted({x for run in above + below for x in run})
        for low, high in pairwise(ends):
            depth = sum(start <= low < end for start, end in above + below)
            if depth == 1 or detailed and depth:
                segments.append(((x0 + low, y0 + row), (x0 + high, y0 + row)))
    return segments


def tile_ring(tile):
    north, west = coordinate(tile["x"] * 256, tile["y"] * 256, tile["zoom"])
    south, east = coordinate((tile["x"] + 1) * 256, (tile["y"] + 1) * 256, tile["zoom"])
    return [[west, south], [east, south], [east, north], [west, north], [west, south]]


def feature(geometry, coordinates, properties):
    return dict(type="Feature", geometry=dict(type=geometry, coordinates=coordinates), properties=properties)


def collection(features):
    return dict(type="FeatureCollection", features=list(features))