fork(8) download
copy 
  1. /**
  2. * Closest pair
  3. * Input: N points (x,y)
  4. * Output: A pair of points (x1,y1),(x2,y2) which are closest.
  5. * Algorithm: Line sweep (see http://w...content-available-to-author-only...r.com/tc?module=Static&d1=tutorials&d2=lineSweep)
  6. * 
  7. * Coder: Erel Segal http://t...content-available-to-author-only...s.fm/rentabrain
  8. * Created: 2010-12-15
  9. */
  10.  
  11. #include <iostream>
  12. #include <algorithm>
  13. #include <set>
  14. #include <map>
  15. #include <vector>
  16. #include <time.h>
  17. #include <math.h>
  18. #include <assert.h>
  19. #include <limits>
  20. using namespace std;
  21.  
  22.  
  23. template <class Iterator> ostream& print (ostream& out, Iterator iFrom, Iterator iTo) {
  24. 	for (; iFrom!=iTo; ++iFrom) out << *iFrom << " ";
  25. 	return (out << endl);
  26. }
  27.  
  28. template <class T> ostream& operator<< (ostream& out, const vector<T>& v) {
  29. 	return print (out, v.begin(), v.end());
  30. }
  31.  
  32. template <class T> ostream& operator<< (ostream& out, const set<T>& v) {
  33. 	return print (out, v.begin(), v.end());
  34. }
  35.  
  36. const int INF = 999999999;
  37.  
  38. struct Point {
  39. 	int x, y;
  40. 	Point() {x=y=INF;}
  41. 	Point(int _x, int _y) { x=_x; y=_y; }
  42. 	friend istream& operator>> (istream& in, Point& r) { in >> r.x >> r.y; return in; }
  43. 	friend ostream& operator<< (ostream& out, const Point& r) { out << r.x << "," << r.y; return out; }
  44. };
  45.  
  46. bool lefter(const Point& A, const Point& B) { return A.x < B.x; }
  47. bool righter(const Point& A, const Point& B) {  return A.x > B.x; }
  48. bool lower(const Point& A, const Point& B) {  return A.y < B.y; }
  49. bool upper(const Point& A, const Point& B) {  return A.y > B.y; }
  50. float euclidean_distance(const Point& A, const Point& B) {  return sqrt( (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y) ); }
  51.  
  52.  
  53. class PointCollection {
  54. 	vector<Point> myPoints;
  55. 	typedef vector<Point>::const_iterator MyPointsIterator;
  56.  
  57. public:
  58. 	PointCollection(int N=0): myPoints(N) {}
  59.  
  60. 	void clear() { myPoints.clear(); }
  61.  
  62. 	void add(const Point& p) {
  63. 		myPoints.push_back(p);
  64. 	}
  65.  
  66. 	void closestPairBruteForce() const {
  67. 		Point p1, p2;
  68. 		float shortestDistance = INF;
  69. 		for (MyPointsIterator i=myPoints.begin(); i!=myPoints.end(); ++i) {
  70. 			for (MyPointsIterator j=myPoints.begin(); j!=i; ++j) {
  71. 				float currentDistance = euclidean_distance(*i, *j);
  72. 				if (currentDistance<shortestDistance) {
  73. 					shortestDistance = currentDistance;
  74. 					p1 = *i;
  75. 					p2 = *j;
  76. 				}
  77. 			}
  78. 		}
  79. 		cout << "Brute Force Closest pair: " << p1 << " - " << p2 << " (distance: " << shortestDistance << ")" << endl;
  80. 	}
  81.  
  82. 	/// @see http://w...content-available-to-author-only...r.com/tc?module=Static&d1=tutorials&d2=lineSweep
  83. 	void closestPairLineSweep() const {
  84. 		Point p1, p2;
  85. 		float shortestDistance = INF;
  86. 		//cout << "update shortest distance to " << shortestDistance << endl;
  87.  
  88. 		// A. Order myPoints by the x coordinate:
  89. 		vector<Point> myPointsOrderedByX(myPoints);
  90. 		::sort(myPointsOrderedByX.begin(), myPointsOrderedByX.end(), &lefter);
  91. 		//cout << "myPointsOrderedByX: " << myPointsOrderedByX;
  92.  
  93. 		// B. Maintain an active set of points - candidates to be a closest-pair with the current point.
  94. 		//    The set is ordered by the y coordinate:
  95. 		typedef set<Point, bool(*)(const Point&,const Point&)> ActiveSetType;
  96. 		typedef ActiveSetType::iterator ActiveSetIterator;
  97. 		ActiveSetType myActiveSet (&lower);
  98.  
  99. 		MyPointsIterator leftestPointInActiveSet = myPointsOrderedByX.begin();
  100.  
  101. 		// C. Line sweep the points by X order:
  102. 		for (MyPointsIterator point=myPointsOrderedByX.begin(); point!=myPointsOrderedByX.end(); ++point) {
  103.  
  104. 			// C-1. Scan the active set for points that may be closer to the current point than the shortest distance:
  105. 			Point lowestPoint (point->x, point->y - shortestDistance);
  106. 			Point highestPoint (point->x, point->y + shortestDistance);
  107. 			ActiveSetIterator lowest = myActiveSet.lower_bound(lowestPoint);
  108. 			if (lowest!=myActiveSet.end()) {
  109. 				ActiveSetIterator highest = myActiveSet.upper_bound(highestPoint);
  110. 				//cout << "scan active set between " << lowestPoint << "<=" << *lowest << " and " << *highest << "<" << highestPoint << endl;
  111.  
  112. 				for (ActiveSetIterator other=lowest; other!=highest; ++other) {
  113. 					//cout << "  compare " << *point << " with " << *other << endl;
  114. 					float currentDistance = euclidean_distance(*point,*other);
  115. 					if (currentDistance<shortestDistance) {
  116. 						shortestDistance = currentDistance;
  117. 						//cout << "    update shortest distance to " << shortestDistance << endl;
  118. 						p2 = *other;
  119. 						p1 = *point;
  120. 					}
  121. 				}
  122. 			}
  123.  
  124. 			// C-2. Update the active set - keep only the points whose distance with the current point is at most the shortest distance
  125. 			//cout << "insert " << *point << " to active set" << endl;
  126. 			myActiveSet.insert(*point);
  127. 			while (point->x - leftestPointInActiveSet->x > shortestDistance) {
  128. 				//cout << "  remove " << *leftestPointInActiveSet << " from active set" << endl;
  129. 				myActiveSet.erase(*leftestPointInActiveSet);
  130. 				++leftestPointInActiveSet;
  131. 			}
  132. 		}
  133.  
  134. 		cout << "Line Sweep  Closest pair: " << p1 << " - " << p2 << " (distance: " << shortestDistance << ")" << endl;
  135. 	}
  136.  
  137. 	friend ostream& operator<< (ostream& out, PointCollection points) {
  138. 		return (out << points.myPoints);
  139. 	}
  140.  
  141. 	void fillRandomX(int N) {
  142. 		Point p;
  143. 		for (int i=0; i<N; ++i) {
  144. 			p.x = rand()%1000;
  145. 			p.y = 500;
  146. 			add(p);
  147. 		}
  148. 	}
  149.  
  150. 	void fillRandomY(int N) {
  151. 		Point p;
  152. 		for (int i=0; i<N; ++i) {
  153. 			p.y = rand()%1000;
  154. 			p.x = 500;
  155. 			add(p);
  156. 		}
  157. 	}
  158.  
  159. 	void fillRandomXY(int N) {
  160. 		Point p;
  161. 		for (int i=0; i<N; ++i) {
  162. 			p.y = rand()%10000;
  163. 			p.x = rand()%10000;
  164. 			add(p);
  165. 		}
  166. 	}
  167.  
  168. 	void fillRandomXYWithCheckpoints(int N) {
  169. 		// In this testcase, the min distance should always be 0, as there
  170. 		//	are two identical points.
  171. 		Point checkpoint(rand()%1000, rand()%1000);
  172. 		int i1 = rand()%N;
  173. 		int i2 = rand()%N;
  174. 		Point p;
  175. 		for (int i=0; i<N; ++i) {
  176. 			if (i==i1 || i==i2) {
  177. 				add(checkpoint);
  178. 			} else {
  179. 				p.y = rand()%1000;
  180. 				p.x = rand()%1000;
  181. 				add(p);
  182. 			}
  183. 		}
  184. 	}
  185. };
  186.  
  187.  
  188. int main() {
  189. 	srand(time(NULL));
  190. 	PointCollection points;
  191. 	points.clear();
  192. 	points.fillRandomXY(1000);
  193. 	points.closestPairLineSweep();
  194. 	points.closestPairBruteForce();
  195. }
  196.  
Success #stdin #stdout 0.01s 2864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Line Sweep  Closest pair: 7164,3160 - 7161,3152 (distance: 8.544)
Brute Force Closest pair: 7161,3152 - 7164,3160 (distance: 8.544)
https://ideone.com/QiwYN
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!