Menu

Problem with Plane sweep algorithm and its solution.

I wanted to you use plane sweep algorithm (originally from Bentley and Ottmann), but there is one reason why I can not.
This algorithm need exact computation. I have exact computation for sign of determinant, but only for double input and I would need exact (rational) input. Why? Because of on every event point I need update status and for this I need orientation test. It is not problem, if this point is end point of edge(s) - is represented in double. But problem occurs, if point is intersection (computed) point. This point can be approximation of real point. Because line intersection can robustly decide intersection but construction of this point is only approximation - using homogenous coordinates. Then orientation test for this intersection point can failed and order of edges in status is bad! I try modification (current implementation of plane sweep in repository), but I finished with same conclusion, need orientation test for exact input. I can change kernel to handle exact input.
At this time, I implemented edge intersector naively, compare each edge with each other in O(n^2), but robustly (lineIntersector do robust decisions).
And I implemented simple snap rounder using Hobby's hot points where each graph's edge is compared witch each hot point's boundary edges in O(n^2).
These two components are contained in noder, witch do noding of graph. In this case slowly, but robustly.

Posted by Ondrej Polach 2012-03-30

Log in to post a comment.

Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.