Skip to content

Bentley Ottman Algorithm to find the intersection points in the 2d plane for lines. The algorithm is input sensitive and has a running time complexity of O((N + K) log N) and space complexity of O(N).

Notifications You must be signed in to change notification settings

neilmehta31/Bentley_Ottmann_algo_CompGeo

Repository files navigation

Design and Analysis of algoritm Assignment 1

How to run

Run the ./run.sh file to run the algorithm followed by the plotting of the segments and the intersection points.

Usage

testcases.txt file contains the segments in the specific form of x1 y1 x2 y2.
output.txt file will contain the intersection points after running the algorithm.
plotting.py contains the python script for plotting the segment.

About

Bentley Ottman Algorithm to find the intersection points in the 2d plane for lines. The algorithm is input sensitive and has a running time complexity of O((N + K) log N) and space complexity of O(N).

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published