Home » courses » Computational Geometry, Spring 2020

Computational Geometry, Spring 2020

Spring 2020, 0368-3173-01

Lecture: Monday, 16:00-19:00, Schreiber 006

Instructor: Dan Halperin , danha@post

Office hours: Monday 19:00-20:00

Grader: Yair Karin, Golan Miglioli-Levy

The course covers fundamental algorithms for solving geometric problems such as computing convex hulls, intersection of line segments, Voronoi diagrams, polygon triangulation, and linear programming in low dimensional space. We will also discuss several applications of geometric algorithms to solving problems in robotics, GIS (geographic information systems), computer graphics, and more.

Bibliography

The main textbook of the course is:

Computational Geometry: Algorithms and Applications (CGAA), 3rd edition by M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf.

A bibliographic list for the course

Slides

I will often use slides that accompany the main textbook of the course.The slides are by Marc van Kreveld and they can be found
at the following site: Geometric Algorithms

Assignments, Examination and Grade

The standard assignments will account for 10% of the final grade, in case they improve the final grade.
The grade in the final exam will account for the remaining 90% of the grade in the course.
Exam(ple) [pdf]

Although the assignment grades will be used only for improving the final grade, submission of the assignments is mandatory and a prerequisite for taking the exam.

About halfway through the course (probably earlier), we will present a programming assignment.

More details on the assignment will be provided later.

We encourage you to submit the programming assignment as well. This is not mandatory.

If however you do submit it, then your grade breakdown will be 10% the standard assignments,
15% the programming assignment, and 75% the final exam. Here as well,
the assignments grades will be counted toward the final grade only if they improve it.

The assignments will appear here.

Assignment no. 1 file , due: April 5th, 2020.
Assignment no. 2 file , due: April 20th, 2020.
Assignment no. 3 file , due: May 11th, 2020.
Assignment no. 4 file , due: June 1st, 2020.
Programming assignment (optional) file (revised 21/5/20, notice the order of cosine,sine), due: June 18th, 2020. Additional information
Assignment no. 5 (optional) file , due: June 24th, 2020.

Course Summary

Below you’ll find a very brief summary of what was covered in class during the semester.
This should not be taken as a complete description of the course’s contents.

09.03.20
What is Computational Geometry?
Course outline, motivation and techniques. A slow convex hull algorithm. Orientation (Side-of-line) test. (slides1, up till Slide #27.)
16.03.20 (online)
The Doubly Connected Edge List, DCEL, and map overlay (CGAA, Chapter 2). (slides2b)Euler’s formula for plane graphs, proof without induction (Proofs from THE BOOK, Aigner-Ziegler, 5th Ed., Chapter 13)
23.03.20 (online)
Point-Line duality, arrangements of lines in the plane, the zone theorem and incremental construction of the arrangement (CGAA, Chapter 8). Applying all this to solve collinearity, and to sum of squares of face complexities.
30.03.20 (online)
Polygon triangulation and the art gallery problem (Slides)
20.04.20 (online)
Casting, half-plane intersection and Linear Programming in low dimensions (slides4a).Supplementary material: unbounded LP2D and more (Slides, revised 23.04.20).

27.04.20 (online, 2 hours)
LP in 3D.Smallest enclosing circle (CGAA Section 4.7, slides4b). GeoGebra files: SEC is unique, SEC new point on boundary

04.05.20 (online)
Point-Line duality, arrangements of lines in the plane, the zone theorem and incremental construction of the arrangement (CGAA, Chapter 8) (slides8).
More on arrangements and duality (slides).
The minimum area triangle problem (CGAL Arrangements and Their Applications, Section 4.2.1)
11.05.20 (online):

Orthogonal range searching I: kd-trees (CGAA, Chapter 5)(slides5a)CGAL: An overview (Slides)

18.05.20 (online):
Orthogonal range searching II: kd-trees (cont’d), range trees, fractional cascading, handling degeneracies through composite numbers (CGAA, Chapter 5)(slides5b)

25.05.20 (online):

Trapezoidal maps and planar point location (CGAA, Chapter 6) (slides6, up till Slide #56)Nearest-neighbor search using kd-trees (Slides)

Nearest-neighbor search in robot motion planning (Slides)

01.06.20 (online):
Trapezoidal maps and planar point location, cont’d (CGAA, Chapter 6) (slides6)Guaranteed logarithmic-time point location (slides, paper)Voronoi diagrams of points in the plane: structure, complexity, and Fortune’s algorithm (CGAA, Chapter 7) (slides7_combined)

08.06.20 (online):
Voronoi diagrams, continued (CGAA, Chapter 7) (slides7_combined)Arcs on the beach line (slides)Triangulating planar point sets and Delaunay triangulations (CGAA, Chapter 9) (slides)Alpha shapes, a glimpse (slides9, Slides #60-67), in 3D: paper by Edelsbrunner and Mucke

15.06.20 (online):
Connections between major geometric structures (slides)Computing convex hulls in 3D (CGAA, Chapter 11) (slides)22.06.20 (online)
The casting problem revisited (slides) (paper)

Programming Assignment, Additional Information

Submission

Please provide an archive that contains all source and documentation files in a flat directory structure (that is, place all files in one directory); Use Moodle to submit the file. Do not forget to state your names and IDs. Specify how to run the program in case the instructions deviates from the instructions below.

Your implementation must be robust and accurate; therefore, you should use CGAL. However, you can develop your code in pure C++ or in Python and use Python bindings.

You may send questions about the exercise to Dr. Efi Fogel via email ([email protected]).

General

If you develop in C++, your solution should consist of at least one source file, CMakeLists.txt (input to cmake), and a pdf file called nesting.pdf that describes the implemented algorithm and discusses the performance. Running cmake on the provided CMakeLists.txt followed by compilation and linkage should produce an executable called nesting.

If you develop in Python, provide a nesting.py script as well as the nesting.pdf file as described above.

For instructions on how to use the CGAL Python bindings (Windows 10):

1. Download the precompiled bindings for Windows

2. Make sure you work with Python 3.7 64 bit

3. If Microsoft Visual C++ is not installed on your computer download and run vc_redist.x64.exe from here: https://support.microsoft.com/en-us/help/2977003/the-latest-supported-visual-c-downloads

4. Put the python bindings file (.pyd) in the directory containing the file nesting.py (from the zip we supplied)

5. Put the libgmp-10.dll and libmpfr-4.dll in the directory containing the file nesting.py

You should now be able to import the library and use the provided classes and functions in your code.

Compiling the CGAL Python bindings yourself (Specific for Ubuntu)

Install Python >= 3.4, 64 bit.
Install boost
1. Download boost_1_73_0.tar.gz from this link https://www.boost.org/users/download/.
2. Extract the tar file using the following command (with the correct path to tar file). It will extract the file to your current directory.
```
  tar -zxvf <PATH-TO-boost-TAR-FILE>
```
3. In the extracted directory you’ll find a file named bootstrap.sh. Run the following command:
```
  ./bootstrap.sh --with-python=python3.7 --with-python-version=3.7
```
4. Run:
```
  sudo ./b2 install
```
  The last step (boost installation) should take a while.

Install other CGAL dependencies:

sudo apt-get install libgmp-dev

sudo apt-get install libmpfr-dev

sudo apt-get install cmake

Install CGAL
1. Extract the tar file to a location at your choice.
2. Set the environment variable CGAL_DIR to temporarily point to the directory where CGAL was extracted. (replace <PATH-TO-EXTRACTED-DIRECTORY> with the correct path)
```
 export CGAL_DIR="<PATH-TO-EXTRACTED-DIRECTORY>"
```
Download the archive file of the CGAL Python bindings sources [link]
Uncompress and extract the files.
```
tar -zxvf cgal-python-bindings.tar.gz
```
Run cmake in the sources root directory. You can set the following variables depending on your needs:
CGALPY_DCEL_NAME:
plain – Default DCEL
faceExtended – DCEL extented with face data
allExtended – DCEL extended with data for faces, halfedges and vertices
(Other options, although presented in the cmake GUI, are not supported)
CGALPY_KERNEL_NAME:
epec [exact predicates exact constructions kernel – uses rational number type]
epic [exact predicates inexact constructions kernel – faster]
CGALPY_GEOMETRIC_TRAITS_NAME – determines the curve type of the arrangement:
segment
linear
nonCachingSegment
algebraic
conic
circleSegment

The recommended values are marked in bold.

The following command sets the values in bold (replace <PATH-TO-CGAL-PYTHON_BINDINGS> with the correct path to cgal-python-bindings directory) :
```
cmake <PATH-TO-CGAL-PYTHON_BINDINGS> -DCGALPY_DCEL_NAME=allExtended  -DCGALPY_KERNEL_NAME=epec -DCGALPY_GEOMETRY_TRAITS_NAME=segment
```
Compile the bindings library via the makefile or the solution generated by cmake.
Set the environment variable PYTHONPATH to point at the directory where the generated library resides.

Input

The program nesting accepts 2 arguments on the command line:

the name of the file that contains the description of the bounding rectangle R.
the name of the file that contains the description of the simple polygon P.

Both files have the same format: An integral number that specifies the number of vertices followed by the vertices of the polygon in counterclockwise order; each vertex is a pair of rational numbers.

A rational number is given by a numerator and denominator separated by ‘/’ (e.g., 1/3), where the numerator and denominator are both unlimited integers.

You may assume the first vertex of P is located at (0,0), and second vertex lies of the positive side of the X axis. You may assume R is axis aligned, and the first vertex of R is the bottom left vertex of the rectangle, located at (0,0).

m x1 y1 x2 y2 ... xm ym

Output

The program should export a series of quadruples (x,y,c,s)—one quadruple for every congruent copy of P. Each number in a quadruple is a rational number.

(x,y) is the location of v1 = (x1,y1).
(c,s) is the normalized direction of the vector (v1,v2). (cosine & sine, s^2 + c^2 should sum to exactly 1.)

You may use the function CGAL::rational_rotation_approximation() (also exposed through the CGAL Python bindings) to obtain rational sine and cosine approximations of any desired level of precision for a given direction. See: https://doc.cgal.org/latest/Kernel_23/group__rational__rotation__approximation__grp.html

Solution verification and visualization

You are provided a python program to verify and visualize your solutions.

The program (polygon_packing.py) accepts 4 arguments:

the name of the file that contains the description of the bounding rectangle R.
the name of the file that contains the description of the simple polygon P.
the name of the file that contains your solution (as described in the output subsection).
a path to a file that contains some angle (c,s) (as described in the output subsection).

The program verifies that the provided solution is valid and displays the placements of P inside the bounding rectangle on the screen.

Additionally, the program displays the remaining valid placements for the first vertex of P when P is rotated by the angle in the 4th argument (By using Minkowski sums, see https://doc.cgal.org/latest/Minkowski_sum_2/index.html).

How to run the program:

1. Download the program files: [link]

2. The program requires the installation of PyQt5 (pip install PyQt5).

3. On Linux you may need to install libxcb-xinerama0 (sudo apt-get install libxcb-xinerama0).

4. The program uses the CGAL python bindings (The code can serve as a demonstration of how they may be used). On Windows, make sure that the python bindings file (.pyd), libgmp-10.dll and libmpfr-4.dll are

in the same directory as polygon_packing.py, or alternatively make sure libgmp-10.dll and libmpfr-4.dll are reachable from the PATH system variable and the python bindings file from your PYTHONPATH system variable.

5. Run polygon_packing.py with the four command line arguments as described above (the folder includes example input files).

8.6.20 Update: The solution verification and visualization program has been updated, please download and use the version currently provided in the link above (updated).

Books

M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications , 3rd Edition Springer, 2008.

J. O’Rourke,
Computational Geometry in C , 2nd Edition
Cambridge University Press, 1998


J.-D. Boissonnat and M. Yvinec
Algorithmic Geometry
Cambridge University Press, 1995, 1998 (English version)
J.E. Goodman , J. O’Rourke, and Csaba Toth (editors)
Handbook of Discrete and Computational Geometry , 3rd Edition CRC Press LLC, Boca Raton, FL, 2017.
J.-R. Sack and J. Urrutia (editors)
Handbook of Computational Geometry
North Holland, 2000.
M. Sharir and P.K. Agarwal
Davenport-Schinzel Sequences and Their Geometric Applications
Cambridge University Press, New York, 1995
K. Mulmuley
Computational Geometry: An Introduction Through Randomized Algorithms
Prentice Hall, Englewood Cliffs, NJ, 1994
F.P. Preparata and M.I. Shamos
Computational Geometry: An Introduction
Springer-Verlag, New York, NY, 1985.
H. Edelsbrunner
Algorithms in Combinatorial Geometry Springer Verlag, Heidelberg, 1987

Yair Oz - Webcreator

Contact

Mobile. 052-4703139 | WhatsApp
Email. [email protected]