我试图从图形xy图中提取语义,其中绘制点并且一些或全部都有标签.标签被绘制成"靠近点",这样人类通常可以理解哪个标签与哪个点相关.例如,在该图中,清楚哪个标签(数字)属于哪个点(*),并且基于欧几里德距离的算法将起作用.(标签和点没有语义排序 - 例如散点图)
*1
*2
*3
*4
在拥挤的图中,创作软件/人可以将标签放置在不同的方向上以避免重叠.例如在
1**2
**4
3
人类读者通常可以确定哪个标签与哪个标签相关联.
我接受的一个解决方案是创建欧几里德距离矩阵并对行进行混洗以获得函数的最小值(例如,对角线或其他启发式上的距离的总和平方).在第二个例子中(从NW角顺时针标记为a,b,c,d的点),我们有一个距离矩阵(到1 dp)
a b c d
1ab2 1 1.0 2.0 2.2 1.4
dc4 2 2.0 1.0 1.4 2.2
3 3 2.0 2.2 1.4 1.0
4 2.2 1.4 1.0 2.0
我们需要贴上标签a1 b2 c4 d3.交换行3和4给出了对角线的最小总和.这是一个更复杂的例子,简单地选择最近的可能会失败
*1*2*5
**4
3 *6
如果这个问题得到解决,那么我需要去看标签数量可能小于或大于点数的情况.
如果算法是标准的,那么我会欣赏指向开源Java的指针(例如JAMA或Apache数学)
注意:这个SO答案将附近的点与路径相关联并不能作为答案,因为给出了通过点的路径.