Makie：散点图的非重叠标签放置算法

我使用 CairoMakie 散点图 XY 数据集，但使用标签作为标记：

using CairoMakie


x = [0, 0.5, 0.50]
y = [0, 0.5, 0.51]
lbls = ["O", "A", "B"]

fig = Figure()
ax = Axis(fig[1,1])
scatter!(ax, x, y, marker=:circle, markersize=10, color=:red)
foreach(i -> text!(ax, position=(x[i], y[i]), lbls[i]), 1:3)

display(fig)

这会产生下图：

因为积分A and B彼此非常接近，各自的标签重叠。 CairoMakie 是否有一种算法来放置标签以避免标签重叠？

我知道 Gadfly 有这个能力Geom.label但我希望我不必使用单独的包来绘制此类图表。我也知道在 CairoMakie，我可以使用诸如position and offset以标签不重叠的方式调整标签位置，但我无法对我的情况下的每个数据集执行此操作。

有人可以帮忙吗？或者也许有一个用 Julia 编写的标签放置算法？谢谢。

令人惊讶的是，已经写了几篇关于非重叠标签放置算法的数学论文，但我既没有数学背景，也没有时间研究这些论文，更不用说将算法翻译成代码了。 Python 和 R 都有此类算法的代码。

不管怎样，下面的 Julia 代码对于我的情况来说已经足够了，但对于所有情况和每个人的情况来说不一定足够全面。

using DataFrames
using CairoMakie
using Random


function allpairs(n::Int)
    arr = collect(Iterators.product(1:n, 1:n))
    row, col = size(arr)
    combo = []
    for r ∈ 1:row-1, c ∈ (r + 1):col
        push!(combo, arr[r, c])
    end
    combo
end


angle(x, y) = atan(y[2] - y[1], x[2] - x[1])


dist(x, y) = sqrt((x[2] - x[1])^2 + (y[2] - y[1])^2)


function label_dist(x, y, δw, δh)
    x1, x2 = x[1], x[2]
    y1, y2 = y[1], y[2]
    x1b, x2b = x1 + δw, x2 + δw
    y1b, y2b = y1 + δh, y2 + δh

    left = x2b < x1
    right = x1b < x2
    bottom = y2b < y1
    top = y1b < y2

    d = top && left ? dist((x1, x2b), (y1b, y2)) :
        left && bottom ? dist((x1, x2b), (y1, y2b)) :
        bottom && right ? dist((x1b, x2), (y1, y2b)) :
        right && top ? dist((x1b, x2), (y1b, y2)) :
        left ? x1 - x2b :
        right ? x2 - x1b :
        bottom ? y1 - y2b :
        top ? y2 - y1b :
        0.0
    d
end


function shift!(x, y, idx, r, angle)
    x[idx[1]] -= r * cos(angle)
    y[idx[1]] -= r * sin(angle)
    x[idx[2]] += r * cos(angle)
    y[idx[2]] += r * sin(angle)
end


function label_pos(x, y;               # label positions (original/untransformed scale)
                   min_dist=0.002,     # min. distance between labels (on a 0-1 scale)
                   shift_size=0.002,   # distance to shift labels (on a 0-1 scale)
                   width=0.05,         # width of label (on a 0-1 scale)
                   height=0.03,        # height of label (on a 0-1 scale)
                   attempts::Int=100)  # no. of tries to place labels
    xlims = extrema(x)
    Δx = xlims[2] - xlims[1]
    ylims = extrema(y)
    Δy = ylims[2] - ylims[1]

    xt = (x .- xlims[1]) ./ Δx  # map to a 0-1 scale
    yt = (y .- ylims[1]) ./ Δy

    combo = allpairs(length(xt))
    iter = true
    i = 1
    while iter
        pts = map(combo) do p
            idx = [p[1], p[2]]
            d = label_dist(xt[idx], yt[idx], width, height)
            θ = angle(xt[idx], yt[idx])
            (idx=idx, dist=d, angle=θ)
        end

        pos = findall(p -> p.dist < min_dist, pts)
        foreach(p -> shift!(xt, yt, p.idx, shift_size, p.angle), pts[pos])
        i += 1
        iter = (i <= attempts) && !isempty(pos)
    end

    xt = xt .* Δx .+ xlims[1]   # revert to original scale
    yt = yt .* Δy .+ ylims[1]

    (; x=xt, y=yt)
end


xlims = (0, 1)
ylims = (-10, 10)

Δxl = xlims[2] - xlims[1]
Δyl = ylims[2] - ylims[1]

n = 150      # no. of points to generate
seed = 392348
Random.seed!(seed)
xs = xlims[1] .+ rand(n) .* Δxl
ys = ylims[1] .+ rand(n) .* Δyl

labels = map(i -> "$i", eachindex(xs))

xt = xs[:]
yt = ys[:]
xt2 = xs[:]
yt2 = ys[:]

xt, yt = label_pos(xt, yt)

xlims2 = (xlims[1] - Δxl * 0.05, xlims[2] + Δxl * 0.05)
ylims2 = (ylims[1] - Δyl * 0.05, ylims[2] + Δyl * 0.05)

fig = Figure(resolution=(600,1200))  # must be square and preferably >500 px
axs = Axis(fig[1,1])
scatter!(axs, xs, ys, marker=:circle, markersize=5, color=:red)
axs.title = "non-overlap label placement"

foreach(eachindex(labels)) do i
    text!(axs, position=(xt[i], yt[i]), labels[i], textsize=15, align=(:right, :bottom))
end

axs2 = Axis(fig[2,1])
scatter!(axs2, xs, ys, marker=:circle, markersize=5, color=:red)
axs2.title = "default label placement"

limits!(axs, xlims2, ylims2)
limits!(axs2, xlims2, ylims2)

foreach(eachindex(labels)) do i
    text!(axs2, position=(xt2[i], yt2[i]), labels[i], textsize=15, align=(:right, :bottom))
end

display(fig)

该代码生成以下 2 个图表：

它远非近乎完美或优化，但它足够充分地梳理标签，以便我可以将图形保存为 SVG，然后使用矢量绘图应用程序在需要时手动调整标签。

这是一个开始，因为我相信聪明的人可以优化这段代码。我希望这对其他人有帮助。