最接近点对问题实现思路和流程图
最接近点对问题的实现思路:
- 首先将所有点按照横坐标排序;
- 然后将所有点分成两个部分,左半部分和右半部分,分别递归求解左半部分和右半部分的最接近点对;
- 求解左半部分和右半部分的最接近点对时,可以使用分治法求解;
- 然后求出左半部分和右半部分的最小距离,记为d;
- 接着,从中间线向左右扩展一个距离为d的区域,将所有在该区域内的点按照纵坐标排序;
- 在该区域内,对于每一个点,只需要考虑该点上下d个点,因为距离大于d的点已经在前面的步骤中处理掉了;
- 对于每个点,只需要计算它和它上下d个点的距离,然后选取距离最小的点对即可。
流程图:
1. 将所有点按照横坐标排序
2. 求解左半部分和右半部分的最接近点对
2.1. 如果点的个数小于等于3,则直接计算所有点的距离并返回最小值
2.2. 否则,分别递归求解左半部分和右半部分的最接近点对
2.3. 求解左半部分和右半部分的最小距离
3. 从中间线向左右扩展一个距离为d的区域,将所有在该区域内的点按照纵坐标排序
4. 在该区域内,对于每一个点,只需要考虑该点上下d个点
5. 对于每个点,计算它和它上下d个点的距离,选取距离最小的点对
6. 返回最小距离
原文地址: https://www.cveoy.top/t/topic/uD9 著作权归作者所有。请勿转载和采集!