Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
2  
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
show 2 more comments

2 Answers 2

up vote 2 down vote accepted

What you have is not really a trivalued logic, but a partially ordered set (aka poset). There is a fairly large body of research on sorting partially ordered sets (a quick googling for "poset sorting" gives some good hits). In particular, you may want to look for something called a "chain merge data structure". Also, a paper called "Sorting and Selection in Posets".

share|improve this answer
    
Thanks aubrey, I found the paper you meant, at link, and it does exactly answer my question, although it looks like the answer is so complex that I may just stick with a simple variant of bubble sort for now. Googling for poset also, interestingly, gave me this question on stack overflow: link which asked the exact same question I asked, except that in that case the questioner knew the correct terminology so could make his question much shorter :) –  Simon Robinson Mar 20 '11 at 12:51
add comment

Though your surfaces are sometimes incomparable (this is the third value in you hoped for trivalent logic), I think it is not necessary to worry about it here. If for two surfaces, neither is in front of the other for the given viewpoint, then you can draw either one before the other, it doesn't matter. So when you sort your surfaces you can just arbitrarily pick one (or the other) to be drawn before the other and it won't mess up the drawing.

share|improve this answer
1  
I think you may have misunderstood the question. The OP mentioned that the order doesn't matter for some elements, but the problem is that the order of two surfaces may be fixed through some intermediate surfaces even if the two surfaces themselves aren't directly comparable, so you can't just use standard sorting and return an arbitrary result in that case. –  joriki Mar 19 '11 at 23:13
1  
Yep, joriki is correct. As an example, imagine you have two glasses on a table, one on the left and one on the right. No overlap, so you can draw them in either order. Now place a spoon diagonally so it lies in front of the left glass but behind the right one. Now the spoon blocks the left glass, and right glass blocks the spoon - that forces the drawing order to be left glass - spoon - right glass. (That example doesn't quite match what I'm doing as a glass is a 3d object in its own right, not a surface, but mathematically it's exactly the same sorting problem. –  Simon Robinson Mar 19 '11 at 23:29
    
@joriki: Argh...yes. Then when you can't compare everything directly (the comparison relation is not total), then yes, use 'topological sort' on the poset of comparisons that you do have. –  Mitch Mar 20 '11 at 15:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.