limonce@pilot.njin.net (Tom Limoncelli +1 201 408 5389) (04/18/91)
[Followups to comp.graphics. I don't read that, but it's the most appropriate.] A while back people requested that I post or email information on an article I had found about a clipping algorithm that completes in linear time. I finally found it. It turns out that the algorithm is O(Cx) (i.e. linear) but the constant C is quite large. It's worth a read considering that it does mean that there is hope for other (linear) algorithms that could take it down smaller. Some people seemed to be a little confused about the subject of the article, as far as I know it's a 2D algorithm but it *can* be generalized for 3D. I don't know if someone has already converted it to 3D yet. Here's the information: KY Fung, TM Nicholl, RE Tarjan, CJ Van Wyk, Simplified Linear-time Jordan Sorting and Polygon Clipping Information Processing Letters 35 (1990), pp. 85-92. The issue date is June 29. Enjoy! -- Tom Limoncelli tlimonce@drew.edu tlimonce@drew.bitnet 201-408-5389 Three witches making a potion. One asks, "A Liza Minnelli record, light beer, poppers, Frye boots; what's this spell for anyway?"