Personal tools
You are here: Home Courses Computational Geometry Spring 2014 Assignments Programming Assignment
« December 2019 »
December
SuMoTuWeThFrSa
1234567
891011121314
15161718192021
22232425262728
293031
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 (do_cover.pdf) that provides some basic information about your program. In particular, it should specify whether your program has any limitations, such as only whether it only handles the general position case. It should also describe the algorithm implemented.

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

If you organize all your sources in a single source file, say do_cover.cpp and place this file in a dedicated directory that does not contain anything else, you can simply run:

cgal_create_cmake_script example

to generate CMakeLists.txt.

The program do_cover accepts two arguments on the command line, namely, the name of the file that contains the description of the input polygon and the name of the file that contains the locations of the cameras. By default, the latter is called polygon.txt and former is called camera.txt. The following three commands are equivalent:

do_cover polygon.txt camera.txt
do_cover polygon.txt
do_cover

You can develop on Windows using VC10 or VC11, but the code must compile and run using g++ on Ubuntu.

Input and Output

Both input files are text files (as their extensions suggest). The format of the file that contains the description of a polygon is as follows:

n x0 y0 x1 y1 ... xn-1 yn-1

where n is the number of vertex points of the input polygons and each point is given by its x and y coordinates, which are rational numbers. A rational number is given either as a floating point or as a numerator and denominator separated by '/' (e.g., 1/3), where the numerator and denominator are both integers. The format of the file that contains the locations of the camera is identical.

Sample test cases:

Polygon
Camera Output
polygon.txt camera.txt Cover
polygon2.txt camera2.txt Cover
polygon3.txt camera3.txt Cover

 

There will be a contest between all the different programs (including mine). To this end you are also required to add to your code a timer that measures the execution time-consumption.

Use a Boost timer.

  • Add the directive below at the top of your cpp source file:
    #include <boost/timer.hpp>
  • Introduce a timer after reading the input files:
    boost::timer timer;
  • At the end of the code that executes the algorithm (and before the start of the code that prints out the final result) measure the elapsed time:
    double secs = timer.elapsed();

The output of the program should comprise two text lines. The first line should be:

"Execution time: <secs>"

where <secs> is the timer elapsed time.

The second line should be either 
"The cameras cover the polygon!"

or

"The cameras do not cover the point (x,y)"

where x and y are the coordinates of an uncovered point.

Contest

As part of the contest the performance of your programs will be compared. I plan to use three sets of input data described below. The results of the contest will be listed in the tables on this page.

  1. The first set comprises star-shaped polygons and corresponding camera positions. gen_star.pl is a perl script that generates two files, namely polygon.txt and camera.txt, in the format above. The generated polygon is star-shaped. The number of spikes is set though a switch of the command line as follows:
         gen_star.pl --spikes <num>
    Let n denote the number of spikes. The scripts also generates cameras located near the tips of n/2 of the spikes if n is even and (n+1)/2 if n is odd.  If n is even the cameras completely cover the polygon. However, removing one camera results with only a partial coverage. If n < 256 is odd, the cameras do not cover the polygon.

    No. of Spikes
    Input Result Efi Tomer K. + Tal
    Oleg Oded + Tomer G.
    Arik Yoav + Or Roee Geva + Shir Aviel
    3   - 0.003 0.003 0.005 0.003 0.003 0.006 0.001 0.188 0.005
    4   + 0.005 0.004  0.005 0.003
    0.005
    0.012 0.008 0.264 0.008
    7   - 0.024
    0.008
    0.014
    0.009
    0.011
    0.022 0.005 1.056 0.028
    8   + 0.028 0.011 0.015
    0.009
    0.014
    0.027 0.030 1.069 0.034
    15   - 0.127
    0.023
    0.051
    0.026
    0.040
    0.060 0.023 3.999 0.129
    16 polygon, camera, [ipe,pdf] + 0.141 0.027 0.057
    0.028
    0.099
    0.081 0.113 4.446 0.137
    31   - 0.833
    0.058
    0.265
    0.089
    0.214
    0.232 0.114 18.751 0.622
    32   + 0.865 0.062 0.272
    0.086
    0.257
    0.375 0.503 19.755 0.641
    63   - 6.007
    0.139
    1.613
    0.321
    1.957
    1.037 0.915 89.717 2.986
    64   + 6.048 0.158 1.805
    0.301
    2.617
    1.221 2.831
    3.039
    127   - 48.788
    0.407
    11.562
    1.238
    19.837
    5.606 4.901
    14.058
    128   + 48.574 0.431 11.623
    1.334
    22.065
    6.823 18.414
    13.787

    The script accepts the following options:
      --inner <radius>
      --outer <radius>
      --query <radius>
      --spikes <num>
    star_3.jpg

    The command below generates input, such that the camera do not cover the polygon
      gen_star.pl --outer 30 --query 15.0000000000001
    However, slightly changing the query radius, generate input, such that the camera do cover the polygon
      gen_star.pl --outer 30 --query 15.00000000000001


    No. of Spikes
    Outer
    Inner
    Query
    Input Result Efi Tomer k. + Tal
    Oleg Oded + Tomer G.
    Arik Yoav + Or Roee Geva + Shir Aviel
    3 30 10 15.00000000000010   -
    0.004
    0.002
    0.004
    0.003
    0.003
    0.006 0.002 0.194 0.006
    3 30 10 15.00000000000001   +
    0.004
    0.003
    0.002
    0.002
    0.003
    0.006 0.005 0.179 0.007
  2. The second set comprises snake-shaped polygons and corresponding camera positions. gen_snake.pl is a perl script that generates two files, namely polygon.txt and camera.txt, in the format above. The generated polygon has a shape of a snake. The number of horizontal  legs is set though a switch of the command line as follows:
      gen_snake.pl --legs <num>
    The scripts also generates as many camera as horizontal legs located near the intersection of a horizontal leg and a vertical leg, such that the cameras completely cover the polygon. However, removing one camera results with a only a partial coverage.
    No. of Legs
    Input Result Efi Tomer k. + Tal Oleg Oded + Tomer G.
    Arik Yoav + Or Roee Geva + Shir Aviel
    2   + 0.002 0.001 0.001
    0.001
    0.001
    0.002 0.003 0.226 0.002
    4   + 0.008 0.003 0.005
    0.002
    0.005
    0.007 0.012 0.894 0.006
    8   + 0.053 0.006 0.021
    0.006
    0.017
    0.027 0.057 3.558 0.025
    16   + 0.376 0.020 0.131
    0.014
    0.058
    0.121 0.348 14.491 0.105
    32
    polygon, camera, [ipe,pdf] + 2.998 0.061 0.834
    0.039
    0.226
    0.671 2.311 64.975 0.459
    64   + 27.045 0.226 6.371
    0.123
    1.176
    4.243 17.338
    2.012
    128   +
    0.937
    56.396
    0.447
    4.509
    29.98

    8.775
    256   +
    4.094
     
    1.733
    26.218



    39.462
  3. Each of you may provide me with three pairs of input files that you believe your program performs well with.

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.
Ipe is a drawing editor for creating figures in PDF or (encapsulated) Postscript format.

Efi Fogel hompage

Document Actions