将二维点映射到固定网格
Mapping 2D points to a fixed grid
我在一个假想的二维表面上有任意数量的点。我在同一个表面上还有一个网格，沿 X 和 Y 通道以固定间隔放置点。我的任务是将每个点映射到最近的网格点。
在缺少网格点之前，代码足够直接。我一直在开发的代码找到最近的网格点，如果当前点的距离更短，则显示已经映射的点。
然后我添加了第二个步骤，将每个映射点与另一个点进行比较，如果将映射与另一个点交换产生两个点的总映射距离之和较小，我将它们交换。
这最后一步似乎很重要，因为它减少了交叉地图线的数量。 （这将用于将一个板上的点映射到另一个板上的网格，用引脚连接两者，不交叉的线似乎更有可能使引脚不接触。）
问题：
任何人都可以评论我的想法，如果上面的图像是真正优化的，（也就是说，映射点——整体——总距离最小），那么none 的线是交叉的?
有没有人见过任何现有的算法来帮助解决这个问题。我已经搜索过了，但一无所获。
如果我正确理解您的主要关注点，最小化线段的总长度，则您使用的算法未找到最佳映射并且在您的图像中很清楚。例如当两条线段相互交叉时，简单的数学表明，如果您重新排列它们的端点以使它们不交叉，它会提供更好的总和。您可以使用这种简单的方法（重新排列交叉项）来更好地逼近最优值，您应该以某种方式应用交换进行更多次迭代。
在下面的图片中你可以看到为什么交叉比非交叉的长度更长（第一个问题）以及为什么交换一次仍然存在交叉边缘（第二个问题和w.r.t。评论），我只是画了一个样本，实际上可能需要多次交换迭代才能得到不交叉的结果。
这是一种启发式算法，当然不是最优的，但我希望它非常好、高效且易于实现。
这个问题可以作为 Assignment Problem, with the "agents" being the grid squares and the points being the "tasks", (or vice versa) with the distance between them being the "cost" for that agent-task combination. You could solve with the Hungarian algorithm.
的变体来解决
要处理网格方块多于点的事实，请为您要考虑的可能网格方块找到一个边界框，并添加与所有网格方块关联的成本为 0 的虚拟点。
匈牙利算法是O(n3)，也许你的方法已经够好了。
另请参阅：
How to find the optimal mapping between two sets?
How to optimize assignment of tasks to agents with these constraints?
我在一个假想的二维表面上有任意数量的点。我在同一个表面上还有一个网格，沿 X 和 Y 通道以固定间隔放置点。我的任务是将每个点映射到最近的网格点。
在缺少网格点之前，代码足够直接。我一直在开发的代码找到最近的网格点，如果当前点的距离更短，则显示已经映射的点。
然后我添加了第二个步骤，将每个映射点与另一个点进行比较，如果将映射与另一个点交换产生两个点的总映射距离之和较小，我将它们交换。
这最后一步似乎很重要，因为它减少了交叉地图线的数量。 （这将用于将一个板上的点映射到另一个板上的网格，用引脚连接两者，不交叉的线似乎更有可能使引脚不接触。）
问题：
任何人都可以评论我的想法，如果上面的图像是真正优化的，（也就是说，映射点——整体——总距离最小），那么none 的线是交叉的?
有没有人见过任何现有的算法来帮助解决这个问题。我已经搜索过了，但一无所获。
如果我正确理解您的主要关注点，最小化线段的总长度，则您使用的算法未找到最佳映射并且在您的图像中很清楚。例如当两条线段相互交叉时，简单的数学表明，如果您重新排列它们的端点以使它们不交叉，它会提供更好的总和。您可以使用这种简单的方法（重新排列交叉项）来更好地逼近最优值，您应该以某种方式应用交换进行更多次迭代。
在下面的图片中你可以看到为什么交叉比非交叉的长度更长（第一个问题）以及为什么交换一次仍然存在交叉边缘（第二个问题和w.r.t。评论），我只是画了一个样本，实际上可能需要多次交换迭代才能得到不交叉的结果。
这是一种启发式算法，当然不是最优的，但我希望它非常好、高效且易于实现。
这个问题可以作为 Assignment Problem, with the "agents" being the grid squares and the points being the "tasks", (or vice versa) with the distance between them being the "cost" for that agent-task combination. You could solve with the Hungarian algorithm.
的变体来解决要处理网格方块多于点的事实，请为您要考虑的可能网格方块找到一个边界框，并添加与所有网格方块关联的成本为 0 的虚拟点。
匈牙利算法是O(n3)，也许你的方法已经够好了。
另请参阅：
How to find the optimal mapping between two sets?
How to optimize assignment of tasks to agents with these constraints?