Written for readers with at least some Perl programming experience, Mastering Algorithms in Perl delivers a solid library of algorithms written in Perl for business and mathematical computing. From data structures to cryptography and more advanced mathematical algorithms, this book provides a worthwhile guide to extending Perl’s coding capabilities.
The best thing about Master Algorithms in Perl is the scope with which it covers the universe of algorithms, while refraining from getting bogged down in academic detail. Besides providing basic data structures (a lynchpin of books on algorithms), the authors provide dozens of algorithms for sorting, searching and doing mathematical computation of all kinds. While they discuss “Big-O” notation and assume a general familiarity with math, they don’t overwhelm the reader. (You can even borrow the code here without a math degree to understand it.) The focus here is on efficient, re-usable Perl subroutines written and compiled by three Perl experts.
Standout chapters include extending Perl’s already powerful string processing abilities, game programming and cryptography. Generally, the authors achieve a good mix of advanced and less well-known algorithms, along with the basics. Chances are you won’t need to use all the dozen or so sorting algorithms presented here, but the authors include them all, just in case. As a reference and tutorial, readers can pick and choose what they need for real world Perl development.
There hasn’t been a book dedicated exclusively to Perl algorithms prior to the publication of this one. In all, Mastering Algorithms in Perl fills a useful niche by compiling a powerful library of Perl algorithms that will be useful for anyone who works with this programming language, whether in business or academic computing. – -Richard Dragan,Amazon.com
Topics covered: Perl data types, Big-O notation, data structures, queues, deques, linked lists, binary trees, sorting and searching algorithms, game and dynamic programming, sets and multisets, matrices, graphs, string matching and parsing, 2-D geometry, number systems, cryptography (including DES and RSA), probability, statistics and numerical analysis. –Amazon.com
About the Author
Jon Orwant is president of Readable Publications, Inc. He founded The Perl Journal in 1995 and served as the sole editor, publisher, accountant, designer, and postal antagonizer until 1999. He has been on the technical committee of all of O’Reilly’s Perl conferences (where he is the emcee of the Internet Quiz Show), and he speaks frequently about Perl, most recently at the first YAPC on Rebuilding Post-Apocalyptic Civilization with Perl. He is currently an MIT Media Laboratory IBM Fellow, creating programs that create programs that play games. His other research interests are user modeling and electronic publishing. He gives frequent talks about Media Lab research, most recently on the promise and perils of Internet gambling. In 1993, he created the world’s first Internet stock-picking game. His Markov-model based Rock-Paper-Scissors program has been undefeated since 1997. He also performs professional voice-overs. A court injunction from the Commonwealth of Massachusetts prohibits him from cooking or otherwise assisting in the preparation of any foodstuff meant for human consumption. Jarkko Hietaniemi is the creator and Master Librarian of CPAN: Comprehensive Perl Archive Network. He has also been known to frequent Perl developer forums. Luckily enough, getting his MSc in CS in the field of parallel computing didn’t interfere overly much with his Perl and UNIX hacking. During those savored moments of off-line time, he fancies gobbling up speculative fiction and popular science. His real life employer is Nokia Research Center. John Macdonald has been using Perl commercially since 1988 for a suite of Unix system administration tools. His background with Unix dates back to the days when Unix was written in PDP-11 assembler and later includes representing the University of Waterloo at the first UNIX Users Meeting at City University of New York in the mid-1970s while finishing his M. Math degree. (In those days before the creation of Usenix, the people at the meeting would sit together around a single table.) In addition, his background includes work on compilers, kernel internals, device drivers and the like. He has also been observed partaking in recreational computing activities.
Excerpt. © Reprinted by permission. All rights reserved.
Chapter 10 Geometric Algorithms
Do not disturb my circles!
Archimedes (287 212 B.C.E.)
Geometry needs no introduction. This most visual branch of mathematics is used whenever you see pictures on your computer screen, and in this chapter we ll explore algorithms useful for tasks such as these:
Web image maps
How can you tell whether the mouse click fell within an oddly shaped area? See the section “Inclusion.”
Arranging windows
How do you open up new windows so that they obscure existing windows as little as possible? See the section “Boundaries.”
Cartography
You have a set of scattered points (say, fenceposts) and want to draw the region that they define. See the section “Boundaries.”
Simulations
Which pair of 10,000 points are closest to each other and therefore in danger of colliding? See the section “Closest Pair of Points.”
In this chapter, we explore geometric formulas and algorithms. We can only provide building blocks for you to improve upon; as usual, we can t anticipate every use you ll have for these techniques. We ll restrict ourselves to two dimensions in almost all of the code we show. We don t cover the advanced topics you ll find in a book devoted solely to computer graphics, such as ray tracing, radiosity, lighting, animation, or texture mapping, although we do cover splines in the section “Splines” in Chapter 16, Numerical Analysis. For deeper coverage of these topics, we recommend Computer Graphics: Principles and Practice, by Foley, van Dam, Feiner, and Hughes, and the Graphics Gems books. Those of a more practical persuasion will find information about windowing toolkits, business graphs, OpenGL (a 3-D graphics language) and VRML (Virtual Reality Markup Language) at the end of the chapter.
For simplicity, almost all the subroutines in this chapter accept coordinates as flat lists of numbers. To interface with your existing programs, you might want to rewrite them so that you can pass in your points, lines, and polygons as array or hash references. If you have a lot of them, this will be faster as well. See the section “References” in Chapter 1, Introduction, for more information.
One last caveat: Many geometric problems have nasty special cases that require special attention. For example, many algorithms don t work for concave objects, in which case you ll need to chop them into convex pieces before applying the algorithms. Complicated objects like people, trees, and class F/X intergalactic dreadnoughts fighting huge tentacled monsters from Orion s Belt are frequently represented as polygons (typically triangles, or tetrahedrons for three dimensions), and collisions with them are checked using bounding boxes convex hulls. More about these later in the chapter.
Wow! eBook
