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
>
