Finding closest pair of 2D points, using divide-and-conquer

I'm learning C++ as well as algorithms. Here's my implementation of finding the closest pair problem. I tried to minimize memory by using only iterators.

And points are being read from points.txt file content:

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

Output is:

Closest pair are: 
3, 5
4, 5

Here's the code:

```
#include
#include
#include
#include
#include
#include

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
using p_iterator = typename std::array::iterator;

template
using p_iterators_array = std::array::iterator, SIZE>;

void initialize_points(std::array &points) {
double x, y;
int i = 0;
char c;
std::ifstream infile("./points.txt");
while((infile >> x >> c >> y) && (c == ',') && (i
p_iterators_array eucledian_closest(T &points, int size) {
p_iterators_array closest_arr;
double closest_distance = DBL_MAX, distance = 0.0;

for(int i = 0; i
p_iterators_array closest_split_pair(p_iterator points_iterator, p_iterators_array &closest_side_pairs) {
std::vector> split_pairs;
p_iterators_array final_result;
double closest_distance = DBL_MAX, distance = 0.0;

typename std::array::iterator midpoint = points_iterator + (SIZE/2);

//filtering points to only points in sigma-2sigma rectangle
for (size_t i = 0; i x_coordinate)
p_iterators_array closest_side_pair(p_iterator points_iterator, p_iterator x_arr_iterator, p_iterator y_arr_iterator) {
std::size_t delimeter = SIZE / 2 ;
if(delimeter closest_left, closest_right, result;

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

if(calculate_distance(*(closest_left

Here are some observations that may help you improve your code.

Use all required #includes

The code uses std::vector which means that it should #include . It was not difficult to infer, but it helps reviewers if the code is complete.

Use better names

The Point class is well named and easy to understand, but member functions sortByX and sortByY are not as good because they only return the result of a comparison and don't actually sort anything by themselves. I might call them Xless and Yless which would be a better explanation of what they do.

Eliminate "magic numbers"

There are a few numbers in the code, such as 2 and 10 that have a specific meaning in their particular context. Generally it's better to avoid that and give such constants meaningful names. That way, if anything ever needs to be changed, you won't have to go hunting through the code for all instances of "10" and then trying to determine if this particular 10 is relevant to the desired change or if it is some other constant that happens to have the same value.

Don't hardcode file names

The points.txt might be something that a user of this program wants to place elsewhere or name something else, so both hardcoding the name and burying it in the middle of the program are unhelpful.

Write more flexible code

Right now, only sets of exactly ten 2-D points can be evaluated. What if I have twelve points? What if I want to compare 3D points? The code could be made much more flexible in both cases by rethinking both the algorithms and the data structures. I'd recommend using a std::array for each point and a std::vector of those points for the main array.

Use idiomatic C++

The initialize_points is an odd standalone function taking a very particular kind of structure as an argument. It would make more sense to write an extractor for the Point class and then call it until the end of the list. For example, to do nothing except create 2D points from std::cin and then echo them back to std::cout we might have something like this:

int main()
{
    std::vector> points;
    Point p{{}};
    while (std::cin >> p) {
        points.push_back(p);
    }
    for (const auto &p : points) {
        std::cout << p << "\n";
    }
}

The standard inserter and extractors are typically implemented as friend functions:

template 
class Point : public std::array {
public:
    static constexpr char DELIMITER{','};
    Point(std::array lst) 
        : std::array{lst}
    {}
    friend std::ostream &operator>(std::istream &in, Point &p) {
        if (in >> p[0]) {
            for (std::size_t i=1; i > c >> p[i];
                if (c != DELIMITER) {
                    in.setstate(std::ios::failbit);
                }
            }
        }
        return in;
    }
};

Fix the bug

Try putting 2,1 as the first and last coordinate pair, and you'll see that the program incorrectly identifies the closes pair as (3,5) and (4,5).

Reconsider the algorithm

It's not necessary to sort on both the X and Y coordinates. See this description of a planar solution for a detailed explanation of an optimal algorithm. The existing code appears to attempt some but not all of this algorithm.

Avoid calculations that are not needed

When optimizing for performance (only after the code is correct!), it's often useful to ponder which calculations might not need to be done. In this case, it's mostly not necessary to do calculate the sqrt to get the actual distance between points since ordering may be done on squared distances with no loss of generality or correctness.

StackExchange Code Review Q#142956, answer score: 3