### self intersection in polygons

SP
Sanjeev Prabhakar
Sun, Sep 10, 2023 11:58 AM

calculating the self intersections in polygons are important especially for
offset.

I wrote Bentley-Ottmann line sweep logic in python but it works out to be
less efficient (it takes around twice the time ) from my existing  logic.

Primary reason for this slow speed could be "python loops" which are much
slower than numpy and also my limited knowledge in python.

attached is the screen shot of the 2 logics written

In case anyone knows a better way to write this, please suggest.

calculating the self intersections in polygons are important especially for offset. I wrote Bentley-Ottmann line sweep logic in python but it works out to be less efficient (it takes around twice the time ) from my existing logic. Primary reason for this slow speed could be "python loops" which are much slower than numpy and also my limited knowledge in python. attached is the screen shot of the 2 logics written In case anyone knows a better way to write this, please suggest.
AM
Sun, Sep 10, 2023 12:16 PM

From looking at that code it looks like maybe you implemented the line
sweep algorithm without using the special data structures that are the key
to making it fast, namely the binary search tree and the priority queue.

The binary search tree may be any balanced binary search tree
https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree data
structure, such as a red–black tree
https://en.wikipedia.org/wiki/Red%E2%80%93black_tree; all that is
required is that insertions, deletions, and searches take logarithmic time.
Similarly, the priority queue may be a binary heap
https://en.wikipedia.org/wiki/Binary_heap or any other logarithmic-time
priority queue;

If you get a correct implementation of this then the line sweep method will
be faster for a large enough polygon, regardless of how bad loops are in
python or anything like that, because N log N always beats N^2 at some
point.  If the method turns out to be impractical in python for some
reason, such as slow loops, that will manifest by it being slower on normal
size (small) polygons, even while it is fast when ten million points or
whatever.

On Sun, Sep 10, 2023 at 7:59 AM Sanjeev Prabhakar sprabhakar2006@gmail.com
wrote:

calculating the self intersections in polygons are important especially
for offset.

I wrote Bentley-Ottmann line sweep logic in python but it works out to be
less efficient (it takes around twice the time ) from my existing  logic.

Primary reason for this slow speed could be "python loops" which are much
slower than numpy and also my limited knowledge in python.

attached is the screen shot of the 2 logics written

In case anyone knows a better way to write this, please suggest.