Home

Awesome

Implementation of Bentley-Ottmann algorithm

This program is part of the assessment work of the course "12RNA - Robust Numerical Algorithms" lectured at FNSPE CTU in Prague.

Java implementation of Bentley–Ottmann sweep line algorithm for listing all crossings in a set of line segments in 2D geometry. The aplication contains a simple GUI.

The algorithm, as described by Bentley and Ottmann, assumes that the following conditions are satisfied:

  1. No two line segment endpoints or crossings have the same x-coordinate
  2. No line segment endpoint lies upon another line segment
  3. No three line segments intersect at a single point
<img src="https://github.com/valenpe7/bentley-ottmann/raw/master/bentley-ottmann.gif" width="400" height="400">

Find more about the algorithm here: https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm

In case of any questions, please submit an issue to this GitHub project repository.