Does anyone know a way to do a quick sort with trivalued logic?
The problem I’m trying to solve is this: I’m trying to display a view of a complex 3d object from a given viewing angle. I’ve broken the object into many 2d surfaces that I can draw separately, but to display the image properly, I need to determine the z-order of the surfaces – a classic computer drawing problem. It’s guaranteed that none of the surfaces intersect, so the problem is solvable. It would be simple if on comparing any two surfaces, I could always determine which one is in front – then a simple mergesort would suffice. But very often, if I compare two surfaces, it’ll turn out that, with the angle I’m viewing from, there’s no overlap at all. One surface is over here, and the other surface is over there, so it’s impossible to say which one is in front.
In mathematical terms, what I’m trying to do is sort a set of entities - call them a, b, c, etc. Transitivity is guaranteed: If a < b is true and b< c is true then a < c is always true. But the complicating factor is the trivalued logic: a < b could be unknown. A consequence is the final sorted list may contain small sets of elements within which the order doesn’t matter, eg. The result may be a < (b, c) < d etc.
Note that even if a < b is unknown, other comparisons may indirectly force a certain ordering for a, b. Eg. If a < b is unknown, but it turns out that a < c = true and b < c is false, then the sorted order must be a < c < b.
I can solve the problem with a bubble sort, but that’s bad because O(N^2) comparisons, and each comparison is very expensive (since it involves figuring out whether two surfaces can block each other when viewed from a certain angle). Is there a way to solve this with a faster sort? (eg. Some adaptation of a mergesort)?