Closest pair of points problem in C++

Given n points, find two points with the smallest distance to each other.

Closest pair of points

The examples listed below demonstrate two algorithms in C++ to tackle this problem. One algorithm simply checks every combination of points, also known as a brute force approach. The other one is an efficient algorithm which uses a divide and conquer approach.  The divide and conqueror algorithm is much faster compared to the brute force algorithm.

Brute force algorithm

void World::CheckDistance(HDC hdc){
	double distance;

	// Brute force O(N^2)
	for(int i=0;i<dotCollection.size();i++){
		for(int t=0;t<dotCollection.size();t++){

			if(i != t){
				distance = GetDistance(dotCollection[i],dotCollection[t]);

				if(distance < this->shortestDistance){
					this->shortestDistance = distance;
					this->shortestFrom = dotCollection[i];
					this->shortestTo = dotCollection[t];
				}
			}
		}
	}

	this->Mark(hdc,this->shortestFrom,this->shortestTo);
}

Divide and conquer algorithm

// Divide and Conquer O(N log N)
void World::CheckDistanceDAC(HDC hdc){
	double distance;

	vector<Dot*> sortedDots;

	// Copy current collection
	for(int i=0;i<dotCollection.size();i++){
		sortedDots.push_back(dotCollection[i]);
	}

	// Used for comparing X values of dots
	struct compareXStruct {
		bool operator ()(Dot* firstDot, Dot* secondDot) {
			POINT fXY = firstDot->GetXY();
			POINT sXY = secondDot->GetXY();

			if(fXY.x < sXY.x){
				return true;
			} else {
				return false;
			}
		}
	};

	// Sort the dots using the X values
	sort(sortedDots.begin(),sortedDots.end(),compareXStruct());

	vector<Dot*> closestDots = this->findClosest(sortedDots);

	this->Mark(hdc,closestDots[0],closestDots[1]);
}
vector<Dot*> World::findClosest(vector<Dot*> px){
	vector<Dot*> tempDots;

	int n = px.size();

	if(n <= 3){
		return this->shortest(px);
	} else {
		int left = n / 2; // left side
		int right = n / 2 + n % 2; // right side

		vector<Dot*> Pleft;
		vector<Dot*> Pright;
		vector<Dot*> Pleftmin;
		vector<Dot*> Prightmin;
		vector<Dot*> Pclosest;

		for(int i=0;i < left;i++){
			Pleft.push_back(px[i]);
		}

		for(int i=0;i < right;i++){
			Pright.push_back(px[i+left]);
		}

		Pleftmin = this->findClosest(Pleft); // closest dots on the right
		Prightmin = this->findClosest(Pright); // closest dots on the left
		Pclosest = this->mergePlanes(Pleftmin,Prightmin);

		return Pclosest;
	}

}
vector<Dot*> World::mergePlanes(vector<Dot*> p1, vector<Dot*> p2){
	vector<Dot*> pMin;

	vector<Dot*> pAll;

	for(int i=0;i<p1.size();i++){
		pAll.push_back(p1[i]);
	}

	for(int i=0;i<p2.size();i++){
		pAll.push_back(p2[i]);
	}

	vector<Dot*> closest;

	closest = shortest(pAll);

	double D = this->GetDistance(closest[0],closest[1]);

	for(int i=0;i<p1.size();i++){

		for(int j=0;j<p2.size();j++){
			Dot* pi = p1[i];
			Dot* pj = p2[j];

			if(pi->equals(pj))
				continue;

			POINT p1XY = p1[i]->GetXY();
			POINT p2XY = p2[j]->GetXY();

			double xi = p1XY.x;
			double xj = p2XY.x;
			double yi = p1XY.y;
			double yj = p2XY.y;

			if(xi < xj + D && yi + D > yj && yj > yi - D){
				if(this->GetDistance(pi,pj) < D){
					vector<Dot*> distVector;
					distVector.push_back(pi);
					distVector.push_back(pj);

					return distVector;
				}
			}
		}

	}

	pMin.push_back(closest[0]);
	pMin.push_back(closest[1]);

	return pMin;
}

vector<Dot*> World::shortest(vector<Dot*> ps){
	vector<Dot*> shortestVector;

	Dot* p1;
	Dot* p2;

	double distance = 8192;

	for(int i=0;i<ps.size();i++){
		for(int j=0;j<i;j++){
			if(i == j)
				continue;

			Dot* ptemp1;
			Dot* ptemp2;

			ptemp1 = ps[i];
			ptemp2 = ps[j];

			double newDistance = this->GetDistance(ptemp1,ptemp2);

			if(newDistance < distance){
				distance = newDistance;
				p1 = ptemp1;
				p2 = ptemp2;
			}
		}
	}

	shortestVector.push_back(p1);
	shortestVector.push_back(p2);

	return shortestVector;
}

The VC++ project belonging to the above examples can be downloaded from here.

Update: double yj = p2XY.x; has been modified to double yj = p2XY.y; .

This entry was posted in C++ and tagged , , , , , , , , , , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

2 Comments

  1. Posted January 26, 2012 at 10:45 am | Permalink

    Hi,
    I’m not sure if i’m right but i guess i found a failure.

    In “World::mergePlanes” during the two for-loops you are writing this:
    double xi = p1XY.x;
    double xj = p2XY.x;
    double yi = p1XY.y;
    double yj = p2XY.x; <- and there seams to be the problem
    shouldn't this be an "p2XY.y"?

    but maybe i'm wrong after all.

    greetings
    Onkeliroh

    • Posted January 28, 2012 at 10:28 pm | Permalink

      You’re right, thanks. I’ve modified the post to correct this issue.

      Ferhat

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Why ask?