sbw@naucse.UUCP (03/03/87)
The November 1983 Issue of CACM has a nice polygon clipping
algorithm by Liang-Barsky, including Pascal code for the
algorithm.
However, when I tried out the algorithm, I found a number of
cases where it did not work correctly. I have checked fairly
carefully and am reasonably certain that what I entered is
what is in the article, and have managed to convince myself
that some of the analysis on vertical and horizontal lines
is incorrect (this is, no doubt, a move of desparation on
my part).
Anyway, my qeustions:
(1) Does the algorithm as given in that CACM issue work?
For example, does it successfully clip the following
polygon correctly to a window bounded by (0,0),(1,1):
(-2,-2)->(-2,2)->(2,2)->(2,-2) ?
It should simply return the edges of the window.
When I try it, it produces mystical results, apparently
because the analysis does not take into account the
fact that the direction of outside vertical (and
horizontal) edges affects the turning points.
(2) If not, then was there a published fix to it?
(3) If so, then can someone point me to it or provide it
to me?
(4) Are there more efficient algorithms about these days
than the Liang-Barsky algorithm?
(5) See (3) above.
(6) Is the answer to (1) above is 'yes', then please let
me know, so I can scrutinize my code for the umpteenth+1
time.
I realize 1983 is a long time ago, but it was only recently
that I was pointed towards this article.
Please Email me the results, as I doubt that there is much
specific interest on the net about this.
Thanks!
Steve Wampler
{.....!arizona!naucse!sbw}wtm@utah-gr.UUCP (W. Thomas McCollough Jr.) (03/05/87)
A friend who implemented the algorithm in 1984 noted exactly the same failing.
He gave me the impression that the authors knew of the problem.
--
Tom McCollough
{ihnp4,decvax}!utah-cs!wtm, wtm@cs.utah.edumccoy%mccoy@Sun.COM (Daniel McCoy) (03/06/87)
In article <252@naucse.UUCP> sbw@naucse.UUCP (Steve Wampler) writes: >The November 1983 Issue of CACM has a nice polygon clipping >algorithm by Liang-Barsky, including Pascal code for the >algorithm. > >However, when I tried out the algorithm, I found a number of >cases where it did not work correctly. [...] > (1) Does the algorithm as given in that CACM issue work? [...] > (2) If not, then was there a published fix to it? > (3) If so, then can someone point me to it or provide it > to me? Make sure to check the Corrigendum in the April 1984 CACM. There was also one in Feb '84, but the April one was cumulative Among other things, two lines of the Pascal were changed. The changes are short, so, from CACM, April '84, changes to be made to the article in CACM Nov '83: Page 875: Figure 20, Line 7 shoud read if (deltax > 0) or (deltax = 0 and x[i] > xright) Page 875: Figure 20, Line 16 shoud read if (deltay > 0) or (deltay = 0 and y[i] > ytop) >Please Email me the results, as I doubt that there is much >specific interest on the net about this. > Since somebody else has already posted more speculation, I thought it might be worth a posting to help straighten things out. Dan McCoy mccoy@sun.COM Sun Microsystems
chapman@fornax.uucp (John Chapman) (03/10/87)
> In article <252@naucse.UUCP> sbw@naucse.UUCP (Steve Wampler) writes: > >The November 1983 Issue of CACM has a nice polygon clipping > >algorithm by Liang-Barsky, including Pascal code for the > >algorithm. > > > >However, when I tried out the algorithm, I found a number of > >cases where it did not work correctly. > [...] > > (1) Does the algorithm as given in that CACM issue work? > [...] > > (2) If not, then was there a published fix to it? > > (3) If so, then can someone point me to it or provide it > > to me? > > Make sure to check the Corrigendum in the April 1984 CACM. > There was also one in Feb '84, but the April one was cumulative In 1984 I implemented the corrected algorithm and it seemed to work in all cases. The only thing which gave me pause was that while I implemented the alg. on the same hardware and language as in the article (and the same data) my timing results differed from the published ones by an order of magnitude.