Vadim wrote:
With the right choice of predicates points using floating data types will be supported too.
Andrii wrote:
Not sure, what you mean by "predicates points". Could you explain with an example?
I think he means he wants to supply his own point comparison and circle event comparison predicates rather than use the library provided ones because he thinks he can just use the epsilon method with floating point coordinates. I don't think that is a good idea.
Is it practical to use floating point coordinates with an epsilon method and have non-robust algorithm when you could snap to integer coordinates with rounding error less than your epsilon and get a robust algorithm with no significant runtime overhead?
Yes, this is correct clarification. The simplest point predicate is just lexicographical compare using x and y coordinates of two points. In theory, without tolerance points are infinitely small and lines are infinitely thin. Tolerance parameter makes points and lines "thick". Such point predicates can be made problem specific. They work well both for integral and floating data types of coordinates. This is why I am suggesting to generalize your algorithm if this is not too costly. The question concerning search and update operations can be reduced to the following: Does this VD support incremental insertion of a new cell? if yes, what is the computational cost? If no, does insertion of new cell require re-building the whole VD? Regards, Vadim Stadnik