main.cpp

/* 

Author: James Henry 

Program: main.cpp

Algorithm: Closest Pair of Points algorithm

Functionality: This program uses recursion and the Divide and Conquer approach to find the closest pair of points in a dataset. 
I applied the Master Theorem for time complexity analysis, achieving an optimized runtime of O(n log n). The program 
calculates Euclidean distance for accuracy, parses files for input processing, and uses sorting for efficient computation.

Complexity: O(n log(n))

*/
#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <limits>

// Function to calculate Euclidean distance
double euclideanDistance(const std::vector<double>& point1, const std::vector<double>& point2) {
    double sum = 0.0;
    for (size_t i = 0; i < point1.size(); ++i) {
        sum += std::pow(point1[i] - point2[i], 2);
    }
    return std::sqrt(sum);
}

// Function to parse and read points from the formatted file
bool parsePointsFromFile(const std::string& filename, std::vector<std::vector<double>>& points) {
    std::ifstream infile(filename);
    if (!infile) {
        std::cerr << "Error: Could not open file " << filename << std::endl;
        return false;
    }

    std::string content;
    std::string line;

    // Reading the whole file content as a single string
    while (std::getline(infile, line)) {
        content += line;
    }

    // Remove unwanted characters like '{', '}', and ',' from the file content
    content.erase(std::remove(content.begin(), content.end(), '{'), content.end());
    content.erase(std::remove(content.begin(), content.end(), '}'), content.end());
    content.erase(std::remove(content.begin(), content.end(), ','), content.end());

    // Use a stringstream to process the cleaned content
    std::istringstream iss(content);
    double coord;
    std::vector<double> point;

    // Read the coordinates from the cleaned string content
    while (iss >> coord) {
        point.push_back(coord);

        // Each point has two coordinates; after reading two coordinates, store the point
        if (point.size() == 2) {
            points.push_back(point);
            point.clear();  // Reset for the next point
        }
    }

    if (points.size() < 2) {
        std::cerr << "Error: File must contain at least two points." << std::endl;
        return false;
    }

    return true;
}

// A utility function to find the distance between the closest points in a strip of points
double stripClosest(std::vector<std::vector<double>>& strip, double d) {
    double min = d; // Initialize the minimum distance as d

    std::sort(strip.begin(), strip.end(), [](const std::vector<double>& a, const std::vector<double>& b) {
        return a[1] < b[1]; // Sort according to y coordinates
    });

    // Compare all points in the strip
    for (size_t i = 0; i < strip.size(); ++i) {
        for (size_t j = i + 1; j < strip.size() && (strip[j][1] - strip[i][1]) < min; ++j) {
            double distance = euclideanDistance(strip[i], strip[j]);
            if (distance < min) {
                min = distance;
            }
        }
    }

    return min;
}

// Recursive function to find the smallest distance
double closestUtil(std::vector<std::vector<double>>& points, size_t left, size_t right) {
    // If there are 2 or 3 points, then use the brute force method
    if (right - left <= 3) {
        double minDist = std::numeric_limits<double>::max();
        for (size_t i = left; i < right; ++i) {
            for (size_t j = i + 1; j <= right; ++j) {
                double distance = euclideanDistance(points[i], points[j]);
                if (distance < minDist) {
                    minDist = distance;
                }
            }
        }
        return minDist;
    }

    // Find the middle point
    size_t mid = left + (right - left) / 2;
    std::vector<double> midPoint = points[mid];

    // Recursively find the smallest distance in the left and right halves
    double dl = closestUtil(points, left, mid);
    double dr = closestUtil(points, mid + 1, right);

    // Find the smaller of two distances
    double d = std::min(dl, dr);

    // Build an array strip[] that contains points close to the line dividing the points
    std::vector<std::vector<double>> strip;
    for (size_t i = left; i <= right; ++i) {
        if (std::abs(points[i][0] - midPoint[0]) < d) {
            strip.push_back(points[i]);
        }
    }

    // Find the closest points in the strip and compare with the overall minimum distance
    return std::min(d, stripClosest(strip, d));
}

// The main function that finds the smallest distance
double closest(std::vector<std::vector<double>>& points) {
    // Sort the points by x coordinates
    std::sort(points.begin(), points.end(), [](const std::vector<double>& a, const std::vector<double>& b) {
        return a[0] < b[0];
    });

    // Use recursive function closestUtil to find the smallest distance
    return closestUtil(points, 0, points.size() - 1);
}

int main() {
    std::vector<std::vector<double>> points;
    std::string filename = "inputfile1.txt";  // Test it using the input files 

    // Parse points from the file
    if (!parsePointsFromFile(filename, points)) {
        return 1; // Exit if parsing fails
    }

    // Find the smallest distance
    double minDistance = closest(points);

    // Output the smallest distance rounded to 3 decimal places
    std::cout << "The smallest distance is: " << std::fixed << std::setprecision(3) << minDistance << std::endl;

    return 0;
}