假设我们有少量物体和它们之间的“距离” - 是否存在一种算法，可以将这些物体适当地贴合到二维空间中的点上，以近似这些距离？
这里的困难在于，“距离”不是欧几里得空间中的距离 - 这就是为什么我们只能进行贴合/近似。
（对于那些对距离概念感兴趣的人，它是一个（有限）集合的幂集上的对称距离度量）。
在2D中适配抽象距离的算法
10
- popstack
5
你是否有每对可能点的距离？ - corsiKa
有没有一种函数可以让你更接近地将当前距离映射到代表欧几里得距离的距离？如果这是情况，那些将差异视为简单错误的解决方案将无法产生良好的结果。如果你的非欧几里得距离在应用某些其他函数后更好地映射到欧几里得空间中的表示形式，那么在尝试绘制你的值之前应用这个函数是有意义的。 - SmacL
想象一下你有n个点，任意两点之间的距离都是1。这显然是一个度量空间。你需要一个n-1维空间来等距地嵌入这些点。你希望将这种情况映射到二维平面上吗？ - Alexandre C.
@glowcoder：是的，我有每对点之间的距离。Shane MacLaughlin：由于点数N较少，我可以准确地将它们映射到(N-1)维空间中。这会给亚历山大C.带来困难的情况 - 是否有能够很好处理这种情况的算法？ - popstack
我相信有算法可以将n维点投影到n-1维。因此，你可以在n-1维度中完美地解决你的系统，执行一些计算以确定将图像投影到n-2维空间的“最充分”角度，并重复此过程直到进入2D空间。 - corsiKa
3个回答
1
考虑到对象数量较少，您可以创建一个无向加权图，其中这些对象将成为节点，任何两个节点之间的边缘的权重对应于这两个对象之间的距离。最终会得到n*(n-1)/2 条边。
一旦图形被创建，就有很多可视化软件和与图形相对应的算法。
- Max Li
0
尝试使用三角测量方法，类似于以下步骤：
首先选取三个已知距离的物体，在任意网格上根据边长创建一个三角形。
对于每个未放置的物体，找到至少三个已放置的物体，这些物体与该物体之间的距离是已知的，使用距离/距离交点（即以固定点为圆心、半径为距离的三个圆的交点）来放置该物体。
重复以上步骤，直到所有物体都被放置或无法再放置为止。
对于未放置的物体，您可以开始另一个类似的练习，然后使用任何可用的距离来关联不同的聚类。查阅三角测量和三边测量网络以获取更多信息。
编辑： 根据下面的评论，在距离大概且包含误差元素的情况下，可以使用上述方法为每个对象建立初步坐标，然后使用最小二乘法（例如坐标变化）调整这些坐标。这也将根据需要加权距离大小。有关更详细的描述，请查看Ghilani & Wolf的相关书籍。 这非常取决于您的距离之间的差异的性质以及您希望基于这些距离在欧几里得空间中表示对象的方式。该关系需要作为任何解决方案的一部分进行建模和应用。
- SmacL
5
如果有四个物体与给定物体的距离已知，但这些距离不一致，该怎么办？ - ElKamina
@ElKamina，如果是这种情况，请使用上述程序生成临时坐标，然后进行最小二乘调整，例如坐标变化以执行最佳拟合。 - SmacL
有趣！但是如果要放置的第四个对象靠近已经放置的三个对象，而这三个对象本身相距很远，我不确定该怎么做。在这种情况下，它们的圆将不会相交。 - popstack
它取决于每个物体之间有多少距离。为了使上述方法有效，确实需要每个物体到任何其他物体的距离至少为三个。如果从任何给定物体只有两个距离，它可以合理地位于连接这两个有距离物体的线的任一侧。如果只有一个距离，则它可以位于由该距离定义的圆上的任何位置。如果某个对象没有距离，则可以将其放置在平面的任何位置。Cont... - SmacL
如果第四个物体与已经放置在平面上的任何物体之间没有三个距离，你需要跳过它并尝试其他物体，直到你能够放置一个物体或者没有更多可放置的物体为止。你重复这个过程，直到无法再放置任何物体。 - SmacL
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接