Personal tools
You are here: Home Courses Computational Geometry Fall 2015/2016 Assignments 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 (do_cover.pdf) that provides some basic information about your program. In particular, it should specify whether your program has any limitations, such as 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 the 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, VC11, or VC12, 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 Amit Chen Danny Itay Ran Ravid Shahar Ran P. Yonatan
    3   -   0.002262
    0.006942 0.007309 0.004472 0.006934 0.010391 0.003942 0.001949 0.005578
    4   +   0.001538
    0.006400 0.009999 0.005297 0.007607 0.008704 0.015776 0.003088 0.006036
    7   -   0.002801
    0.025371 0.013117 0.011971 0.012689 0.015128 0.009891 0.006557 0.133258
    8   +   0.005868
    0.022393 0.017447 0.004012 0.015742 0.01736 0.049435 0.007869 2.025860
    15   -   0.007576
    0.083046 0.025096 0.025750 0.025398 0.028684 0.020585 0.029213 2.025320
    16 polygon, camera, [ipe,pdf] +   0.008454
    0.072926 0.03158 0.024250 0.031481 0.034525 0.102324 0.033254 26.786000
    31   -   0.020675
    0.313908 0.052813 0.089711 0.056045 0.057526 0.047947 0.171843 26.839600
    32   +   0.020160
    0.250307 0.067233 0.08702 0.067353 0.070765 0.312847 0.184122 26.694400
    63   -   0.042763
    1.244360 0.125409 0.606162 0.145131 0.135233 0.123224 1.359960 295.883000
    64   +   0.045220
    0.889832 0.153551 0.615392 0.175407 0.165319 1.012183 1.308000  
    127   -   0.124893
    5.363790 0.331874 6.139140 0.447188 0.363722 0.352483 11.515900  
    128   +   0.120891
    3.479580 0.386773 6.070050 0.501641 0.425604 4.041759 11.577600  

    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 Amit Chen Danny Itay Ran Ravid Shahar Yonatan
    3 30 10 15.00000000000010   -   0.001549
    0.001725 0.006838 0.003168 0.004506 0.007719 0.004417 X
    3 30 10 15.00000000000001   +   0.002548
    0.001325 0.002461 0.004502 0.002124 0.007185 0.002509 0.004245
  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 No. of Cameras Input Result Efi Amit Chen Danny Itay Ran Ravid Shahar Ran P. Yonatan
    2 2   +   0.001937
    0.003092 0.001282 0.002942 0.003706 0.004418 0.001510 0.001939 0.002364
    4 4   +   0.001633
    0.007982 0.002582 0.002886 0.007304 0.010360 0.005330 0.001633 0.008906
    8 8   +   0.003726
    0.013365 0.005648 0.011793 0.018196 0.018483 0.007024 0.005082 0.012283
    16 16   +   0.014659
    0.024642 0.014222 0.020933 0.042295 0.042785 0.010217 0.022552 0.046873
    32 32 polygon, camera, [ipe,pdf] +   0.040603
    0.077966 0.036712 0.067218 0.113926 0.106834 0.028674 0.066270 0.140769
    64 64   +   0.142078
    0.281906 0.119218 0.276539 0.350436 0.293578 0.072228 0.268371 0.561421
    128 128   +   0.592920
    1.150170 0.366384 1.185460 1.226950 0.889332 0.232305 1.199540 2.434050
    256 256   +   2.568950
    4.809810 1.313300 5.432450 4.802200 3.099110 0.852469 5.274540 10.425200
    512 512   +   12.504000
    20.868500 2.171910 26.119600 3.592360 2.212420 3.340062 25.416400  
    1024 1024   +   59.375400
      9.595110   16.436000 9.298280 14.908733    
    Extra
    No. of Legs No. of Cameras Input Result Efi Amit Chen Danny Itay Ran Ravid Shahar Ran P. Yonatan
    2 1   -   v
    v
    v
    v
    X v
    v
    v
    X
    4 3   -   v
    v
    v
    v
    X v
    v
    v
    X
    8 7   -   v
    v
    v
    v
    X v
    v
    v
    X
    16 15   -   v
    v
    v
    v
    X v
    v
    v
    X
    32 31 - -    v v
    v
    v
    X v
    v
    v
    X
    64 63   -    v v
    v
    v
    X v
    v
    v
    X
    128 127   -    v v
    v
    v
    X v
    v
    v
    X
    256 255   -    v v
    v
    v
    X v
    v
    v
    X
    512 511   -    







    1024 1023   -      






  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