[FEATURE REQUEST] Proposal: Add Bentley–Ottmann Algorithm for Line Segment Intersection

[Microindole]

What would you like to Propose?

I would like to propose adding an implementation of the Bentley–Ottmann algorithm to the geometry category. This algorithm efficiently finds all intersection points among a set of line segments in a plane.

Issue details

• Algorithm: Bentley–Ottmann
• Problem Statement: Given a set of line segments in a 2D plane, find all points where two or more segments intersect. This is a fundamental problem in computational geometry.
• Example:
  • Input: A list of line segments, e.g., Segment A: [(1, 1), (5, 5)], Segment B: [(1, 5), (5, 1)], Segment C: [(3, 0), (3, 6)]
  • Expected Output: A list of intersection points, e.g., [(3, 3)] (intersection of A, B, and C)
• File Path: src/main/java/com/thealgorithms/geometry/BentleyOttmann.java

Additional Information

• Why this is useful:
  • Adds a classic sweep-line algorithm, fundamental to computational geometry education.
  • Has applications in Computer Graphics (collision detection) and GIS (map overlays).
  • Fills a gap in the geometry package by providing an efficient method to find all intersections, complementing existing geometry algorithms.
• Implementation Notes:
  • The algorithm uses a sweep-line approach with an event queue (Priority Queue) and a status structure (Balanced Binary Search Tree).
  • Complexity is typically O((n+k) log n), where n is the number of segments and k is the number of intersections.
  • Implementation will include Javadoc and comprehensive JUnit tests covering various cases (including horizontal/vertical segments, coincident points, etc.).

I have searched the repository (DIRECTORY.md and src/main/java/com/thealgorithms/geometry/) and confirmed this algorithm is not currently implemented.