Get a visibility polygon (for shadow casting).

visibility-polygon.ts

// segments are all of the segments in all of the shapes in the scene
// point is light point
// viewport is top left, top right, bottom right, bottom left
function getVisibilityPolygon(segments: Segment[], point: Point, viewport: Point[]) {
	const brokenSegments: Segment[] = []

	const viewportMinCorner = viewport[0]
	const viewportMaxCorner = viewport[2]

	for (let i = 0; i < segments.length; ++i) {
		if (segments[i][0][0] < viewportMinCorner[0] && segments[i][1][0] < viewportMinCorner[0])
			continue
		if (segments[i][0][1] < viewportMinCorner[1] && segments[i][1][1] < viewportMinCorner[1])
			continue
		if (segments[i][0][0] > viewportMaxCorner[0] && segments[i][1][0] > viewportMaxCorner[0])
			continue
		if (segments[i][0][1] > viewportMaxCorner[1] && segments[i][1][1] > viewportMaxCorner[1])
			continue
		const intersections: Point[] = []
		for (let j = 0; j < viewport.length; ++j) {
			let k = j + 1
			if (k == viewport.length) k = 0
			if (
				doLineSegmentsIntersect(
					segments[i][0][0],
					segments[i][0][1],
					segments[i][1][0],
					segments[i][1][1],
					viewport[j][0],
					viewport[j][1],
					viewport[k][0],
					viewport[k][1]
				)
			) {
				const intersect = intersectLines(segments[i][0], segments[i][1], viewport[j], viewport[k])
				if (!intersect) continue
				if (equal(intersect, segments[i][0]) || equal(intersect, segments[i][1])) continue
				intersections.push(intersect)
			}
		}
		const start: Point = [segments[i][0][0], segments[i][0][1]]
		while (intersections.length > 0) {
			let endIndex = 0
			let endDis = distance(start, intersections[0])
			for (let j = 1; j < intersections.length; ++j) {
				const dis = distance(start, intersections[j])
				if (dis < endDis) {
					endDis = dis
					endIndex = j
				}
			}
			brokenSegments.push([
				[start[0], start[1]],
				[intersections[endIndex][0], intersections[endIndex][1]],
			])
			start[0] = intersections[endIndex][0]
			start[1] = intersections[endIndex][1]
			intersections.splice(endIndex, 1)
		}
		brokenSegments.push([start, [segments[i][1][0], segments[i][1][1]]])
	}

	const viewportSegments: Segment[] = []
	for (let i = 0; i < brokenSegments.length; ++i) {
		if (
			inViewport(brokenSegments[i][0], viewportMinCorner, viewportMaxCorner) &&
			inViewport(brokenSegments[i][1], viewportMinCorner, viewportMaxCorner)
		) {
			viewportSegments.push([
				[brokenSegments[i][0][0], brokenSegments[i][0][1]],
				[brokenSegments[i][1][0], brokenSegments[i][1][1]],
			])
		}
	}

	const eps = epsilon * 10

	viewportSegments.push([
		[viewportMinCorner[0] - eps, viewportMinCorner[1] - eps],
		[viewportMaxCorner[0] + eps, viewportMinCorner[1] - eps],
	])
	viewportSegments.push([
		[viewportMaxCorner[0] + eps, viewportMinCorner[1] - eps],
		[viewportMaxCorner[0] + eps, viewportMaxCorner[1] + eps],
	])
	viewportSegments.push([
		[viewportMaxCorner[0] + eps, viewportMaxCorner[1] + eps],
		[viewportMinCorner[0] - eps, viewportMaxCorner[1] + eps],
	])
	viewportSegments.push([
		[viewportMinCorner[0] - eps, viewportMaxCorner[1] + eps],
		[viewportMinCorner[0] - eps, viewportMinCorner[1] - eps],
	])

	return compute(point, viewportSegments)
}

type Point = number[]
type Segment = number[][]

const epsilon = 0.0000001

function angle(a: Point, b: Point) {
	return (Math.atan2(b[1] - a[1], b[0] - a[0]) * 180) / Math.PI
}

function angle2(a: Point, b: Point, c: Point) {
	const a1 = angle(a, b)
	const a2 = angle(b, c)
	let a3 = a1 - a2
	if (a3 < 0) a3 += 360
	if (a3 > 360) a3 -= 360
	return a3
}

function equal(a: Point, b: Point) {
	if (Math.abs(a[0] - b[0]) < epsilon && Math.abs(a[1] - b[1]) < epsilon) return true
	return false
}

function intersectLines(a1: Point, a2: Point, b1: Point, b2: Point) {
	const dbx = b2[0] - b1[0]
	const dby = b2[1] - b1[1]
	const dax = a2[0] - a1[0]
	const day = a2[1] - a1[1]

	const u_b = dby * dax - dbx * day
	if (u_b != 0) {
		const ua = (dbx * (a1[1] - b1[1]) - dby * (a1[0] - b1[0])) / u_b
		return [a1[0] - ua * -dax, a1[1] - ua * -day]
	}
}

function distance(a: Point, b: Point) {
	const dx = a[0] - b[0]
	const dy = a[1] - b[1]
	return dx * dx + dy * dy
}

function isOnSegment(xi: number, yi: number, xj: number, yj: number, xk: number, yk: number) {
	return (
		(xi <= xk || xj <= xk) &&
		(xk <= xi || xk <= xj) &&
		(yi <= yk || yj <= yk) &&
		(yk <= yi || yk <= yj)
	)
}

function computeDirection(xi: number, yi: number, xj: number, yj: number, xk: number, yk: number) {
	const a = (xk - xi) * (yj - yi)
	const b = (xj - xi) * (yk - yi)
	return a < b ? -1 : a > b ? 1 : 0
}

function doLineSegmentsIntersect(
	x1: number,
	y1: number,
	x2: number,
	y2: number,
	x3: number,
	y3: number,
	x4: number,
	y4: number
) {
	const d1 = computeDirection(x3, y3, x4, y4, x1, y1)
	const d2 = computeDirection(x3, y3, x4, y4, x2, y2)
	const d3 = computeDirection(x1, y1, x2, y2, x3, y3)
	const d4 = computeDirection(x1, y1, x2, y2, x4, y4)
	return (
		(((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) && ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) ||
		(d1 == 0 && isOnSegment(x3, y3, x4, y4, x1, y1)) ||
		(d2 == 0 && isOnSegment(x3, y3, x4, y4, x2, y2)) ||
		(d3 == 0 && isOnSegment(x1, y1, x2, y2, x3, y3)) ||
		(d4 == 0 && isOnSegment(x1, y1, x2, y2, x4, y4))
	)
}

function sortPoints(position: Point, segments: Segment[]) {
	const points = new Array(segments.length * 2)
	for (let i = 0; i < segments.length; ++i) {
		for (let j = 0; j < 2; ++j) {
			const a = angle(segments[i][j], position)
			points[2 * i + j] = [i, j, a]
		}
	}
	points.sort(function (a, b) {
		return a[2] - b[2]
	})
	return points
}

function lessThan(
	index1: number,
	index2: number,
	position: Point,
	segments: Segment[],
	destination: Point
) {
	const inter1 = intersectLines(segments[index1][0], segments[index1][1], position, destination)
	const inter2 = intersectLines(segments[index2][0], segments[index2][1], position, destination)
	if (!inter1 || !inter2) {
		return true
	} else {
		if (!equal(inter1, inter2)) {
			const d1 = distance(inter1, position)
			const d2 = distance(inter2, position)
			return d1 < d2
		}
		let end1 = 0
		let end2 = 0
		if (equal(inter1, segments[index1][0])) end1 = 1
		if (equal(inter2, segments[index2][0])) end2 = 1
		const a1 = angle2(segments[index1][end1], inter1, position)
		const a2 = angle2(segments[index2][end2], inter2, position)
		if (a1 < 180) {
			if (a2 > 180) return true
			return a2 < a1
		}
		return a1 < a2
	}
}

function parent(index: number) {
	return Math.floor((index - 1) / 2)
}

function child(index: number) {
	return 2 * index + 1
}

function insert(
	index: number,
	heap: any,
	position: Point,
	segments: Segment[],
	destination: Point,
	map: any
) {
	const intersect = intersectLines(segments[index][0], segments[index][1], position, destination)
	if (!intersect) return

	let cur = heap.length
	heap.push(index)
	map[index] = cur

	while (cur > 0) {
		const par = parent(cur)
		if (!lessThan(heap[cur], heap[par], position, segments, destination)) {
			break
		}
		map[heap[par]] = cur
		map[heap[cur]] = par
		const temp = heap[cur]
		heap[cur] = heap[par]
		heap[par] = temp
		cur = par
	}
}

function remove(
	index: number,
	heap: any,
	position: Point,
	segments: Segment[],
	destination: Point,
	map: any
) {
	map[heap[index]] = -1
	if (index == heap.length - 1) {
		heap.pop()
		return
	}
	heap[index] = heap.pop()
	map[heap[index]] = index
	let cur = index
	const par = parent(cur)
	if (cur != 0 && lessThan(heap[cur], heap[par], position, segments, destination)) {
		while (cur > 0) {
			const par = parent(cur)
			if (!lessThan(heap[cur], heap[par], position, segments, destination)) {
				break
			}
			map[heap[par]] = cur
			map[heap[cur]] = par
			const temp = heap[cur]
			heap[cur] = heap[par]
			heap[par] = temp
			cur = par
		}
	} else {
		// eslint-disable-next-line no-constant-condition
		while (true) {
			const left = child(cur)
			const right = left + 1
			if (
				left < heap.length &&
				lessThan(heap[left], heap[cur], position, segments, destination) &&
				(right == heap.length || lessThan(heap[left], heap[right], position, segments, destination))
			) {
				map[heap[left]] = cur
				map[heap[cur]] = left
				const temp = heap[left]
				heap[left] = heap[cur]
				heap[cur] = temp
				cur = left
			} else if (
				right < heap.length &&
				lessThan(heap[right], heap[cur], position, segments, destination)
			) {
				map[heap[right]] = cur
				map[heap[cur]] = right
				const temp = heap[right]
				heap[right] = heap[cur]
				heap[cur] = temp
				cur = right
			} else break
		}
	}
}

function compute(position: Point, segments: Segment[]) {
	const bounded: Segment[] = []
	let minX = position[0]
	let minY = position[1]
	let maxX = position[0]
	let maxY = position[1]
	for (let i = 0; i < segments.length; ++i) {
		for (let j = 0; j < 2; ++j) {
			minX = Math.min(minX, segments[i][j][0])
			minY = Math.min(minY, segments[i][j][1])
			maxX = Math.max(maxX, segments[i][j][0])
			maxY = Math.max(maxY, segments[i][j][1])
		}
		bounded.push([
			[segments[i][0][0], segments[i][0][1]],
			[segments[i][1][0], segments[i][1][1]],
		])
	}
	--minX
	--minY
	++maxX
	++maxY
	bounded.push([
		[minX, minY],
		[maxX, minY],
	])
	bounded.push([
		[maxX, minY],
		[maxX, maxY],
	])
	bounded.push([
		[maxX, maxY],
		[minX, maxY],
	])
	bounded.push([
		[minX, maxY],
		[minX, minY],
	])

	const polygon: number[][] = []

	const sorted = sortPoints(position, bounded)

	const map = new Array(bounded.length).fill(-1)

	const heap: number[] = []

	const start: Point = [position[0] + 1, position[1]]

	for (let i = 0; i < bounded.length; ++i) {
		const a1 = angle(bounded[i][0], position)
		const a2 = angle(bounded[i][1], position)
		let active = false
		if (a1 > -180 && a1 <= 0 && a2 <= 180 && a2 >= 0 && a2 - a1 > 180) active = true
		if (a2 > -180 && a2 <= 0 && a1 <= 180 && a1 >= 0 && a1 - a2 > 180) active = true
		if (active) {
			insert(i, heap, position, bounded, start, map)
		}
	}

	for (let i = 0; i < sorted.length; ) {
		let extend = false
		let shorten = false
		const orig = i
		let vertex = bounded[sorted[i][0]][sorted[i][1]]
		const old_segment = heap[0]
		do {
			if (map[sorted[i][0]] != -1) {
				if (sorted[i][0] == old_segment) {
					extend = true
					vertex = bounded[sorted[i][0]][sorted[i][1]]
				}
				remove(map[sorted[i][0]], heap, position, bounded, vertex, map)
			} else {
				insert(sorted[i][0], heap, position, bounded, vertex, map)
				if (heap[0] != old_segment) {
					shorten = true
				}
			}
			++i
			if (i == sorted.length) break
		} while (sorted[i][2] < sorted[orig][2] + epsilon)

		if (extend) {
			polygon.push(vertex)
			const cur = intersectLines(bounded[heap[0]][0], bounded[heap[0]][1], position, vertex)
			if (cur && !equal(cur, vertex)) {
				polygon.push(cur)
			}
		} else if (shorten) {
			const i1 = intersectLines(bounded[old_segment][0], bounded[old_segment][1], position, vertex)
			if (i1) {
				polygon.push(i1)
			}
			const i2 = intersectLines(bounded[heap[0]][0], bounded[heap[0]][1], position, vertex)
			if (i2) {
				polygon.push(i2)
			}
		}
	}
	return polygon
}

export function inViewport(position: Point, viewportMinCorner: Point, viewportMaxCorner: Point) {
	if (position[0] < viewportMinCorner[0] - epsilon) return false
	if (position[1] < viewportMinCorner[1] - epsilon) return false
	if (position[0] > viewportMaxCorner[0] + epsilon) return false
	if (position[1] > viewportMaxCorner[1] + epsilon) return false
	return true
}

export function inPolygon(position: Point, polygon: Point[]) {
	let val = polygon[0][0]

	for (let i = 0; i < polygon.length; ++i) {
		val = Math.min(polygon[i][0], val)
		val = Math.min(polygon[i][1], val)
	}
	const edge: Point = [val - 1, val - 1]
	let parity = 0

	for (let i = 0; i < polygon.length; ++i) {
		let j = i + 1
		if (j == polygon.length) j = 0
		if (
			doLineSegmentsIntersect(
				edge[0],
				edge[1],
				position[0],
				position[1],
				polygon[i][0],
				polygon[i][1],
				polygon[j][0],
				polygon[j][1]
			)
		) {
			const intersect = intersectLines(edge, position, polygon[i], polygon[j])
			if (!intersect) {
				++parity
			} else {
				if (equal(position, intersect)) return true
				if (equal(intersect, polygon[i])) {
					if (angle2(position, edge, polygon[j]) < 180) ++parity
				} else if (equal(intersect, polygon[j])) {
					if (angle2(position, edge, polygon[i]) < 180) ++parity
				} else {
					++parity
				}
			}
		}
	}
	return parity % 2 != 0
}

function convertToSegments(polygons: Segment[]) {
	const segments: Segment[] = []
	for (let i = 0; i < polygons.length; ++i) {
		for (let j = 0; j < polygons[i].length; ++j) {
			let k = j + 1
			if (k == polygons[i].length) k = 0
			segments.push([
				[polygons[i][j][0], polygons[i][j][1]],
				[polygons[i][k][0], polygons[i][k][1]],
			])
		}
	}
	return segments
}

function breakIntersections(segments: Segment[]) {
	const output = []
	for (let i = 0; i < segments.length; ++i) {
		const intersections = []
		for (let j = 0; j < segments.length; ++j) {
			if (i == j) continue
			if (
				doLineSegmentsIntersect(
					segments[i][0][0],
					segments[i][0][1],
					segments[i][1][0],
					segments[i][1][1],
					segments[j][0][0],
					segments[j][0][1],
					segments[j][1][0],
					segments[j][1][1]
				)
			) {
				const intersect = intersectLines(
					segments[i][0],
					segments[i][1],
					segments[j][0],
					segments[j][1]
				)
				if (!intersect) continue
				if (equal(intersect, segments[i][0]) || equal(intersect, segments[i][1])) continue
				intersections.push(intersect)
			}
		}
		const start: Point = [segments[i][0][0], segments[i][0][1]]
		while (intersections.length > 0) {
			let endIndex = 0
			let endDis = distance(start, intersections[0])
			for (let j = 1; j < intersections.length; ++j) {
				const dis = distance(start, intersections[j])
				if (dis < endDis) {
					endDis = dis
					endIndex = j
				}
			}
			output.push([
				[start[0], start[1]],
				[intersections[endIndex][0], intersections[endIndex][1]],
			])
			start[0] = intersections[endIndex][0]
			start[1] = intersections[endIndex][1]
			intersections.splice(endIndex, 1)
		}
		output.push([start, [segments[i][1][0], segments[i][1][1]]])
	}
	return output
}