mesh/src/delaunayRefine.ts

import {addBoundingSquareTo, Angle, Graph, GraphBoundary, Point, rad2deg, rad2degp, Segment, Triangle} from "./pslg";

export function addTriangle(graph: Graph, boundary: GraphBoundary, segment: Segment) {
    let p1 = segment.from
    let p2 = segment.to

    // Want to order p1 and p2 such that p2 is the right neighbor of p1
    if ( !boundary.rightNeighbor(p1).is(p2) ) {
        let temp = p1
        p1 = p2
        p2 = temp
    }

    // Get a segment with the ordered from/to
    // So, looking from p1 to p2, points on the "left side" of the line
    // are within the boundary
    const orderedSegment = new Segment(p1, p2)

    // Collect all points that could form valid triangles
    const possiblePoints: {angle: number, point: Point}[] = []

    // Find some p3 such that p1p2p3 is Delaunay (<p1p3p2 is the largest angle)
    for ( const point of graph.points ) {
        if ( point.is(p1) || point.is(p2) ) continue

        // Check if the point is within boundary -- excluding boundary points themselves
        if ( !boundary.containsPointWithin(point) ) continue

        // TODO Check if the point is within the search region

        // Check if the point is on the left-side of segment
        if ( !orderedSegment.pointIsLeftOf(point) ) continue

        possiblePoints.push({
            angle: Triangle.getAngleFrom(p1, point, p2),
            point,
        })
    }

    // Sort the possible points to find the one with the largest angle
    const sortedPossiblePoints = possiblePoints.sort((a, b) => {
        const aDeg = rad2degp(a.angle)
        const bDeg = rad2degp(b.angle)
        return bDeg - aDeg
    })

    // Go through the sorted points and find one that forms a valid triangle
    for ( const {point} of sortedPossiblePoints ) {
        const seg13 = new Segment(p1, point)
        const seg23 = new Segment(p2, point)

        // Make sure the legs that would form from this triangle wouldn't intersect
        // with the boundary segment except at p1 and p2
        if ( segment.getIntersectionWithin(seg13) || segment.getIntersectionWithin(seg23) ) {
            continue
        }

        // We found a valid 3rd point for this triangle!
        const graphSeg13 = graph.findExistingSegmentOrAdd(seg13)
        const graphSeg23 = graph.findExistingSegmentOrAdd(seg23)
        const graphSeg12 = graph.findExistingSegmentOrAdd(segment)

        graph.findExistingTriangleOrAdd(new Triangle([graphSeg13, graphSeg23, graphSeg12]))
        break
    }
}

export function delaunay(originalGraph: Graph): Graph {
    const graph = originalGraph.clone()
    const boundary = addBoundingSquareTo(graph)

    // for ( const segment of boundary.segments ) {
    //     addTriangle(graph, boundary, segment)
    //     break
    // }
    // const segment = boundary.segments[0]
    // addDelaunayTriangle(graph, boundary, segment)

    for ( const point of graph.points ) {

    }

    return graph
}

export function delaunayRefine(originalGraph: Graph, minAngle: Angle): Graph {
    const graph = originalGraph.clone()

    addBoundingSquareTo(graph)

    return graph
}