Hi,

Guest

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

Adrian Mariano

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 wikipedia page says:

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.

OpenSCAD mailing list

To unsubscribe send an email to discuss-leave@lists.openscad.org

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 wikipedia page says:
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.
>
>
> _______________________________________________
> OpenSCAD mailing list
> To unsubscribe send an email to discuss-leave@lists.openscad.org
>

Replying to:

Empathy v1.0
2023 ©Harmonylists.com