Who can recommend me a good sweep algorithm which would have good results for double data? Some documentation, methods, anything.
This is a sweep algorithm for detecting the intersection points of a graph in the 2-dimensional space. The graph is always closed.
The one in http://www.amazon.com/Computational-Geometry-Algorithms-Applications-Second/dp/3540656200 is pretty good.
The sweepline for testing intersections is pretty straightforward, though. Here's a paper to get you started: http://www.cs.umd.edu/~mount/Papers/crc-intersect.pdf.
I have implemented so far 3 variants for the sweep algorithm for detecting the intersection of a planar closed graph. I have big data that represent the graph (like 200 edges or more. The vertices are pairs of points in 2d the edges are a pair of two vertices- one being the source the other being the destination) which is read from another function implemented in a C++ library for some other purpose.
The problem is that the 3 implementation work fine on integers or doubles data that are not as long, but when I tried anyone of these 3 implementations on my datas representing the graph I got different result each time and not even the good ones.
-whether I have all the intersections that I want but some other points from the graph (which are not intersection)
-whether I have some points from the graph as result but some intersections that I need are missing from the computed result
-whether I have just the intersections needed. This all depends on the sort function that I had I saw and maybe on something else but I cannot figure it out. The sort function orders the edges of the graph as follows: Given two edges as E1(Vstart,Vend), E2(Vstart,Vend)
x.E1.Vstart<x.E2.Vstart or
x.E1.Vstart==x.E2.Vstart and y.E1.Vstart<y.E2.Vstart or
x.E1.Vstart==x.E2.Vstart and y.E1.Vstart==y.E2.Vstart and slope(E1)<slope(E2)
I thought this sort function is good for monoticity and other cases but apparently it is working only for some cases when besides the regular intersections it detects some other intersections also; for some cases it does work at all in that it does not computes all the intersections but just some point from the graph.
thank you in advance, madalina