stable collison detect use in mapbox symbol layer

collision.js

/**
 * 初始的 filter
 */

export function initialFilter({ map, list }) {
	list.forEach(item => setBox({ map, item }))

	let i = 0
	while (i < list.length) {
		let prev = list.slice(0, i)
		let cur = list[i]
		let rest = list.slice(i + 1)

		const curBox = cur.box
		rest = rest.filter(item => {
			return !intersect(cur.box, item.box)
		})
		list = [...prev, cur, ...rest]
		i++
	}

	return list
}

/**
 * zoom 变大, 数量变多
 */

export function filterMore({ map, fullList, curList }) {
	fullList.forEach(item => setBox({ map, item }))
	curList.forEach(item => setBox({ map, item }))

	// fullList --> 除去curList的list --> 除去和curList有交集的
	const curListIds = curList.map(x => x.id)
	let list = fullList.filter(x => !curListIds.includes(x.id))

	// 剩余部分自己去重
	list = initialFilter({ map, list })

	// 和 curList 不重叠
	list = list.filter(item => {
		for (let curitem of curList) {
			if (intersect(item.box, curitem.box)) {
				return false
			}
		}
		return true
	})

	return curList.concat(list)
}

/**
 * zoom 变小, 数量变少
 */
export function filterLess({ map, curList }) {
	return initialFilter({ map, list: curList })
}

/**
 * add item.box
 */

function setBox({ map, item }) {
	item.box = locToBox({ map, lnglat: item.camera_position })
}

/**
 * lnglat -> box
 */

function locToBox({ map, lnglat, r = 20 }) {
	const { x, y } = map.project(lnglat)
	return {
		left: x - r,
		right: x + r,
		top: y - r,
		bottom: y + r,
	}
}

/**
 * 判断两个 box 是否有交集
 */

function intersect(box1, box2) {
	const { left, right, top, bottom } = box1
	const xIntersects =
		(box2.left > left && box2.left < right) || (box2.right > left && box2.right < right)
	const yIntersects =
		(box2.top > top && box2.top < bottom) || (box2.bottom > top && box2.bottom < bottom)
	return xIntersects && yIntersects
}