Angle function and atan2

[Andrey Diduh]

Hi! I saw that you use atan2 function which is very heavy.

I see that you use it in Sweep.Angle function, and you need this function only to determinate is perpendicular lines, and if not in which side.

I don't understand your code very well, but maybe it would be less costly to replace atan with dot product (2 mul, 1 add)? If dot product is 0 - its 90, , if >0 <90 degree, if <0 >90 degree.

Thank you.

[obi]

Yes you are correct at the part where angle function is used just to determine if an angle is obtuse, a dot product and a sign check would be enough. 

At least atan2 is run in a part of the algorithm that is O(n) so the performance improvement will probably not be gigantic but non the less!

Thanks for the suggestion.

[Andrey Diduh]

I have one question, if you will. You must be hear about this one http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html (you have this implementation in python poly2tri version)

They claim that their algorithm complexity is O(n* log n ). And yours implementation based on  O(n* log n ) algorithm too. Does it faster than yours? I undersatnd that it makes thin and long triangles which not satisfies Delaunay condition.

--
You received this message because you are subscribed to the Google Groups "poly2tri" group.
To unsubscribe from this group and stop receiving emails from it, send an email to poly2tri+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[obi]

The constraint Delaunay algorithm is a sweep line algorithm. During triangulation there is a spatial traversal over the 2D plane. Think of it as a horizontal line going from bottom to top. Every edge of the polygon this line intersects create a subset of points that is part of the triangulation, called an advancing front. How many edges this sweeping line intersects at the same time during the traversal will impact the speed of the triangulation.

If this subset of points/edges is kept in a hierarchical search list this algorithm is guaranteed to perform at O(n*log(n)). The thing is that a balancing binary search tree will add more complexity in both time and computation and I tried several BST implementations and all made the triangulation slower. I decided to go with a linked list and a last instance cache for the advancing front. So in theory poly2tri can't guarantee worst case O(n*log(n)).

In practice poly2tri is pretty darned fast and have still to hear anyone complain about speed compared to other triangulation libs.

I suggest you try the triangulation libraries you consider using for your case and see which one's perform the best.

[obi]

Ah Mason Green did write some seidel triangulator in python. I have no knowledge of that one and that question must be answered by him both regarding speed and robustness. 

So your question boils down to which of the two triangulators to use? I can only vouch for the Delaunay version and that one should be pretty damn robust for simple polygons.

On Saturday, 5 April 2014 12:24:15 UTC+2, Andrey Diduh wrote:

[zzzzrrr]

The Seidel algorithm in practice is more than likely faster than the sweep line algorithm CDT algorithm, but certainly not as written in Python. Also, Seidel does not produce Delaunay triangles, which limits it's usefulness. 

I wrote the Seidel triangulator in Python for fun while researching triangulation algorithms several years ago. 

In any regard, Sweep line CDT is "fast enough" for anything you practically need throw at it in software. If you need blazing speed, try writing it on the GPU, e.g.:

http://www.comp.nus.edu.sg/~tants/cdt.html

Regards,

Mason

[Andrey Diduh]

I ask this, because I read paper http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html, and don't see why it have to be faster than yours. 

- It sort vertices using random algoritm, but it not faster than your sorting.

- It moves through vertices to find simple polygon (by calculating doted angle). And you do this, but to find is triangle meet Delaunay requirements.

I just not see where it have to be faster.

P.S. CUDA/OpenCL - is not an option, as it not supported widly.

--

[Andrey Diduh]

FYI. Performance comparsion results.

1) I was unable to use http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html implementation on less or more complex hulls. I read, that other people found it "a little bit buggy" too.

2) I found Ken Clarkson's Seidel implementation http://www.netlib.org/voronoi/hull.html. It triangulate debug2.dat in 64ms (I know, that it process convex polygons only). I also tried this reimplementation http://www.codeproject.com/Articles/587629/A-Delaunay-triangulation-function-in-C , as it generate random convex polygon. But it was even slower.

3) I tested this http://sites-final.uclouvain.be/mema/Poly2Tri/poly2tri.html with debug2.dat data. It triangulate it in 42ms. VS 2013 build, full optimization flag.

4) And than, I test your, with debug2.dat. It triangulate it in 25ms. I must admit, that this was QT project build, gcc 4.8 -O2 flag.

Hardware used in test: 

 - i7-4771 (all energy save functions, such as, floating frequency multiplier disabled)

 - 8 GB dual DDR2 1600Mhz

 - Windows 8.1

[obi]

Nice, thanks for the comparison.

Hope thats fast enough for your needs :)

[r3mi]

I implemented the suggestion in the JavaScript version. I managed to replace the two atan2 calls. This give about 5% to 10% performance improvement on my benchmark. Thanks Andrey !

[Andrey Diduh]

Well, nice to hear that. You are welcome.

--