Bentley-Ottmann Algorithm Implementation

Question

Is there any existing Bentley-Ottmann Algorithm Implementation/library in C# or Java?

take a look at here ...http://stackoverflow.com/questions/4490331/implementing-the-bentley-ottmann-algorithm — Glory Raj, Nov 13 '11 at 17:34
Did you ever get this fully working? The Java implementation link is dead now. — Evan Parsons, Aug 22 '13 at 11:54
Not C# or Java, but heres a single-file implementation you could port http://stackoverflow.com/a/33199826/432509 — ideasman42, Oct 18 '15 at 15:59
Has anyone sighted a public C# implementation yet? Thank you! — Jeremy Tammik, Aug 04 '19 at 15:12

score 4 · Answer 1 · answered Nov 13 '11 at 18:01

4

Here is at least a C++ implementation (including description): http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm

answered Nov 13 '11 at 18:01

Martin Maurer

51
1

While technically this is a bentley-ottmann implementation, its only returning true/false. Not finding all intersection points. – ideasman42 Aug 02 '15 at 04:20

Óscar López · Accepted Answer · 2015-06-28T14:55:38.693

1

Here is a Java implementation of the Bentley-Ottman algorithm

edited Jun 28 '15 at 14:55

answered Nov 13 '11 at 17:43

Óscar López

232,561
37
312
386

1

Java link is still available here: http://web.archive.org/web/20040329071207/http://www.solyanik.com/sergey/sweep11/ – ideasman42 Jun 28 '15 at 10:20

score 0 · Answer 3 · answered Jan 12 '22 at 00:10

0

The implmentation at softsurfer.com is the Shamos-Hoey algorithm to decide if there is at least one intersection. And, if one is found, it stops. The code at the reference is for testing if a polygon is simple.

answered Jan 12 '22 at 00:10

user2924198

1
1

This does not provide an answer to the question. Once you have sufficient [reputation](https://stackoverflow.com/help/whats-reputation) you will be able to [comment on any post](https://stackoverflow.com/help/privileges/comment); instead, [provide answers that don't require clarification from the asker](https://meta.stackexchange.com/questions/214173/why-do-i-need-50-reputation-to-comment-what-can-i-do-instead). - [From Review](/review/late-answers/30795816) – Andres Gardiol Jan 14 '22 at 15:16
I was the author of that code, and that is my website. The website has been converted to a book, and this code is no longer available online, As for the code you are discussing, it was for the Shamos-Hoey algorithm which historically preceded the Bentley-Ottman. Shamos-Hoey was for testing if a polygon is simple, so it only returns true or false. It stops as soon as it finds one intersection. – user2924198 Jan 15 '22 at 16:36

Bentley-Ottmann Algorithm Implementation

3 Answers3

Linked