Letters to the Editor

Readers sound off.
Shopping for Linux

Cory Plock wonders why he can't find Linux distributions on the shelves of local software stores (LJ February 1997). Perhaps he's just living in a technologically repressed area. I just checked my nearest shopping-mall computer store here in Quebec City: They have the 6-CD InfoMagic package and the 4-CD Walnut Creek distribution, both up to date and competitively priced. A nearby store has several copies of two books on Linux. The distribution mechanisms must exist—encourage local dealers to use them. —Don Galbraith dsg@clic.net

On-line Linux Users Group

Hi. I have been a long time reader of LJ and it has been a great help to me, and I am sure that applies to many in the Linux community. Now, my friends on the Net and I have also done something as a contribution to Linux which I thought would be interesting to you and helpful to your readers. This is to create an On-Line Linux Users Group for people interested in learning more about Linux, providing help to other Linuxers and promoting Linux. Our web address is: http://www.linuxware.com/. —Peter Lazecky peteri@linuxware.com

AutoMount Article Comment

I am using the version of amd that comes with Red Hat 4.0. The NFS hosts are running SunOS 4.1.4 and Solaris. I found the suggestion that amd is relatively bug free incorrect. In the first few days of using it I found two important bugs. The first is that it confused the node name of one machine with the IP address of another machine. That is, I found directories from one machine under the name of the other in the /net directory. The second bug I have experienced several times. If a directory is unmounted, amd doesn't seem to know how to mount it for several minutes afterwards. Both of these bugs result in directories disappearing—including my home directory. It can make it very hard to justify using Linux when these major type problems exist.

As you can see, this is a big issue for me. I have seen several postings in dejanews referring to other problems with amd. I would like to see more support, but up to this point I have found very little in the way of answers to most questions about amd. Thanks for the article anyway. —David Uhrenholdt duhrenho@vette.sanders.com

Larry Wall Article Comment

I read Larry Wall's article on Perl on the way in to work today. My work involves C, Korn shell and Perl. I am convinced that Perl is a marvelous language. Mr. Wall's article supports that.

I understand the notion of creativity as a function of a large palette (...there's more than one way....) and the theory that “form follows function”. My conclusion is that Perl is unacceptable as a development tool because I cannot support it. It takes too long to discover (glean, figure out, guess at, puzzle out) which of the myriad possible methods was used by the original developer—even when that was me. I will continue to write Perl for fun and use more documentable, supportable languages for important systems.

I also wonder if Mr. Wall's writing would be a little more effective if he didn't attempt to be funny in every paragraph. He is the linguistic equivalent of the aggressive graphics that prevent many people from being able to read that very trendy San Francisco- based magazine on pop-wired culture. —Brandon Sussman #VATAcc70713@vantage.fmr.com

Another Algorithm for Polygons

5 Feb 1997: I enjoyed the interesting article by Bob Stein on algorithms for deciding whether a point is in a polygon in your March issue (“A Point about Polygons”). It is too bad that Bob wasn't familiar with the algorithm used for this in the WN web server (see http://hopf.math.nwu.edu/), as it has some interesting similarities and differences when compared to the algorithm he describes. Like Stein's it uses integer (actually long int) arithmetic rather than floating point.

I first used this algorithm in a version of WN released in July of 1995. As with Stein's algorithm we start by translating, so the test point is at the origin. Instead of counting the parity (evenness or oddness) of the number of crossings with the positive Y-axis, the actual signed number of crossings is counted (I used the positive X-axis instead of the Y-axis, but that is immaterial). More precisely, the algorithm counts +2 if an edge crosses the positive X-axis with positive slope and -2 if it crosses with negative slope. If an edge ends on the positive X-axis, it gets a count of only +1 or -1 depending on the slope. If the edge lies entirely in the positive X-axis, it gets a count of 0. If the origin (test point) is actually on any edge, we declare that the point is in the polygon and quit. After all edges have been counted, we declare that the test point is outside the polygon only if the total count is zero.

The implementation in WN is about three times as long as Stein's implementation, largely because I wanted to get all the special cases right even if in practice they don't matter much. In particular, if the test point is on an edge, it is always declared in the polygon. Also polygons with only two sides or degenerate polygons (like points) work properly.

There is one very big difference in the way the two algorithms behave when the polygon is not simple (i.e. crosses itself). Imagine a five-pointed star drawn in the usual way without lifting your pencil from the paper. With the even/odd count only points in the five triangular “tips” of the star will be considered inside while points in the pentagonal central region will be considered outside. The WN algorithm, on the other hand, will count all these points, tips and center, as “inside”. This is, in fact, the reason I chose this method rather than the even/odd count.

The reason this difference occurs is not too difficult to understand. Imagine the polygon is a stretched rubber band held in place on a table with thumb tacks at each vertex. At the test point we erect a vertical post perpendicular to the table. Now remove all the tacks and let the rubber band contract into the post. It may wrap around the post some number of times positively or negatively (i.e., counter-clockwise or clockwise) or it may not be hooked on the post at all. The even/odd algorithm is counting whether the number of times it wraps around is even or odd, while the WN algorithm is counting the full number.

If the polygon does not cross itself the actual number can only be 0, +1, or -1, so the even/odd algorithm works fine. With the five-pointed star, if the post is put in the central region, the rubber band goes around twice, and so the algorithms give different answers.

If anyone is interested in the WN implementation, just download the distribution and in the file wn/image.c look for the functions dopoly() and segment(). The distribution can be found at http://hopf.math.nwu.edu/. —John Franks john@math.nwu.edu