aramini@apollo.COM (Michael Aramini) (03/15/89)
I thought about the problem of degenerate cell disambiguation
some more. I came up with an equivalent, but much simpler
to compute, way of disambiguating degenerate cells:
IF y[left] < y[right] THEN BEGIN
Connect left and bottom intersection points;
Connect right and top intersection points;
END
ELSE IF y[left] = y[right] THEN BEGIN
Connect left and right intersection points;
Connect top and bottom intersection points;
ELSE BEGIN (* y[left] > y[right] *)
Connect left and top intersection points;
Connect right and bottom intersection points;
END;
To intuitively see why this works, consider that the following can be shown
algebraicly:
y[left] < y[right] if and only if x[bottom] < x[top]
y[left] = y[right] if and only if x[bottom] = x[top]
y[left] > y[right] if and only if x[bottom] > x[top]
In light of that, there are only six possible cases to consider, as represented
by the following diagrams:
+++0----- ++++0---- +++++0--- ---0+++++ ----0++++ -----0+++
+ / - + | - + \ - - / + - | + - \ +
+/ - + | - + \- -/ + - | + - \+
0 - + | - + 0 0 + - | + - 0
- - - 0___0___0 + + + + + + 0___0___0 - - -
- 0 - | + 0 + + 0 + | - 0 -
- /+ - | + -\ + + /- + | - +\ -
- / + - | + - \ + + / - + | - + \ -
-----0+++ ----0++++ ---0+++++ +++++0--- ++++0---- +++0-----
where
+ means f(x,y) > h
0 means f(x,y) = h
- means f(x,y) < =
/,\,|,_ mean line segments to be plotted
Too bad I didn't think of this simplification 8 years ago when I wrote my master's
thesis.
-Michael Aramini
(aramini@apollo.com)