What I have
I have a mapbox map, where a add some Feature points, with a text label showing the name of the location.
I'm trying to add collision detection/avoidance to this so that no labels are colliding. I actually have this working (see picture below), but I wan't to improve it further.
Currently I'm doing a collision detection using a D3 quadtree, and if two bounding boxes are overlapping (let's call them A and B), I first check if the have the biggest overlap in the X or the Y direction, and then move them apart from each other in the shortest overlapping direction.
What I need help with
If you look at the map, you can see that some labels are moved quite far away from the corresponding icon (green dot, fixed at original location). For instance the highlighted label "Dublin". How can I improve the algorithm so it also takes into account the distance to the icon position? "Dublin" could be much closer to the icon on the left side.
What am I looking for?
I don't necessarily need full code of the solution, just some pointers. I've spent too much time thinking about this, so I need some new input.
Implementation
D3.js simulation is just defined like this:
getSimulation() {
return (
d3
/** Setup a physics based simulation */
.forceSimulation<Node>()
.force('collision', this.forceCollide())
.stop()
)
}
The collision detection is defined like this:
/** Collision detection with quadtree.
*
* Will compare node to other nodes, using a quadtree,
* and move them apart of the overlap. If biggest overlap
* is in x direction, move apart in y direction, or visa versa.
*/
forceCollide() {
let nodes: Array<Node>
function force(alpha: number) {
// for (var i = 0; i < 10; i++) {
const quadtree = d3
.quadtree<Node>()
.x(d => d.x)
.y(d => d.y)
.addAll(nodes)
for (const node of nodes) {
const l1 = node.x
const r1 = node.x + node.size[0]
const t1 = node.y
const b1 = node.y + node.size[1]
/**
* visit each squares in the quadtree x1 y1 x2 y2
* constitutes the coordinates of the square want
* to check if each square is a leaf node (has data prop)
*/
quadtree.visit((visited, x1, y1, x2, y2) => {
/** Is a leaf node, and is not checking against itself */
if (isLeafNode(visited) && visited.data.id !== node.id) {
const l2 = visited.data.x
const r2 = visited.data.x + visited.data.size[0]
const t2 = visited.data.y
const b2 = visited.data.y + node.size[1]
/** We have a collision */
if (l2 < r1 && l1 < r2 && t1 < b2 && t2 < b1) {
/** Calculate intersecting rectangle */
const xLeft = Math.max(l1, l2)
const yTop = Math.max(t1, t2)
const xRight = Math.min(r1, r2)
const yBottom = Math.min(b1, b2)
/** Move the rectangles apart, so that they don't overlap anymore. */
/* Find which direction has biggest overlap */
if (xRight - xLeft > yBottom - yTop) {
/** Biggest in x direction (move y) */
const dy = (yBottom - yTop) / 2
node.y -= dy
visited.data.y += dy
} else {
/** Biggest in y direction (move x) */
const dx = (xRight - xLeft) / 2
node.x -= dx
visited.data.x += dx
}
}
}
return x1 > r1 || x2 < l1 || y1 > b1 || y2 < t1
})
}
}
force.initialize = (_: any) => (nodes = _)
return force
}