Skip to content

Instantly share code, notes, and snippets.

@pancanin
Created September 19, 2022 07:22
Show Gist options
  • Save pancanin/fa2fc26605fd8e976132f31221841df6 to your computer and use it in GitHub Desktop.
Save pancanin/fa2fc26605fd8e976132f31221841df6 to your computer and use it in GitHub Desktop.
Closest 2 points in 2D space
// Example program
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
using namespace std;
struct Point {
int x;
int y;
};
struct Result {
Point a;
Point b;
int distance;
void calcDistance() {
int yD = b.y - a.y;
int xD = b.x - a.x;
distance = sqrt(yD * yD - xD * xD);
}
};
Result findClosest(vector<Point>& points) {
cout << points.size() << endl;
if (points.size() == 3) {
Result r;
r.a = points[0];
r.b = points[1];
r.calcDistance();
Result r2;
r2.a = points[0];
r2.b = points[1];
r2.calcDistance();
Result r3;
r3.a = points[1];
r3.b = points[2];
r3.calcDistance();
if (r.distance <= r2.distance) {
if (r.distance <= r3.distance) {
return r;
} else {
return r3;
}
} else {
if (r2.distance <= r3.distance) { return r2; } else { return r3; }
}
}
if (points.size() == 2) {
Result r;
r.a = points[0];
r.b = points[1];
r.calcDistance();
return r;
}
auto mid = points.begin() + (points.size() / 2);
auto start = points.begin();
auto end = points.end();
vector<Point> leftSide(mid - start);
copy(start, mid, leftSide.begin());
vector<Point> rightSide(end - mid);
copy(mid, end, rightSide.begin());
Result leftRes = findClosest(leftSide);
Result rightRes = findClosest(rightSide);
if (leftRes.distance <= rightRes.distance) { return leftRes;} else { return rightRes; }
}
int main()
{
vector<Point> points = {
Point{1,1},
Point{1,3},
Point{3,7},
Point{4,4},
Point{6,9},
Point{7,4},
Point{8,2},
Point{9,2}
};
Result r = findClosest(points);
cout << "First point is: x=" << r.a.x << " and y=" << r.a.y << " and second point is with x=" << r.b.x << " and y=" << r.b.y << endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment