# Quicksort with Trivalued Logic

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)?

-
– joriki Mar 19 '11 at 13:27
BTW, what you call "associativity" is usually called "transitivity". – joriki Mar 19 '11 at 13:41
If your polygons are convex, you can probably use a sweep algorithm. You can move your reference frame pretty simply, there are camera formulas for that, and then sort your polygons by biggest and smallest z-value, and sweep far to near. Just keep track of the set of elements you can see at each time, and that should be enough. en.wikipedia.org/wiki/Sweep_line_algorithm – leif Mar 19 '11 at 17:22
@joriki - well spotted on the transitivity, thanks. I've edited to fix that. Topological sorting definitely looks interesting. – Simon Robinson Mar 19 '11 at 17:48
@leif - unfortunately my polygons are not guaranteed to be convex. – Simon Robinson Mar 19 '11 at 17:51