Polygon Generator

A Program to generate Random Polygons using three different algorithms, write them to a file in WKT format and visualise them using OpenGL.

Authors

Chandradhar Rao , Mihir M Kestur , Dhruval PB

Project Structure

Random-Polygon-Generator
├── Images                        [Contains sample Images]
├── Makefile
├── Profiler.sh                   [A Shell script for profiling our program]
├── Distribution.py               [A Python program for graphing the Distribution of the generated polygons]
├── Metrics.py                    [A Python program for visualising the metrics generated after profiling the program]
├── Plotter.py                    [A Python program for plotting the polygons from a WKT file using matplotlib]
├── README.md
├── Requirements.txt
└── src
    ├── Driver.cpp                [Contains the main funtion]
    ├── Graphics.cpp              [Contains the OpenGL graphing routines]
    ├── WKT_writer.cpp            [Contains the routines to write the generated Polygons to a file in WKT format]
    ├── Algorithms                [Contains various polygon generation algorithms]
    │   ├── Naive.cpp
    │   ├── Polar.cpp
    │   └── SpacePartition.cpp
    ├── Classes                   [Contains the definitions of all the classes used]
    │   ├── Classes.cpp               
    │   └── Classes.hpp               
    └── Utils                     [Contains utility functions]
        ├── ConvexHull.cpp
        ├── ConvexHull.hpp
        ├── Geom.cpp
        ├── Geom.hpp
        ├── Helpers.cpp
        └── Helpers.hpp

Dependencies

• A C++ compiler like g++ or clang
• popt.h (for command line input)
• OpenGL (for visualising the generated polygons)
• Python 3 interpreter with all the packages in Requirements.txt installed

Compiling and running

Install the dependencies:

$ sudo apt install libpopt-dev freeglut3-dev
$ python3 -m pip install -r Requirements.txt

Compile using the make utility:

$ make polygonGenerator -j$(($(nproc)*2))

Run the following command to print the help doc for the program:

$ ./build/bin/polygonGenerator -?

Compile the Shared Library using:

$ make polygonGenerator_SharedLibrary -j$(($(nproc)*2))

Run the Profiler using:

$ chmod +x ./Profiler.sh
$ ./Profiler.sh 5

Here, the 5 represents the number of iterations the Profilers runs the program. In any iteration i, 100i polygons are generated using each of the three algorithms.

Metrics Analysis

The leftmost graph shows how the size of the WKT file changes as the number of polygons generated increases. The other two plots show a comparison of time taken by the three algorithms for generating large number of polygons.

Sample Maps

These are a few graphs generated by plotting multiple random polygons on the same OpenGL window (Note: The random variables are sampled from different distributions)

Sampling distribution	Polar Algorithm	Space Partition Algorithm	Naive Polygon Algorithm
Uniform
Binomial
Geometric
Poisson
Normal

Samples of Distribution Plots

Sampling distribution	Polar Algorithm	Space Partition Algorithm	Naive Polygon Algorithm
Uniform
Binomial
Geometric
Poisson
Normal