plot - nvd3 散点图 : labels on bullets

Question

我有一个要求，散点图的特定实现上的项目符号需要在它们旁边有标签，但是，众所周知，集合中的许多数据点彼此相同或非常接近，所以如果我要设置相对于子弹的固定坐标上的标签，标签将堆叠在彼此的顶部并且不可读。

我想实现这一点，以便标签将为彼此让路 - 四处移动，因此它们不会重叠 - 我认为这是一个足够普遍的想法，某些方法已经存在，但我不知道要搜索什么为了。这个概念有名字吗？

我当然会欣赏一个实现示例，但这不是最重要的事情。我相信我自己可以解决它，但我宁愿不重新发明别人已经做得更好的东西。



上图显示了子弹在顶部并彼此靠近的示例

Answer 1

我最终在 Simulated Annealing 中找到了灵感.

我的解决方案看起来像这样

/**
 * Implements an algorithm for placing labels on a chart in a way so that they
 * do not overlap as much.
 * The approach is inspired by Simulated Annealing
 * (https://en.wikipedia.org/wiki/Simulated_annealing)
 */
export class Placer {
    private knownPositions: Coordinate[];
    private START_RADIUS = 20;
    private RUNS = 15;
    private ORIGIN_WEIGHT = 2;

    constructor() {
        this.knownPositions = []
    }

    /**
     * Get a good spot to place the object.
     *
     * Given a start coordinate, this method tries to find the best place
     * that is close to that point but not too close to other known points.
     *
     * @param {Coordinate} coordinate
     * @returns {Coordinate}
     */
    getPlacement(coordinate: Coordinate) : Coordinate {
        let radius = this.START_RADIUS;
        let lastPosition = coordinate;
        let lastScore = 0;
        while (radius > 0) {
            const newPosition = this.getRandomPosition(coordinate, radius);
            const newScore = this.getScore(newPosition, coordinate);
            if (newScore > lastScore) {
                lastPosition = newPosition;
                lastScore = newScore;
            }
            radius -= this.START_RADIUS / this.RUNS;
        }
        this.knownPositions.push(lastPosition);
        return lastPosition;
    }

    /**
     * Return a random point on the radius around the position
     *
     * @param {Coordinate} position Center point
     * @param {number} radius Distance from `position` to find a point
     * @returns {Coordinate} A random point `radius` distance away from
     *     `position`
     */
    private getRandomPosition(position: Coordinate, radius:number) : Coordinate {
        const randomRotation = radians(Math.random() * 360);
        const xOffset = Math.cos(randomRotation) * radius;
        const yOffset = Math.sin(randomRotation) * radius;
        return {
            x: position.x + xOffset,
            y: position.y + yOffset,
        }
    }

    /**
     * Returns a number score of a position. The further away it is from any
     * other known point, the better the score (bigger number), however, it
     * suffers a subtraction in score the further away it gets from its origin
     * point.
     *
     * @param {Coordinate} position The position to score
     * @param {Coordinate} origin The initial position before looking for
     *     better ones
     * @returns {number} The representation of the score
     */
    private getScore(position: Coordinate, origin: Coordinate) : number {
        let closest: number = null;
        this.knownPositions.forEach((knownPosition) => {
            const distance = Math.abs(Math.sqrt(
                Math.pow(knownPosition.x - position.x, 2) +
                Math.pow(knownPosition.y - position.y, 2)
            ));
            if (closest === null || distance < closest) {
                closest = distance;
            }
        });
        const distancetoOrigin = Math.abs(Math.sqrt(
            Math.pow(origin.x - position.x, 2) +
            Math.pow(origin.y - position.y, 2)
        ));
        return closest - (distancetoOrigin / this.ORIGIN_WEIGHT);
    }
}

getScore还有改进的空间方法，但结果对我来说已经足够了。

基本上，所有点都尝试移动到给定半径内的随机位置，并查看该位置是否比原始位置“更好”。该算法不断地对越来越小的半径执行此操作，直到半径 = 0。

该类会跟踪所有已知点，因此当您尝试放置第二点时，评分可以说明第一点的存在。