slicing of polygon

index.ts

interface Point {
    x: number
    y: number
}
type Ring = Point[]
interface Joint {
    i: number
    j: number
    k: number
    p: Point
    removed?: boolean
}
function lerp2(a: Point, b: Point, f: number) {
    return {
        x: a.x * (1 - f) + b.x * f,
        y: a.y * (1 - f) + b.y * f,
    }
}
function slice(rings: Ring[], dir: number, pos: number, side = 1) {
    const joints = [] as Joint[],
        ends = rings.map(ring => ring.map(pt => [] as Joint[]))
    for (const [k, r] of rings.entries()) {
        const e = ends[k]
        for (let i = 0, n = r.length; i < n; i ++) {
            const j = (i + 1) % n,
                [a, b] = [r[i], r[j]],
                test = dir === 0 ? (a.x - pos) * (b.x - pos) : (a.y - pos) * (b.y - pos),
                fac  = dir === 0 ? (a.x - pos) / (a.x - b.x) : (a.y - pos) / (a.y - b.y)
            if (test < 0) {
                const p = lerp2(a, b, fac),
                    joint = { i, j, k, p }
                joints.push(joint)
                e[i].push(joint)
                e[j].push(joint)
            }
        }    
    }
    joints.sort((a, b) => dir === 0 ? a.p.y - b.p.y : a.p.x - b.p.x)
    if (joints.length % 2 !== 0) {
        throw Error('polygon seems not closed')
    }

    const ret = [] as Point[][]
    let idx
    while ((idx = joints.findIndex(j => !j.removed)) >= 0) {
        let [a, b] = joints.slice(idx, idx + 2) as (Joint | undefined)[]
        const ring = [] as Point[]
        while (a && b) {
            ring.push(a.p, b.p)
            a.removed = b.removed = true

            const [r, e] = [rings[b.k], ends[b.k]],
                inversed = ((dir === 0 ? r[b.i].x : r[b.i].y) - pos) * side > 0
            let [i, d] = inversed ? [b.i, -1] : [b.j, 1]
            while (true) {
                ring.push(r[i])
                let joint = e[i].find(j => j !== b)
                if (joint) {
                    if (joint.removed) {
                        a = b = undefined
                    } else {
                        a = joint
                        b = joints[joints.indexOf(joint) + 1]
                    }
                    break
                } else {
                    i = (i + d) % r.length
                }
            }
        }
        ret.push(ring)
    }
    return ret
}
function makePoly(arr: [number, number][][]) {
    return arr.map(pts => pts.map(([x, y]) => ({ x, y })))
}
function makePath(rings: Ring[], stroke = 'black') {
    return rings.map(ring => {
        const points = ring.map(pt => `${pt.x},${pt.y}`).join(' ')
        return `<polygon points="${points}" fill="none" stroke="${stroke}" />`
    }).join('\n')
}

const input = makePoly([
    [
        [100, 100],
        [200, 100],
        [200, 200],
        [120, 200],
        [120, 300],
        [300, 300],
        [300,  80],
        [100,  80],
        [100,  50],
        [400,  50],
        [400, 400],
        [100, 400],
    ],
    [
        [120, 120],
        [180, 120],
        [180, 180],
        [120, 180],
    ],
    [
        [140, 140],
        [160, 140],
        [160, 160],
        [140, 160],
    ],
])
const output = slice(input, 0, 150, 1)

const div = document.createElement('div')
document.body.appendChild(div)
div.innerHTML = `<svg width="100%" height="100%">
${makePath(input, 'black')}
${makePath(output, 'blue')}
</svg>`