Personal tools
You are here: Home Courses Computational Geometry Fall 2017/2018 Programming Assignment
« August 2019 »
August
SuMoTuWeThFrSa
123
45678910
11121314151617
18192021222324
25262728293031
Log in


Forgot your password?
 

Programming Assignment

General

Your solution to this exercise should consist of at least one source file, CMakeLists.txt (input to cmake), and a pdf file called Knn.pdf. The latter should provide some basic information about your program. It should also describe the algorithm implemented.

Running cmake on the CMakeLists.txt file followed by compilation and linkage should produce an executable called knn.

You can run the following commands to generate the CMakeLists.txt file:

cd /path/to/program 
cgal_create_CMakeLists -s executable 
cmake -DCGAL_DIR=$HOME/CGAL-4.11 . 
make

Add the following lines to the generated CMakeLists.txt file in order to add c++11 support

set(CMAKE_CXX_STANDARD 11)
set(CMAKE_CXX_STANDARD_REQUIRED TRUE)

The program knn accepts three arguments on the command line, namely, the dimension, the name of a file containing the input points and the name of the file containing the query points. A rational number is given either as a decimal number or as a numerator and denominator separated by '/' (e.g., 1/3), where the numerator and denominator are both unlimited integers. When given as a decimal number it is first converted to the nearest floating-point number, and then to a rational number represented by a numerator and a denominator. Observe that such numbers may have long bit lengths, and, as a consequence, arithmetic operations on them may be slow.

Your code must run on Ubuntu 16.04 using g++ 5.4.0

You must use a single thread.

Input, output, and more

You are given an example code in which you should write your code (do not change main.cpp! it will be swapped during our test).

Note that this version of main.cpp contains our code for testing the correctness of your output.

main.cpp main.cpp

#include <fstream>
#include <sstream>
#include <ostream>
#include <set>
#include <boost/lexical_cast.hpp>
#include <boost/timer.hpp>
#include <CGAL/Cartesian_d.h>
#include <CGAL/Gmpq.h>
#include <CGAL/Kernel_d/Point_d.h>


#include "knn.h"


typedef CGAL::Gmpq                      Number_type;
typedef CGAL::Cartesian_d<Number_type>  Kernel;
typedef Kernel::Point_d                 Point_d;

Point_d read_point(size_t d, std::ifstream& is)
{

  std::vector<Number_type> point_to_be;
  for(int i=0;i<d;++i)
  {
	Kernel::FT c;
	is >> c;
	point_to_be.push_back(c);
  }
  Point_d point(d,point_to_be.begin(),point_to_be.end());
  return point;
}

Kernel::FT squared_dist_d(Point_d p, Point_d q, size_t d)
{
    Kernel::FT res = 0;
    for (size_t i=0; i < d ;++i)
    {
	res += (p[i] - q[i]) * (p[i] - q[i]);
    }
    return res;
}




using namespace std;

//argv: ./a.out dimension input_points_file query_points_file
int main(int argc, char* argv[])
{
  if (argc < 4) {
    std::cerr << "Format: ./a.out dimension input_points_file query_points_file" << std::endl;
    return 1;
  }

  auto d = boost::lexical_cast<size_t>(argv[1]);

  const auto* build_filename = argv[2];
  std::ifstream  build_is;
  build_is.open(build_filename);
  if (!build_is.is_open()) {
    std::cerr << "Failed to open " << build_filename << "!" << std::endl;
    return -1;
  }
  size_t bulidn;
  build_is >>  bulidn;
  std::vector<Point_d> build_points;
  for (size_t i = 0; i <  bulidn; ++i) {
    build_points.push_back(read_point(d, build_is));
  }

  const auto* test_filename = argv[3];
  std::ifstream test_is;
  test_is.open(test_filename);
  if (!test_is.is_open()) {
    std::cerr << "Failed to open " << test_filename << "!" << std::endl;
    return -1;
  }
  size_t testn;
  test_is >> testn;
  std::vector<Point_d> test_points;
  for (auto i = 0; i <  testn; ++i) {
    test_points.push_back(read_point(d, test_is));
  }
  
  //create a set of the build points
  std::set<Point_d> pset(build_points.begin(), build_points.end());


  Knn<Kernel> knn(d, build_points.begin(), build_points.end());
  for (size_t k = 2; k < 10; ++k) {
      for (auto it = test_points.begin(); it != test_points.end(); ++it) {
	  std::vector<Point_d> res;
	  res.reserve(k);
	  boost::timer timer;
	  knn.find_points(k,*it,std::back_inserter(res));
	  auto secs = timer.elapsed();
	  std::cout<<secs<<" time"<<std::endl;



	  //----------------------------------------------//
	  //code for testing the output of knn.find_points
	  //----------------------------------------------//
	  
	  //1. we should get k points or less if k > n
	  if ((k!= res.size()  && k<=build_points.size()) ||
	      res.size() > k)
	  {
	      std::cerr << "Not enough neighbors" << std::endl;
	      return -1;
	  }

	  //2. make sure that all reported points are points 
          //    from the build_points
	  for (auto rit = res.begin(); rit != res.end(); ++rit)
	  {
	      if (pset.find(*rit)  == pset.end())
	      {
		  std::cerr << "Reported point was not part of the build point set" << std::endl;
		  return -1;
	      }
	  }  

	  //3. make sure that each reported point appears once in res
	  std::set<Point_d> res_set(res.begin(), res.end());
	  if (res_set.size() < res.size())
	  {
	      std::cerr << "A point was reported as a neighbor more than once" << std::endl;
	      return -1;

	  }
	    

	  //4. make sure that there is no point from build_points that is 
          //   closer to the query point than the farthest point in res
          //   and that is not reported in res.
	  //   Make sure that every point whose distance to the query is as the 
          //   distance of the farthest point to the query, is lexicographically greater than the farthest point in res.

	  //find maximal in res (point whose dist to test_point it is maximal)

	  size_t ind_of_max = 0;
	  Kernel::FT maxdist = squared_dist_d(res[0], *it, d);
	  for (auto  j=1; j < res.size() ; ++j){
	      Kernel::FT j_dist = squared_dist_d(res[j], *it, d);
	      if (maxdist < j_dist){
		  ind_of_max = j;
		  maxdist = j_dist;
	      }
	      else if (maxdist ==  j_dist){
		  if (res[ind_of_max] < res[j])
		      ind_of_max = j;
	      }
	  }
      
      
	  Point_d& max_neighbor = res[ind_of_max];

	  //verify that no other point in the data set is closer to *it then the farthest in res.
	  //If there is a point whose distance from *it is the same then verify it is lexicographically greater than the point in res obtaining the max distance
	  for (auto pit = build_points.begin(); pit != build_points.end(); ++pit)
	  {
	      if (*pit == max_neighbor)
		  continue;
	      Kernel::FT pit_dist = squared_dist_d(*pit, *it,d);
	      if ((pit_dist == maxdist && *pit < max_neighbor) || (pit_dist < maxdist))
	      {
		  //verify that *pit is reported in res
		  if (res_set.find(*pit) == res_set.end())
		  {
		      std::cerr << "A potential neighbor was not reported" << std::endl;
		      return -1;
		  }
	      }
	  }
      
      }   
  }
     
  return 0;
}
 

knn.h

#include <vector>

template <typename Kernel>
class Knn {
public:
typedef typename Kernel::Point_d                 Point_d;
  //input: d - the dimension
  // itreator to the input points
  template <typename InputIterator>
  Knn(size_t d, InputIterator beginPoints, InputIterator endPoints)
  {
    //your build code 
  }

  //input:   const refernce to a d dimensional vector which represent a d-point.
  //output:  a vector of the indexes of the k-nearest-neighbors points
  template <typename OutputIterator>
  OutputIterator find_points(size_t k,const Point_d &it,OutputIterator oi)
  {
    //your query code
    return oi;
  }
};

The input files are text files. The format of the file containing the points is as follows:

n a11 a21 .. ad1 a12 a22 .. ad2 ... a1n a2n .. adn

where n is the number of distinct points and each point is given by its d coordinates, which are rational numbers.

There will be a contest between all the different programs (including ours).

An example of a CMakeLists.txt file that can be used to build the program above can be found here.

Your code will be tested by the output of the function "find_points".

Contest

As part of the contest the performance of your programs will be compared on various inputs.

Make sure your program can handle at least several thousands of input points of dimension 15 in various special positions.

Installation and Assistance

You can obtain the latest CGAL public release from here.
The CGAL installation manual is available here.
Further detailed instructions for installing CGAL on Windows is available here. This is a bit outdated though.
Ipe is a drawing editor for creating figures in PDF or (encapsulated) Postscript format.

Examples of input files

Here are some examples of input files containing random 3D points.

10_points_3d.txt

100_points_3d.txt

200_points_3d.txt

500_points_3d.txt

1000_points_3d.txt

main.cpp for older CGAL versions (before 4.9)

Take a look at version.h file in CGAL directory to understand which version of CGAL is installed.

If your  CGAL version is older than CGAL 4.9, you should use the following file as your main.cpp file:

main_for_older_cgal_versions.cpp

In this file we replace the < operator for Point_d comparison with a function that compares points lexicographically.

Results

 

 

 

dimension
build 
test

CGAL Adar Zeitak Amir Barda Andrey Leshchenko Elior Frig Guy Rom Ido Kessler Ido Spector Itamar Behar Lewi Yuval Matan Harel Or Ostrovsky Tomer Davidor Yehonatan Zecharia Tomer Ben Moshe & Matan Hasson
3 build 0.000011 0.003576 0.005582 0.004238 0.001816 0.004784 0.003014 0.002543 0.002313 0.003664 0.003741 0.002211 bad results 0.001557 0.001942
1000 K=10 0.289855 0.186861 1.965841 1.51019 0.340401 2.40119 0.235306 0.144615 0.187913 3.643119 0.265164 0.28456 bad results 0.190332 3.820499
1000 k=999 4.287719 3.09743 86.915527 62.3824 3.057725 2.85611 2.436562 2.993322 3.846108 4.057755 6.033381 5.673974 bad results 3.538207 4.36328

















3 build 0.000002 0.000234 0.000384 0.00019 0.000043 0.000217 0.000087 0.000429 0.000177 0.000195 0.000143 0.000168 0.000104 0.000163 0.000076
100 On 1,1 K=10 0.011017 0.01672 0.254191 0.207178 0.026842 0.020504 0.017797 0.02046 0.023471 0.035296 0.024018 0.0323 0.027755 0.027759 0.036187
100 On 0,0 k=99 0.039367 0.022737 0.601061 0.37423 0.025917 0.018971 0.020189 0.031729 0.030738 0.036624 0.042305 0.047993 0.033776 0.03192 0.038683

















3 build 0.00002 0.005867 0.008395 0.006943 0.001756 bad results 0.004056 0.006066 0.003681 0.005368 0.00509 0.003623 bad results 0.00359 0.002419
1593 on sphere K=10 0.027028 0.00271 0.079594 0.044859 0.004375 bad results 0.002913 0.004562 0.00473 0.006103 0.006556 0.008486 bad results 0.004905 0.005248
center k=1592 0.020458 0.006363 0.198327 0.097957 0.005068 bad results 0.005566 0.005183 0.007145 0.007294 0.007872 0.008972 bad results 0.006899 0.008958

















10 build 0.000004 0.000718 0.002251 0.000693 0.000331 0.002642 0.002294 0.00046 0.000609 0.000584 0.002502 0.000345 bad results 0.000468 0.000412
300 K=10 0.967514 0.601354 10.907986 8.77238 0.917361 0.623879 0.660795 0.644251 0.876567 0.937287 0.906376 1.458277 bad results 0.904755 0.953781
300 k=299 1.018771 0.660224 20.344609 14.9283 0.878589 0.630154 0.633097 0.665899 0.932571 0.961103 1.385119 1.503131 bad results 0.916947 0.990846

















15 build 0.000004 0.000373 0.00162 0.000412 0.000192 0.002856 0.001608 0.000281 0.00032 0.000524 0.002157 0.000275 0.000498 0.00029 0.000295
200 K=10 0.622119 0.396479 7.247204 6.06047 0.620481 0.406435 0.415555 0.424264 0.580756 0.610696 0.763421 0.981132 0.602287 0.59732 0.611936
200 k=199 0.647226 0.418928 12.647563 9.37608 0.594281 0.405254 0.414603 0.422924 0.601403 0.61749 0.813261 0.979852 0.601245 0.596538 0.660783

















15 build 0.000001 0.000207 0.001044 0.000238 0.000081 0.001059 0.000683 0.000417 0.000181 0.00022 0.000866 0.000131 0.000131 0.000145 0.000114
100 on 1,1 K=10 0.1795 0.114276 1.955115 1.65086 0.173727 0.116282 0.116733 0.122419 0.167289 0.169052 0.222708 0.270803 0.177021 0.163603 0.171439
100 on 0,0 k=99 0.192521 0.125386 3.037345 2.26155 0.165303 0.115053 0.122769 0.123961 0.174766 0.172371 0.233432 0.273699 0.17214 0.163387 0.176806
Document Actions