Closest Distance 2D Points

[oleg9419]

In the following code I don't understand why am I splitting the y left and y right.
(closest distance between 2 points in 2D)

Am I splitting the y left and y right so that I can concatenate them afterwards and then build the strip,only
according to these concatenated halves ?

PS : Finding the min. distance between sorted x right and x left works fine , only problem is with the strip.

Thank you very much

#ifndef CLOSESTPAIR_H_
#define CLOSESTPAIR_H_

#include <float.h>
#include <math.h>

typedef struct Point2D
{
	double x;
	double y;
}Point2D;

double distance(Point2D*, Point2D*);

inline double distance(Point2D* p1, Point2D* p2)
{
	return sqrt((p1->x - p2->x)*(p1->x - p2->x) + (p1->y - p2->y)*(p1->y - p2->y));
}


double brute_search(Point2D* p, const unsigned len)
{
	if(len < 2) return DBL_MAX;

	//find the min distance between 3 or 2 points
	double min_distance = DBL_MAX;

	for(int i = 0; i < len - 1; ++i)
	for(int j = i + 1; j < len; ++j)
	{
		double d = distance(&p[i], &p[j]);
		if(d < min_distance) min_distance = d;
	}

	return min_distance;
}


double strip_min(Point2D* p,const unsigned len)
{
	double default_distance = DBL_MAX;
	double dist = DBL_MAX;

	for(int i = 0; i < len - 1; ++i)
		for(int j = i + 1;(j < 7 && j < len); ++j)
		{
			default_distance = distance(&p[i], &p[j]);
			if(default_distance < dist) dist = default_distance;
		}

	return dist;
}


double closest_pair(Point2D* pX, Point2D* pY, const unsigned start, const unsigned end)
{
	const unsigned midd_x = end / 2;
	Point2D splitter = pX[midd_x];

	//base case
	if((end - start) <= 3) return brute_search( pX, end);

	double xl_min = closest_pair(pX, pY, start, midd_x);
	double xr_min = closest_pair((pX + midd_x), pY, midd_x, (end - midd_x));
	double x_min = xr_min < xl_min ? xr_min : xl_min;

	//split and copy array of Y into 2 halves
	int r = 0;
	int l = 0;
//	printf("min %f mid is %f and xr_min is %f xlmin %f\n",x_min, splitter.y, xr_min,xl_min);
	Point2D y_right[midd_x];
	Point2D y_left[end - midd_x];

	for(int i = 0; i < end; ++i)
	{
		if(pY[i].x <= splitter.x)
			y_right[r++] = pY[i];
		else
			y_left [l++] = pY[i];
	}


//	for(int i = 0; i < r;++i) printf("%i (%f,%f)\n",i ,y_right[i].x, y_right[i].y);
//	for(int i = 0; i < l;++i) printf("%i (%f,%f)\n",i ,y_left[i].x, y_left[i].y);

	//what size ?
	Point2D strip[end];
	unsigned strip_size = 0;

	for(int i = 0; i < end; ++i)
	{
		if(fabs(pX[i].x - splitter.x) < x_min)
			strip[strip_size++] = pY[i];
	}
//	for(int i = 0; i < end; ++i) printf("strip %i. %f %f\n", i, strip[i].x, strip[i].y);

	double y_min = strip_min(strip, strip_size);
	printf("y_min = %f\n", y_min);

	return x_min < y_min ? x_min : y_min;

}
#endif /* CLOSESTPAIR_H_ */   

#include <stdio.h>
#include "closestpair.h"

int main(void)
{
	Point2D points[] = {
						  {.x = -5.f, .y = 6.f},
						  {.x = -3.f, .y = 2.f},
						  {.x = -1.f, .y = 3.f},
						  {.x = 0.0f, .y = 0.7f},
						  {.x = 0.0f, .y = 3.f},
						  {.x = 0.0f, .y = 0.6f},
						  {.x = 1.f,  .y = 3.f},
						  {.x = 4.f,  .y = 5.f},
						};

	Point2D points_[] = {
						  {.x = 0.0f, .y = 0.6f},
						  {.x = 0.0f, .y = 0.7f},
						  {.x = -3.f, .y = 2.f},
						  {.x = 1.f,  .y = 3.f},
						  {.x = 0.f,  .y = 3.f},
						  {.x = -1.f, .y = 3.f},
						  {.x = 4.f,  .y = 5.f},
						  {.x = -5.f, .y = 6.f},
						};

	printf("%.3f is closest distance\n", closest_pair(points, points_,0,sizeof(points)/sizeof(points[0])));


return 0;
}

[helios]

1. What's the overall algorithm you're trying to implement? It sort of looks like you want the minimum distance between any two points from different sets, but I can't tell.
2. Aren't brute_search() and strip_min() equivalent, other than strip_min() fails if len < 7?

[oleg9419]

1. http://en.wikipedia.org/wiki/Closest_pair_of_points_problem
2. I was confused already , with the sorting of Y halves , hence the strip_min is also wrong I guess.

[helios]

The input to closest pair of points is a single sequence of points. Why two arrays (points and points_)?

brute_search() is a solution to the problem.

[oleg9419]

I heard about this problem from coursera.org(Stanford algorithm lessons) .
They said that in order to achieve nlogn complexity time we must have a pre-sorted Y array of these points.
simply by brute force is more time consuming.