Home > Articles, Data Structures & Algorithms > Implementation of closest point calculation.

Implementation of closest point calculation.

This program demonstrates the use of an array and is representative of the usual situation in which we store data in one array to process them later. It counts the number of pairs of N randomly generated points of the unit square, which can be connected to a line segment of length less than ‘d’, using the point data type. Because the execution time of this program is O(n2), it can’t be used for large N.

You should know that the implementation of the algorithm does not take into account issues of data input validation or proper management of dynamic memory (e.g. avoiding memory leaks) because it is only necessary to highlight the logic of the algorithm.

Interface (point.h) of the data structure ‘point’.

#ifndef _POINT_H
#define _POINT_H

struct point {
  float x, y;
};

float dist (point, point);

#endif // _POINT_H

Implementation (point.cpp) of the data structure ‘point’.

#include <cmath>
#include "point.h"

float
dist (point a, point b) {
 float dx = a.x - b.x;
 float dy = a.y - b.y;

 return sqrt (dx * dx + dy * dy);
}

Driver (main.cpp) – use of the data structure.

#include <iostream>
#include <cstdlib>
#include "point.h"
using namespace std;

float
randFloat () {
  return 1.0 * rand () / RAND_MAX;
}

int
main (int argc, char *argv[]) {
  float d; int N, i, cnt = 0;

  if (!argv[1] || !argv[2])
    return EXIT_FAILURE;

  d = atof (argv[2]);
  N = atoi (argv[1]);

  srand (time (NULL));

  point *a = new point[N];

  for (i = 0; i < N; i++) {
    a[i].x = randFloat ();
    a[i].y = randFloat ();
  }

  for (i = 0; i < N; i++)
    for (int j = i + 1; j < N; j++)
      if (dist (a[i], a[j]) < d)
        cnt++;

  cout << cnt << " pairs within " << d << endl;

  return EXIT_SUCCESS;
}
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: