geometry-2d.js

/**
 * A collection of utility functions for working with 2d geometry:
 * Polygons, Segments, Lines & Points
 * 
 * @author Lara Sophie Schütt (@literallylara)
 * @license MIT
 */

/**
 * @typedef {[x:Number,y:Number]} Point2D
 * @typedef {[[px:Number,py:Number],[nx:Number,ny:Number]]} Line2D
 * @typedef {[[x1:Number,y1:Number],[x2:Number,y2:Number]]} Segment2D
 * @typedef {Array<Point2D>} Polygon2D
 */

/**
 * Test whether line `a` intersects with line `b`  
 * by checking for a solution where `Pa + Na * s = Pb + Nb * t`.
 * @param {Line2D} a 
 * @param {Line2D} b 
 * @returns {Boolean}
 */
export function query_line_line(a, b)
{
    const na = a[1]
    const nb = b[1]

    // p + n * s = q + m * t
    
    // px + nx * s = qx + mx * t             | (I)
    // px + nx * s = qx + mx * t             | - px
    //      nx * s = qx + mx * t - px        | : nx
    //           s = (qx + mx * t - px) / nx | (I')
    
    // py + ny * s =  qy + my * t            | (II)
    // py + ny * s =  qy + my * t            | - py
    //      ny * s =  qy + my * t - py       | : ny
    //           s = (qy + my * t - py) / ny | (II')

    // (I') = (II')
    // (qy + my * t - py) / ny       = (qx + mx * t - px) / nx                  | * nx
    // (qy + my * t - py) / ny * nx  =  qx + mx * t - px                        | * ny
    // (qy + my * t - py) * nx       = (qx + mx * t - px) * ny                  | + nx * (py - qy)
    //       my * t       * nx       = (qx + mx * t - px) * ny + nx * (py - qy) | - ny * (mx * t)
    //      (my * nx - ny * mx) * t  = (qx - px) * ny + nx * (py - qy)          | : (my * nx - ny * mx)

    // t = (ny * (qx - px) - nx * (qy - py)) / (nx * my - ny * mx)

    const det = na[0] * nb[1] - na[1] * nb[0]

    if (det === 0) return false

    return true
}

/**
 * Test whether segment `a` intersects with segment `b`  
 * by checking for a solution where `Pa + Na * s = Pb + Nb * t`  
 * with `0 <= s <= 1` and `0 <= t <= 1`.
 * @param {Segment2D} a 
 * @param {Segment2D} b 
 * @returns {Boolean}
 * - `false` = they ***don't*** intersect
 * - `true` = they ***do*** intersect
 */
export function query_segment_segment(a, b)
{
    const pa = a[0]
    const pb = b[0]
 
    const na = vec2_sub(a[1], a[0])
    const nb = vec2_sub(b[1], b[0])

    const det = na[0] * nb[1] - na[1] * nb[0]

    if (det === 0 || na[1] === 0) return false

    const t = (na[1] * (pb[0] - pa[0]) - na[0] * (pb[1] - pa[1])) / det

    if (t <= 0 || t >= 1) return false

    const s = (pb[1] + nb[1] * t - pa[1]) / na[1]

    if (s <= 0 || s >= 1) return false

    return true
}

/**
 * Determine the direction of point `a` in relation to line `b`  
 * by looking at the sign of the dot product between  
 * `a` relative to `b`'s origin and `b`'s normal vector.
 * @param {Point2D} a 
 * @param {Line2D} b 
 * @returns {Number}
 * - `-1` = `a` left to `b`
 * - `+1` = `a` right to `b`
 * -  `0` = `a` on `b`
 */
export function query_point_line(a, b)
{
    const va = vec2_sub(a, b[0])
    const vb = vec2_sub(b[1], b[0])

    const d = vec2_dot([-vb[1], vb[0]], va)

    if (d === 0) return 0

    return d > 0 ? -1 : 1
}

/**
 * Determine the containment between point `a` and polygon `b`  
 * by checking if point `a` is left or right to each of `b`'s  
 * segments depending on `b`'s winding order.  
 * 
 * `b` must be convex.
 * @param {Point2D} a 
 * @param {Polygon2D} b 
 * @returns {Number}
 * - `-1` = `a` outside `b`
 * - `+1` = `a` inside `b`
 * -  `0` = `a` on `b`
 */
export function query_point_poly(a, b)
{
    b = close_poly(b)

    const w = get_winding_order(b)

    for (let i = 0; i < b.length - 1; i++)
    {
        const q = query_point_line(a, [b[i], b[i + 1]])

        if (q === 0) return 0

        if (Math.sign(q) !== w) return -1
    }

    return 1
}

/**
 * Determine the containment between polygon `a` and polygon `b`  
 * by looking for individual segment intersections and lastly checking if  
 * a vertex from `a` lies within `b`.  
 * 
 * `a` and `b` must be convex.
 * @param {Point2D} a 
 * @param {Polygon2D} b 
 * @returns {Number}
 * - `-1` if `a` outside `b`
 * - `+1` if `a` inside `b`
 * -  `0` if `a` on `b`
 */
export function query_poly_poly(a, b)
{
    // If no segments intersect and at least one segment
    // is inside B then A is inside B.
    
    a = close_poly(a)
    b = close_poly(b)

    for (let i = 0; i < a.length - 1; i++)
    {
        const sa = [a[i], a[i + 1]]
        
        for (let j = 0; j < b.length - 1; j++)
        {
            const sb = [b[j], b[j + 1]]

            if (query_segment_segment(sa, sb)) return 0
        }
    }
    // Given that there are no intersections up until this point,
    // if the very first point of A lies inside B then all other
    // segments must also lie within b since otherwise there would be
    // an intersection and vice versa.

    return query_point_poly(a[0], b)
}

/**
 * Determine a convex polygon's winding order  
 * by looking at the direction of the third vertex
 * relative to the first segment.
 * @param {Polygon2D} p 
 * @returns {Number}
 * - `-1` = Left
 * - `+1` = Right
 */
export function get_winding_order(p)
{
    return query_point_line(p[2], [p[0], p[1]])
}

/**
 * @param {Polygon2D} p
 * @returns {Boolean}
 * A boolean indicating the given polygon's convexity 
 * by checking for self intersections and segment direction changes.
 */
export function is_poly_convex(p)
{
    p = open_poly(p)

    const w = get_winding_order(p)

    for (let i = 1; i < p.length; i++)
    {
        const p1 = p[i % p.length]
        const p2 = p[(i + 1) % p.length]
        const p3 = p[(i + 2) % p.length]

        const q = query_point_line(p3, [p1, p2])

        if (w != q) return false
    }

    p = close_poly(p)

    for (let i = 0; i < p.length - 1; i++)
    {
        const sa = [p[i], p[i + 1]]
        
        for (let j = i; j < p.length - 1; j++)
        {
            const sb = [p[j], p[j + 1]]

            if (query_segment_segment(sa, sb)) return false
        }
    }

    return true
}

/**
 * @param {Polygon2D} p
 * @returns {Boolean}
 * A boolean indicating the given polygon's concavity 
 * by checking for self intersections and segment direction changes.
 */
export function is_poly_concave(p)
{
    return !is_poly_convex(p)
}

/**
 * Closes the given polygon by appending the
 * first vertex to the end if necessary.
 * @param {Polygon2D} p 
 * @returns {Polygon2D}
 * The modified input polygon `p`.
 */
export function close_poly(p)
{
    const i = p.length - 1

    if (p[0][0] !== p[i][0] || p[0][1] !== p[i][1])
    {
        p = p.slice(0)
        p.push(p[0])
    }

    return p
}

/**
 * Opens the given polygon by removing the
 * last vertex if it is equal to the first.
 * @param {Polygon2D} p 
 * @returns {Polygon2D}
 * The modified input polygon `p`.
 */
export function open_poly(p)
{
    const i = p.length - 1

    if (p[0][0] === p[i][0] && p[0][1] === p[i][1])
    {
        p = p.slice(0, -1)
    }

    return p
}

/**
 * Make the given Polygon2D convex by removing any segments that do not follow
 * the average segment direction.
 * @param {Polygon2D} p 
 * @returns {Polygon2D}
 * The modified input polygon `p`.
 */
export function make_convex(p)
{
    if (is_poly_convex(p)) return p

    let w  = 0
    let lw = 0
    let rw = 0

    p = open_poly(p)

    for (let i = 1; i < p.length; i++)
    {
        const p1 = p[i % p.length]
        const p2 = p[(i + 1) % p.length]
        const p3 = p[(i + 2) % p.length]

        const q = query_point_line(p3, [p1, p2])

        if (q === -1) lw++
        else if (q === 1) rw++
    }

    w = lw > rw ? -1 : 1

    for (let i = 1; i < p.length; i++)
    {
        const p1 = p[i % p.length]
        const p2 = p[(i + 1) % p.length]
        const p3 = p[(i + 2) % p.length]

        const q = query_point_line(p3, [p1, p2])

        if (w !== q)
        {
            p.splice(i + 2, 1)
        }
    }

    return p
}

/**
 * @param {Number} x 
 * X-coordinates of the first vertex
 * @param {Number} y 
 * Y-coordinates of the first vertex
 * @param {Number} a
 * The angle of the line 
 * @returns {Line2D}
 * A Line2D of length 1 with a given angle.
 */
export function create_line(x, y, a)
{
    return [[x, y], [x + Math.cos(a), y + Math.sin(a)]]
}

/**
 * @param {Number} x1
 * X-coordinates of the first vertex
 * @param {Number} y1
 * Y-coordinates of the first vertex
 * @param {Number} x2
 * X-coordinates of the second vertex
 * @param {Number} y2
 * Y-coordinates of the second vertex
 * @returns {Segment2D}
 * A Segment2D with the given vertices.
 */
export function create_segment(x1, y1, x2, y2)
{
    return [[x1, y1], [x2, y2]]
}

/**
 * @param {Number} cx Center X-coordinate
 * @param {Number} cy Center Y-coordinate
 * @param {Number} n Amount of sides
 * @param {Number} r Radius
 * @returns {Polygon2D}
 * An regular Polygon2D with the given parameters.
 */
export function create_ngon(cx, cy, n, r)
{
    const a = Math.PI * 2 / n
    const v = []

    for (let i = 0; i < n; i++)
    {
        v.push([
            cx + Math.cos(a * i) * r,
            cy + Math.sin(a * i) * r
        ])
    }

    return v
}

/**
 * @param {Number} cx
 * Center X-coordinate
 * @param {Number} cy 
 * Center Y-coordinate
 * @param {Number} w 
 * Width
 * @param {Number} h 
 * Height
 * @param {Number} a 
 * Rotation angle
 * @returns {Polygon2D}
 * A Polygon2D representing a rectangle with the given parameters.
 */
export function create_rect(cx, cy, w, h, a)
{
    const verts =
    [
        [cx - w / 2, cy - h / 2],
        [cx + w / 2, cy - h / 2],
        [cx + w / 2, cy + h / 2],
        [cx - w / 2, cy + h / 2]
    ]

    if (a)
    {
        for (let i = 0; i < verts.length; i++)
        {
            verts[i] = vec2_rot(verts[i], a, [cx, cy])
        }
    }

    return verts
}

// Utility functions

function vec2_rot(v, a, o = [0, 0])
{
    const c = Math.cos(a)
    const s = Math.sin(a)

    const x = v[0] - o[0]
    const y = v[1] - o[1]

    return [
        x * c - y * s + o[0],
        x * s + y * c + o[1]
    ]
}

function vec2_dot(a, b)
{
    return a[0] * b[0] + a[1] * b[1]
}

function vec2_sub(a, b)
{
    return [
        a[0] - b[0],
        a[1] - b[1]
    ]
}