Hi Thomas, Sorry for the late response.
Hi Fernando,
The clear position of Lucanus Simonson with respect to the "allowed" output of a line segments intersection algorithm and your reactions to his position makes me wonder which output you consider "allowed".
The figures 1a), 1b), 2) and 3b) of John Hobby's publication http://cutebugs.net/files/curve/2-27.ps clearly illustrate the discussed issue.
3b) would be a reasonable result. 1b) could also depending on the application: in rendering for example it could be totally acceptable.
I considered 2) as non-acceptable output and Lucanus Simonson considered 1b) as non-acceptable. (The output 3b) seems to be the most attractive one for this example.) Your position that geometric algorithms should use exactly evaluated "predicates" called explicitly on the input (and never ever on an intermediate result) to drive the topological construction doesn't seem to settle this question.
Put like that, no it doesn't :) But notice that I carefully said "unless you really have to use intermediate results, and if you do, use them very very carefully"
Why not? Because the output 1b) would not be allowed as input to your algorithm, it's hard to see why you should allow it as output from your algorithm. The output 2) and 3b) on the other hand clearly fall into the category "modification of input" (because a straight segment was replaced by a bent segment), which you explicit call "hacking". And it clearly is hacking in the sense that it doesn't generalize to other problems (like the straight skeleton for example). I somehow got the impression that 1b) is indeed the output that you consider "allowable", but I would like you to confirm or correct this impression.
Yes, (1b) could be considered allowed as well, depending on what you need to do with the result. These questions are excelent to put what I've said before in a much better persective: What I outlined are general guidelines for all types of geometric computation problems. As such, it has particular cases where something case-specific must be done, as in this case. OTOH the very fact that the guidelines don't directly apply calls for reconsidering the inmediate solution a bit further. In the case of booleans, for instance, one could notice the following: Let's label the points in the figures, in topological order, for the sake of discussion: P, Q, R, S such that the segments are PQ, QR, RS and segments PQ and RS intersect at point I Given exact predicates operating exclusively in the input, it is possible to know that segments PQ and RS intersect at I, but there is no other intersection, specially NOT with QR. That indicates that all the problems stated in the cited paper comes from approximating the intersection point embeeding it into a finite space, which is a problem that can be considered separated from the boolean operation algorithm (which a researcher could express in tems of a RealRAM). Therefore, a boolean operations algorithm could be designed in a such a way that it just doesn't attempt to ouput ANY approximation for intersections points at all. Instead, it could merely return the Planar Directed Graph (PDG) that corresponds to the result, with all intersection points given "expressively": i.e. using a representation that actually stores the four points that define the two intersecting segments. Such an algorithm would have the luxury of totally ignoring the potential side effect of introducing "unreported intersections" as you call it. It is extremely useful to be able to implement a geometric algorithm with such a freedom. Then a second, separate and composable "embeeding" algorithm could take on the job of approximating intersection points fullfilling certain output requirements. Given a DAG, such an algorithm can produce (3b) since it can know using the exact predicates that point I is to one side of segment QR but the best approximation it can generate is (as reported by the predicate but this time called on the potential result) to the other side, so it MUST modify the idealized result splitting and snapping QR. Granted, this is using the predicate with an intermediate result, but in a place specifically designed to carefully consider the effect of rounding and with the "ideally correct" result already in hand (the DAG). Notice how the general exact computation paradigm lead us to decompose an algorithm into concerns that could not have been obviously separated. As a consequence, one can now consider the possibility of providing a toolbox of distinct "embeeding" steps that, for instance produce (1b), which could be more than acceptable, for example, for rendering. Users would choosen the one they need. Even more, the entire geometric computing framework could follow a similar design by pushing the actual computation of intermediate results as far ahead as possible. That is, there could be several algorithms taking the DAG produced by the "error-free" boolean operation and go from there. Only in the very end of the processing pipeline the results would have to be embeeded, but now in a context where approximation erros have little, if any, impact. Best -- Fernando Cacciola SciSoft Consulting, Founder http://www.scisoft-consulting.com