最も近い点のペアを見つける - 再帰的なサイドペアの関数呼び出しの中でスプリットペアを実装する方法

Question

私はdivide and conquerアプローチを使用して最も近い点のペアを見つける方法を実装しようとしています。

まず、スプリットペア（p1、p2）は、p1が左側、右側がp2となるように最も近いペアです。サイドペア（p3、p4）は、p3とp4が一方の側にあるような最も近いペアです。

closest_split_pairs関数が別途呼び出された場合（関数closest_side_pairsではなく）、正しい結果を返す実装を行っています。私はこれらの点を提供あれば：

2,1 
8,3 
5,8 
9,1 
5,2 
3,3 
4,5 
6,5 
1,9 
2,1.5 

を私は2,1と2,1.5の結果を取得します。 （私はそれがそのようであるべきだと思う）

しかし、私はclosest_side_pairs内closest_split_pairを呼び出した場合..私は間違った結果3,3と4,5を取得します。問題は、closest_split_pairsをclosest_side_pairsの中に組み込むために何をしなければならないのか分かりません。コードclosest_split_pairsはclosest_side_pairsと呼ばれ、別の呼び出しはmain機能でコメントされています。

#include <iostream> 
#include <array> 
#include <algorithm> 
#include <fstream> 
#include <cfloat> 
#include <cmath> 

struct Point { 
    Point(double x = 0, double y = 0) { 
     x_coordinate = x; 
     y_coordinate = y; 
    } 
    double x_coordinate; 
    double y_coordinate; 
    static bool sortByX(const Point &lhs, const Point &rhs) { 
     return lhs.x_coordinate < rhs.x_coordinate; 
    } 
    static bool sortByY(const Point &lhs, const Point &rhs) { 
     return lhs.y_coordinate < rhs.y_coordinate; 
    } 
}; 

using p_iterator = std::vector<Point>::iterator; 

template<std::size_t SIZE> 
using p_iterators_array = std::array<std::vector<Point>::iterator, SIZE>; 

void initialize_points(std::vector<Point> &points) { 
    double x, y; 
    char c; 
    std::ifstream infile("./points.txt"); 
    while((infile >> x >> c >> y) && (c == ',')) { 
     points.push_back(Point(x, y)); 
    } 
} 

double calculate_distance(Point &p1, Point &p2) { 
    return std::sqrt(std::pow(p1.x_coordinate - p2.x_coordinate, 2) + std::pow(p1.y_coordinate - p2.y_coordinate , 2)); 
} 

template<typename T> 
p_iterators_array<2> eucledian_closest(T &points, int size) { 
    p_iterators_array<2> closest_arr; 
    double closest_distance = DBL_MAX, distance = 0.0; 

    for(int i = 0; i < size - 1; i++){ 
     for(int j = i + 1; j < size; j++) { 
     distance = calculate_distance(points[i], points[j]); 
     if(distance < closest_distance) { 
      closest_distance = distance; 
      closest_arr[0] = points + i; 
      closest_arr[1] = points + j; 
     } 
     } 
    } 
    return closest_arr; 
} 

p_iterators_array<2> closest_split_pair(p_iterator points_iterator, p_iterators_array<2> &closest_side_pairs, std::size_t size) { 
    std::vector<p_iterator> split_pairs; 
    p_iterators_array<2> final_result; 
    double closest_distance = DBL_MAX, distance = 0.0; 

    p_iterator midpoint = points_iterator + (size/2); 

    //filtering points to only points in sigma-2sigma rectangle 
    for (size_t i = 0; i < size; i++) { 
     if(std::abs(points_iterator[i].x_coordinate - midpoint->x_coordinate) < calculate_distance(*(closest_side_pairs[0]), *(closest_side_pairs[1]))){ 
      split_pairs.push_back(points_iterator + i); 
     } 
    } 

    //finding closest pair in split_pairs 
    for (size_t i = 0; i < split_pairs.size() - 1; i++) { 
     for (size_t j = i+1; (j < 7) && (j < split_pairs.size()) ; j++) { 
     distance = calculate_distance(*(split_pairs[i]), *(split_pairs[j])); 
     if(distance < closest_distance) { 
      closest_distance = distance; 
      final_result[0] = split_pairs[i]; 
      final_result[1] = split_pairs[j]; 
     } 
     } 
    } 

    //comparing split paris distance and side pairs distance 
    if(calculate_distance(*(closest_side_pairs.front()), *(closest_side_pairs.back())) < calculate_distance(*(final_result.front()), *(final_result.back()))) { 
     final_result = closest_side_pairs; 
    } 
    return final_result; 
} 

p_iterators_array<2> closest_side_pair(p_iterator points_iterator, p_iterator x_arr_iterator, p_iterator y_arr_iterator, std::size_t size) { 
    std::size_t delimeter = size/2 ; 
    if(delimeter <= 3) { 
     return eucledian_closest(points_iterator, delimeter); 
    } 
    p_iterators_array<2> closest_left, closest_right, result; 

    closest_left = closest_side_pair(points_iterator, x_arr_iterator, y_arr_iterator, delimeter); 
    closest_right = closest_side_pair(points_iterator + delimeter, x_arr_iterator + delimeter, y_arr_iterator + delimeter, delimeter); 

    if(calculate_distance(*(closest_left.front()), *(closest_left.back())) < calculate_distance(*(closest_right.front()), *(closest_right.back()))) { 
     result = closest_left; 
    } else { 
     result = closest_right; 
    } 
    return closest_split_pair(points_iterator, result, delimeter); 
} 

int main() 
{ 
    std::vector<Point> points; 
    initialize_points(points); 

    std::vector<Point> x_p = points; 
    std::vector<Point> y_p = points; 
    std::sort(x_p.begin(), x_p.end(), Point::sortByX); 
    std::sort(y_p.begin(), y_p.end(), Point::sortByY); 

    p_iterators_array<2> closest_result = closest_side_pair(points.begin(), x_p.begin(), y_p.begin(), points.size()); 
    //Separate call of closest_split_pair 
    //closest_result = closest_split_pair(points.begin(), closest_result, points.size()); 
    std::cout << "Closest pair are: " << std::endl; 
    for(auto p: closest_result) { 
     std::cout << p->x_coordinate << ", " << p->y_coordinate << std::endl; 
    } 
} 

Answer 1

closest_side_pairルーチンには2つのバグがあります。

eucledian_closestルーチンを呼び出すと、その関数に渡されるベクトルの長さはdelimiterですが、これはsizeになるはずです。同様に、closest_split_pairを呼び出すと、渡されるベクトルの長さはdelimiterになります。それはsizeでなければなりません。

現在のところ、closest_split_pairは、中点がpoints_iterator + delimiter/2にあるとします。points_iterator + size/2にしたいと考えています。これは混乱するように見えますが、 'delimiter'をclosest-side_pairの 'size'に置き換えるだけで、コードが機能するはずです。