Skip to content

Provides implementations of Polygon Triangulation, DCEL and Convex Hull Generation

License

Notifications You must be signed in to change notification settings

RikilG/Geometry-Algorithms

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

10 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Computational Geometry Assignment

Getting Started

This repo contains implementations of the following 3 algorithms:

  • Convex Hull computation using divide and conquer tangent approach
  • DCEL (Doubly Connected Edge List) data structure implementation
  • Polygon Triangulation using the following algorithms:
    • Plane Sweep method to divide polygon into monotones.
    • Triangulation of each monotone polygon

Each algorithm is implemented seperately in its folder using C++ language. A README file in each folder describes how to run and other information about that particular folder.

Algorithm Directory
├── datasets # folder containing datasets to be tested upon
├── docs # folder containing the documentation of the source code
├── src # folder containing the source code
└── README.md # a readme file describing the algo and how to run it

Plotting Output

Each directory contains a plot.py python program which can be used to plot the output of each algorithm. output of algorithm can be directly piped to this program or given as command line argument

# do this in the src directory if program is compiled in the same directory
# the text in the [] brackets is optional. if given, it prints the input dataset also
./a.out ../datasets/data.txt | ../plot [-i ../datasets/data.txt]

# without piping, save output to file and use it
./a.out ../datasets/data.txt > output.txt
../plot -o output.txt [-i ../datasets/data.txt]

References

The following references have been used to understand and implement the algorithms: