如何将标记转换为具有最小线交叉点的半圆？
How to translate markers into a half circle with minimal line intersection?
我有一张地图，上面显示了很多标记。有时标记彼此非常接近以至于它们重叠。为了解决这个问题，我实现了一个 spiderfier 库来解决这个问题。
我们的想法是将屏幕上足够靠近的标记分组（在数学上向下），这样它们就不会相互交叉。
标记显示为矩形。
实施：
- 遍历marker和相交的marker，归为一组，中心为((minX + maxX) / 2, maxY)，半径刚好足够显示周边的marker不相交
- 虽然有相互交叉的半圆，但我们将它们合并成一个更大的半圆
- 我们通过比较器对标记进行排序，将 "smaller" 标记与其 "greater" 对应物
相比放置在圆圈的左侧
- 我们在上半圈显示标记，但我们显示一条从修改后的位置到实际位置的线
到目前为止，还不错。
问题：这些线彼此相交的频率太高，我们需要一个比较器函数来最小化标记线相交的数量。
尝试次数：
P1.x <= P2.x => P1 <= P2
arctan((P1.y - C.y) / (R * (P1.x - C.x))) <= arctan((P2.y - C.y) / (R * (P2.x - C.x))) => P1 <= P2
我对第二次尝试寄予厚望，但不得不承认这不是一个好主意，因为平移线和实际位置与圆心之间的线不一定共线，在实际上，如果有许多标记的真实位置彼此非常接近，则它们的角度会变得相当大，而半圆的表面除了这个子区域之外是相当贫瘠的。因此，这也会导致交叉点，并且比第一次尝试复杂得多。我相信Javascript的Math.atan is implemented either with Taylor series or Fourier series，它在第一种情况下涉及导数，在第二种情况下涉及积分。或者，可能还有第三种方法，它也非常复杂。如果第二种方法可以显着减少交叉点的数量，我会考虑优化和类似的东西，但由于这种改进几乎看不到，所以我回到了第一种方法。
我正在考虑以下方法：
- 计算外围标记槽的位置
- 尝试将所有标记平移到最接近的位置
- 找到冲突组并通过找到最优解来解决所有冲突，即总翻译量最小的翻译集
这个想法是否会导致蜘蛛线交叉点数量最小化的状态，如果不是，我如何才能最小化此类交叉点的数量？
这是一道难题，研究了很久。
它有时被称为
automatic label placement。
下面引用的工作是文献中可用的典型工作。
Van Kreveld, Marc, Tycho Strijk, and Alexander Wolff. "Point set labeling with sliding labels." Proceedings of the fourteenth annual symposium on Computational geometry. ACM, 1998. ACM link.
我有一张地图，上面显示了很多标记。有时标记彼此非常接近以至于它们重叠。为了解决这个问题，我实现了一个 spiderfier 库来解决这个问题。
我们的想法是将屏幕上足够靠近的标记分组（在数学上向下），这样它们就不会相互交叉。
标记显示为矩形。
实施：
- 遍历marker和相交的marker，归为一组，中心为((minX + maxX) / 2, maxY)，半径刚好足够显示周边的marker不相交
- 虽然有相互交叉的半圆，但我们将它们合并成一个更大的半圆
- 我们通过比较器对标记进行排序，将 "smaller" 标记与其 "greater" 对应物 相比放置在圆圈的左侧
- 我们在上半圈显示标记，但我们显示一条从修改后的位置到实际位置的线
到目前为止，还不错。
问题：这些线彼此相交的频率太高，我们需要一个比较器函数来最小化标记线相交的数量。
尝试次数：
P1.x <= P2.x => P1 <= P2
arctan((P1.y - C.y) / (R * (P1.x - C.x))) <= arctan((P2.y - C.y) / (R * (P2.x - C.x))) => P1 <= P2
我对第二次尝试寄予厚望，但不得不承认这不是一个好主意，因为平移线和实际位置与圆心之间的线不一定共线，在实际上，如果有许多标记的真实位置彼此非常接近，则它们的角度会变得相当大，而半圆的表面除了这个子区域之外是相当贫瘠的。因此，这也会导致交叉点，并且比第一次尝试复杂得多。我相信Javascript的Math.atan is implemented either with Taylor series or Fourier series，它在第一种情况下涉及导数，在第二种情况下涉及积分。或者，可能还有第三种方法，它也非常复杂。如果第二种方法可以显着减少交叉点的数量，我会考虑优化和类似的东西，但由于这种改进几乎看不到，所以我回到了第一种方法。
我正在考虑以下方法：
- 计算外围标记槽的位置
- 尝试将所有标记平移到最接近的位置
- 找到冲突组并通过找到最优解来解决所有冲突，即总翻译量最小的翻译集
这个想法是否会导致蜘蛛线交叉点数量最小化的状态，如果不是，我如何才能最小化此类交叉点的数量？
这是一道难题，研究了很久。 它有时被称为 automatic label placement。 下面引用的工作是文献中可用的典型工作。
Van Kreveld, Marc, Tycho Strijk, and Alexander Wolff. "Point set labeling with sliding labels." Proceedings of the fourteenth annual symposium on Computational geometry. ACM, 1998. ACM link.