mesh/src/pslg.ts

export type Angle = number

/**
 * A better rounding function than .toFixed(...).
 * @param value
 * @param precision
 */
export function safeRound(value: number, precision = 12) {
    return parseFloat(
        Math.round(
            // @ts-ignore
            value.toFixed(precision + 1) + 'e' + precision
        ) + 'e-' + precision
    );
}

export function deg2rad(degrees: number): number {
    return degrees * (Math.PI / 180)
}

export function rad2deg(radian: number): number {
    return radian * (180 / Math.PI)
}

export function rad2degp(radian: number): number {
    const deg = rad2deg(radian)
    return deg < 0 ? deg + 180 : deg
}

export interface Coordinate {
    x: number,
    y: number,
}

export class Point {
    public static from(x: number, y: number): Point {
        return new Point({x, y})
    }

    constructor(
        public readonly coordinate: Coordinate,
        public readonly name?: string,
    ) {
        this.coordinate = {
            x: safeRound(coordinate.x),
            y: safeRound(coordinate.y),
        }
    }

    get x() {
        return this.coordinate.x
    }

    get y() {
        return this.coordinate.y
    }

    clone(): Point {
        return new Point({...this.coordinate}, this.name)
    }

    is(x: Point) {
        return (
            x.coordinate.x === this.coordinate.x
            && x.coordinate.y === this.coordinate.y
        )
    }

    isLeftOf(x: Point) {
        return this.x < x.x
    }

    isRightOf(x: Point) {
        return this.x > x.x
    }

    public static midpoint(a: Point, b: Point): Point {
        const x = (a.x + b.x) / 2
        const y = (a.y + b.y) / 2
        return Point.from(x, y)
    }

    public static distinct(points: Point[]): Point[] {
        const distinct: Point[] = []
        for ( const point of points ) {
            if ( !distinct.some(other => other.is(point)) ) {
                distinct.push(point)
            }
        }

        return distinct
    }
}

export class Segment {
    static fromCombinedHorizontals(a: Segment, b: Segment) {
        const leftmostA = a.getLeftmostPoint()
        const leftmostB = b.getLeftmostPoint()
        const rightmostA = a.getRightmostPoint()
        const rightmostB = b.getRightmostPoint()

        const leftmost = leftmostA.x < leftmostB.x ? leftmostA : leftmostB
        const rightmost = rightmostA.x > rightmostB.x ? rightmostA : rightmostB
        return new Segment(leftmost, rightmost)
    }

    constructor(
        public readonly from: Point,
        public readonly to: Point,
    ) {
        if ( from.is(to) ) {
            console.log('new Segment', [from.coordinate, to.coordinate])
            throw new RangeError('Cannot create segment with same from and to points')
        }
    }

    get slope() {
        return (this.to.y - this.from.y) / (this.to.x - this.from.x)
    }

    get yIntercept() {
        return this.getXAtY(0)
    }

    getXAtY(y: number) {
        const y1 = this.from.y
        const x1 = this.from.x
        const slope = this.slope
        return ((y - y1) + (slope * x1)) / slope
    }

    getYAtX(x: number) {
        const y1 = this.from.y
        const x1 = this.from.x
        const slope = this.slope
        return (slope * (x - x1)) + y1
    }

    isHorizontal() {
        return Math.abs(this.slope) === 0
    }

    isVertical() {
        return Math.abs(this.slope) === Infinity
    }

    clone(): Segment {
        return new Segment(this.from.clone(), this.to.clone())
    }

    getOtherPoint(x: Point) {
        if ( this.from.is(x) ) return this.to
        return this.from
    }

    getLeftmostPoint() {
        return this.from.x < this.to.x ? this.from : this.to
    }

    getRightmostPoint() {
        return this.getOtherPoint(this.getLeftmostPoint())
    }

    is(x: Segment) {
        return (
            (
                x.from.is(this.from)
                && x.to.is(this.to)
            )
            || (
                x.from.is(this.to)
                && x.to.is(this.from)
            )
        )
    }

    containsPoint(x: Point) {
        if ( this.isHorizontal() ) {
            return (
                x.y === this.ymax
                && x.x >= this.xmin
                && x.x <= this.xmax
            )
        }

        if ( this.isVertical() ) {
            return (
                x.x === this.xmax
                && x.y >= this.ymin
                && x.y <= this.ymax
            )
        }

        return Point.from(this.getXAtY(x.y), this.getYAtX(x.x)).is(x)
    }

    yValueIsWithinRange(y: number, inclusive = true) {
        if ( inclusive ) {
            return y >= this.ymin && y <= this.ymax
        }

        return y > this.ymin && y < this.ymax
    }

    xValueIsWithinRange(x: number, inclusive = true) {
        if ( inclusive ) {
            return x >= this.xmin && x <= this.xmax
        }

        return x > this.xmin && x < this.xmax
    }

    hasPoint(x: Point) {
        return (
            this.from.is(x)
            || this.to.is(x)
        )
    }

    getIntersectionWithin(x: Segment): Point | undefined {
        const intersection = this.getIntersectionWith(x)

        if ( intersection ) {
            if ( !this.hasPoint(intersection) && !x.hasPoint(intersection) ) {
                return intersection
            }
        }
    }

    getIntersectionWith(seg: Segment): Point | undefined {
        const [x1, y1] = [this.from.x, this.from.y]
        const [x2, y2] = [this.to.x, this.to.y]
        const [x3, y3] = [seg.from.x, seg.from.y]
        const [x4, y4] = [seg.to.x, seg.to.y]

        const x12 = x1 - x2
        const x34 = x3 - x4
        const y12 = y1 - y2
        const y34 = y3 - y4

        const c = x12 * y34 - y12 * x34

        if ( !Math.abs(c) ) {
            return
        }

        const a = x1 * y2 - y1 * x2
        const b = x3 * y4 - y3 * x4

        const x = (a * x34 - b * x12) / c
        const y = (a * y34 - b * y12) / c

        const point = Point.from(x, y)
        if (
            this.xValueIsWithinRange(point.x)
            && seg.xValueIsWithinRange(point.x)
            && this.yValueIsWithinRange(point.y)
            && seg.yValueIsWithinRange(point.y)
        ) return point
    }

    getLength(): number {
        return Math.sqrt(
            Math.pow(this.to.x - this.from.x, 2)
            + Math.pow(this.to.y - this.from.y, 2)
        )
    }

    /**
     * Checks if a given point is to the left of this segment, if you were
     * to look at the segment standing at "from" toward "to".
     *
     * This returns true if the point is on the segment itself.
     *
     * @param x
     */
    pointIsLeftOf(x: Point) {
        // TODO replace with 3x3 determinant? See C. Du pg 24 (2)
        const det = (this.to.x - this.from.x) * (x.y - this.from.y) - (this.to.y - this.from.y) * (x.x - this.from.x)
        return det >= 0
    }

    split(): [Point, Segment, Segment] {
        const midpoint = Point.midpoint(this.from, this.to)
        return [midpoint, ...this.splitAt(midpoint)]
    }

    splitAt(x: Point): [Segment, Segment] {
        if ( !this.containsPoint(x) ) {
            console.log(
                'splitAt',
                [this.from.coordinate, this.to.coordinate],
                x.coordinate,
            )
            throw new RangeError('Cannot split segment on point that does not occur on segment')
        }

        const segment1 = new Segment(this.from, x)
        const segment2 = new Segment(x, this.to)
        return [segment1, segment2]
    }

    getMidpoint(): Point {
        return Point.midpoint(this.from, this.to)
    }

    get xmin() {
        return Math.min(this.from.x, this.to.x)
    }

    get xmax() {
        return Math.max(this.from.x, this.to.x)
    }

    get ymin() {
        return Math.min(this.from.y, this.to.y)
    }

    get ymax() {
        return Math.max(this.from.y, this.to.y)
    }

    toQuickDisplay() {
        return [this.from.coordinate, this.to.coordinate]
    }
}

export class Circle {
    constructor(
        public readonly center: Point,
        public readonly radius: number,
    ) { }

    containsPoint(x: Point) {
        const distance = (
            Math.pow(x.x - this.center.x, 2)
            + Math.pow(x.y - this.center.y, 2)
        )

        return distance <= Math.pow(this.radius, 2)
    }

    containsPointWithin(x: Point) {
        const distance = (
            Math.pow(x.x - this.center.x, 2)
            + Math.pow(x.y - this.center.y, 2)
        )

        return distance < Math.pow(this.radius, 2)
    }
}

export class Trapezoid {
    constructor(
        public readonly points: [Point, Point, Point, Point],
        public readonly segments: [Segment, Segment, Segment, Segment],
    ) {
        if ( !this.validateSegments() ) {
            throw new Error('Attempted to create Trapezoid with invalid points/segments.')
        }
    }

    public validateSegments() {
        const points: Point[] = []
        this.segments.some(side => {
            if ( !points.some(point => point.is(side.from)) ) points.push(side.from)
            if ( !points.some(point => point.is(side.to)) ) points.push(side.to)
        })

        if ( !Trapezoid.distinctPoints(...points as [Point, Point, Point, Point]) ) {
            return false
        }

        if ( points.length !== 4 ) {
            return false
        }

        const sidesByPoint: Segment[][] = [[], [], [], []]
        for ( const side of this.segments ) {
            const toPointIndex = points.findIndex(point => point.is(side.to))
            const fromPointIndex = points.findIndex(point => point.is(side.from))

            if ( !sidesByPoint[toPointIndex].some(seg => seg.is(side)) )
                sidesByPoint[toPointIndex].push(side)

            if ( !sidesByPoint[fromPointIndex].some(seg => seg.is(side)) )
                sidesByPoint[fromPointIndex].push(side)
        }

        return sidesByPoint.every(group => group.length === 2)
    }

    public static distinctPoints(p1: Point, p2: Point, p3: Point, p4: Point) {
        return Point.distinct([p1, p2, p3, p4]).length === 4
    }
}

/**
 * Use the convention that:
 *
 * Vertex a: 0-from / 2-to
 * Vertex b: 1-from / 0-to
 * Vertex c: 2-from / 1-to
 */
export class Triangle {
    get a(): Point {
        return this.getPoints()[0]
    }

    get b(): Point {
        return this.getPoints()[1]
    }

    get c(): Point {
        return this.getPoints()[2]
    }

    get orderedSides(): [Segment, Segment, Segment] {
        return this.sides.sort((a, b) => {
            if ( a.from.x !== b.from.x ) {
                return a.from.x - b.from.x
            }

            return a.from.y - b.from.y
        })
    }

    constructor(
        public readonly sides: [Segment, Segment, Segment]
    ) {
        if ( !this.validateSides() ) {
            console.log(
                [this.sides[0].from.coordinate, this.sides[0].to.coordinate],
                [this.sides[1].from.coordinate, this.sides[1].to.coordinate],
                [this.sides[2].from.coordinate, this.sides[2].to.coordinate],
            )
            throw new Error('Tried to create Triangle with invalid sides.')
        }
    }

    public validateSides(): boolean {
        const points: Point[] = []
        this.sides.some(side => {
            if ( !points.some(point => point.is(side.from)) ) points.push(side.from)
            if ( !points.some(point => point.is(side.to)) ) points.push(side.to)
        })

        if ( !Triangle.distinctPoints(...points as [Point, Point, Point]) ) {
            return false
        }

        if ( points.length !== 3 ) {
            return false
        }

        const sidesByPoint: Segment[][] = [[], [], []]
        for ( const side of this.sides ) {
            const toPointIndex = points.findIndex(point => point.is(side.to))
            const fromPointIndex = points.findIndex(point => point.is(side.from))

            if ( !sidesByPoint[toPointIndex].some(seg => seg.is(side)) )
                sidesByPoint[toPointIndex].push(side)

            if ( !sidesByPoint[fromPointIndex].some(seg => seg.is(side)) )
                sidesByPoint[fromPointIndex].push(side)
        }

        return sidesByPoint.every(group => group.length === 2)
    }

    clone(): Triangle {
        const [s1, s2, s3] = this.sides.map(x => x.clone())
        return new Triangle([s1, s2, s3])
    }

    is(x: Triangle) {
        return this.orderedSides.every((side, i) => x.orderedSides[i].is(side))
    }

    hasSegment(x: Segment) {
        return !this.sides.some(side => side.is(x))
    }

    hasPoint(x: Point) {
        return !this.sides.some(side => side.hasPoint(x))
    }

    /** Get the angles of the vertices a, b, c, respectively. */
    getAngles(): [Angle, Angle, Angle] {
        const a = Triangle.getAngleFrom(this.b, this.a, this.c)
        const b = Triangle.getAngleFrom(this.a, this.b, this.c)
        const c = Triangle.getAngleFrom(this.b, this.c, this.a)
        return [a, b, c]
    }

    getMinimumAngle(): Angle {
        return deg2rad(
            Math.min(...this.getAngles().map(x => rad2degp(x)))
        )
    }

    /** Get the points of the triangle a, b, c, respectively. */
    getPoints(): [Point, Point, Point] {
        let points: Point[] = []
        this.sides.some(side => {
            if ( !points.some(point => point.is(side.from)) ) points.push(side.from)
            if ( !points.some(point => point.is(side.to)) ) points.push(side.to)
        })

        points = points.sort((a, b) => {
            if ( a.x === b.x ) return a.y - b.y
            return a.x - b.x
        })

        return [points[0], points[1], points[2]]
    }

    getCircumcenter(): Point {
        const [pointA, pointB, pointC] = this.getPoints()

        const [sin2A, sin2B, sin2C] = this.getAngles().map(x => Math.sin(2 * x))

        const x = ((pointA.x * sin2A) + (pointB.x * sin2B) + (pointC.x * sin2C))
            / (sin2A + sin2B + sin2C)

        const y = ((pointA.y * sin2A) + (pointB.y * sin2B) + (pointC.y * sin2C))
            / (sin2A + sin2B + sin2C)

        return Point.from(x, y)
    }

    getCircumcenterCircle(): Circle {
        const center = this.getCircumcenter()
        const radius = (new Segment(center, this.a)).getLength()
        return new Circle(center, radius)
    }

    public static distinctPoints(p1: Point, p2: Point, p3: Point) {
        return Point.distinct([p1, p2, p3]).length === 3
    }

    public static getAngleFrom(p2: Point, p1: Point, p3: Point): Angle {
        const numerator = p2.y * (p1.x - p3.x) + p1.y * (p3.x - p2.x) + p3.y * (p2.x - p1.x)
        const denominator = (p2.x - p1.x) * (p1.x - p3.x) + (p2.y - p1.y) * (p1.y - p3.y)
        const radio = numerator / denominator
        return Math.atan(radio)
    }
}

export enum GraphDirection {
    UP,
    DOWN,
    LEFT,
    RIGHT,
}

export interface SegmentWithIntersection {
    segment: Segment,
    intersect: Point,
}

export function getDirectionSorter(direction: GraphDirection) {
    if ( direction === GraphDirection.UP ) {
        return (a: SegmentWithIntersection, b: SegmentWithIntersection) => {
            return a.intersect.y - b.intersect.y  // get the lowest y-value first
        }
    } else if ( direction === GraphDirection.DOWN ) {
        return (a: SegmentWithIntersection, b: SegmentWithIntersection) => {
            return b.intersect.y - a.intersect.y  // get the highest y-value first
        }
    } else if ( direction === GraphDirection.LEFT ) {
        return (a: SegmentWithIntersection, b: SegmentWithIntersection) => {
            return b.intersect.x - a.intersect.x  // get the right-most x value first
        }
    } else {
        return (a: SegmentWithIntersection, b: SegmentWithIntersection) => {
            return a.intersect.x - b.intersect.x  // get the left-most x-value first
        }
    }
}

export class GraphBoundary {
    constructor(
        public readonly points: Point[],
        public readonly segments: Segment[],
    ) { }

    getLeftBoundary(): Segment {
        const left = this.segments.find(segment => segment.from.x === this.xmin && segment.to.x === this.xmin)
        if ( !left ) throw new RangeError('Unable to find left boundary')
        return left
    }

    getRightBoundary(): Segment {
        const right = this.segments.find(segment => segment.from.x === this.xmax && segment.to.x === this.xmax)
        if ( !right ) throw new RangeError('Unable to find right boundary')
        return right
    }

    getUpperBoundary(): Segment {
        const top = this.segments.find(segment => segment.from.y === this.ymax && segment.to.y === this.ymax)
        if ( !top ) throw new RangeError('Unable to find upper boundary')
        return top
    }

    getLowerBoundary(): Segment {
        const bottom = this.segments.find(segment => segment.from.y === this.ymin && segment.to.y === this.ymin)
        if ( !bottom ) throw new RangeError('Unable to find lower boundary')
        return bottom
    }

    getBoundary(direction: GraphDirection) {
        if ( direction === GraphDirection.UP ) return this.getUpperBoundary()
        else if ( direction === GraphDirection.DOWN ) return this.getLowerBoundary()
        else if ( direction === GraphDirection.LEFT ) return this.getLeftBoundary()
        else return this.getRightBoundary()
    }

    leftNeighbor(to: Point): Point {  // NP1
        const i = this.points.findIndex(point => point.is(to))
        if ( i < 0 ) throw new Error('Cannot find neighbor of point not on boundary.')

        const neighbor = (i-1) < 0 ? this.points.length - 1 : i - 1
        return this.points[neighbor]
    }

    rightNeighbor(to: Point) {  // NP2
        const i = this.points.findIndex(point => point.is(to))
        if ( i < 0 ) throw new Error('Cannot find neighbor of point not on boundary.')

        const neighbor = (i+1) >= this.points.length ? 0 : i + 1
        return this.points[neighbor]
    }

    isBoundaryPoint(x: Point) {
        return this.points.some(point => point.is(x))
    }

    isBoundarySegment(x: Segment) {
        return this.segments.some(segment => segment.is(x))
    }

    containsPoint(x: Point) {
        return (
            x.x >= this.xmin
            && x.x <= this.xmax
            && x.y >= this.ymin
            && x.y <= this.ymax
        )
    }

    containsPointWithin(x: Point) {
        return (
            x.x > this.xmin
            && x.x < this.xmax
            && x.y > this.ymin
            && x.y < this.ymax
        )
    }

    // TODO centralize into a ContainsPointsAndSegments base class
    get xmin() {
        return Math.min(
            ...this.points.map(point => point.x)
        )
    }

    get xmax() {
        return Math.max(
            ...this.points.map(point => point.x)
        )
    }

    get ymin() {
        return Math.min(
            ...this.points.map(point => point.y)
        )
    }

    get ymax() {
        return Math.max(
            ...this.points.map(point => point.y)
        )
    }
}

export class Graph {
    public readonly vertices: Point[] = []
    public readonly edges: Segment[] = []

    constructor(
        public points: Point[] = [],
        public segments: Segment[] = [],
        public triangles: Triangle[] = [],
    ) {
        this.vertices = [...points.map(x => x.clone())]
        this.edges = [...segments.map(x => x.clone())]
    }

    get xmin() {
        return Math.min(
            ...this.points.map(point => point.x)
        )
    }

    get xmax() {
        return Math.max(
            ...this.points.map(point => point.x)
        )
    }

    get ymin() {
        return Math.min(
            ...this.points.map(point => point.y)
        )
    }

    get ymax() {
        return Math.max(
            ...this.points.map(point => point.y)
        )
    }

    get span() {
        return Math.max(
            this.xmax - this.xmin,
            this.ymax - this.ymin
        )
    }

    get center(): Point {
        const xmax = Point.from(this.xmax, 0)
        const xmin = Point.from(this.xmin, 0)
        const xmid = Point.midpoint(xmin, xmax)

        const ymax = Point.from(0, this.ymax)
        const ymin = Point.from(0, this.ymin)
        const ymid = Point.midpoint(ymin, ymax)

        return Point.from(xmid.x, ymid.y)
    }

    findExistingPointOrAdd(x: Point): Point {
        const existing = this.points.find(point => point.is(x))
        if ( existing ) return existing

        this.points.push(x)
        return x
    }

    findExistingSegmentOrAdd(x: Segment): Segment {
        const existing = this.segments.find(segment => segment.is(x))
        if ( existing ) return existing

        this.segments.push(x)
        this.findExistingPointOrAdd(x.from)
        this.findExistingPointOrAdd(x.to)
        return x
    }

    hasExistingSegment(x: Segment) {
        return this.segments.some(segment => segment.is(x))
    }

    findExistingTriangleOrAdd(x: Triangle): Triangle {
        const existing = this.triangles.find(triangle => triangle.is(x))
        if ( existing ) return existing

        this.triangles.push(x)
        return x
    }

    getFreePoints(): Point[] {
        return this.points.filter(point => {
            return !this.segments.some(segment => segment.hasPoint(point))
        })
    }

    getSegmentsEndingAt(point: Point): Segment[] {
        return this.segments.filter(segment => segment.hasPoint(point))
    }

    removeSegment(x: Segment) {
        this.segments = this.segments.filter(segment => !segment.is(x))
    }

    clone() {
        const newPoints: Point[] = this.points.map(point => point.clone())

        const newSegments = this.segments.map(segment => {
            const newFrom = newPoints.find(point => point.is(segment.from))
            const newTo = newPoints.find(point => point.is(segment.to))
            if ( !newFrom || !newTo ) {
                console.log({from: segment.from.coordinate, to: segment.to.coordinate})
                throw new Error('Tried to clone segment, but could not match all points')
            }

            return new Segment(newFrom, newTo)
        })

        const newTriangles = this.triangles.map(triangle => {
            const side0 = newSegments.find(segment => segment.is(triangle.sides[0]))
            const side1 = newSegments.find(segment => segment.is(triangle.sides[1]))
            const side2 = newSegments.find(segment => segment.is(triangle.sides[2]))
            if ( !side0 || !side1 || !side2 ) {
                throw new Error('Tried to clone triangle, but could not match all sides')
            }

            return new Triangle([side0, side1, side2])
        })

        return new Graph(newPoints, newSegments, newTriangles)
    }
}

export function addBoundingSquareTo(graph: Graph): GraphBoundary {
    const span = graph.span
    const sideLength = 3 * span
    const halfSideLength = sideLength / 2
    const center = graph.center

    const bottomLeftBound = Point.from(center.x - halfSideLength, center.y - halfSideLength)
    const bottomRightBound = Point.from(center.x + halfSideLength, center.y - halfSideLength)
    const topLeftBound = Point.from(center.x - halfSideLength, center.y + halfSideLength)
    const topRightBound = Point.from(center.x + halfSideLength, center.y + halfSideLength)

    const bottomLeft = graph.findExistingPointOrAdd(bottomLeftBound)
    const bottomRight = graph.findExistingPointOrAdd(bottomRightBound)
    const topLeft = graph.findExistingPointOrAdd(topLeftBound)
    const topRight = graph.findExistingPointOrAdd(topRightBound)

    const bottom = graph.findExistingSegmentOrAdd(new Segment(bottomLeft, bottomRight))
    const right = graph.findExistingSegmentOrAdd(new Segment(bottomRight, topRight))
    const left = graph.findExistingSegmentOrAdd(new Segment(bottomLeft, topLeft))
    const top = graph.findExistingSegmentOrAdd(new Segment(topLeft, topRight))

    return new GraphBoundary(
        [bottomLeft, bottomRight, topRight, topLeft],
        [bottom, right, top, left]
    )
}