国外基础几何算法答与问（算法）

　　http://www.faqs.org/faqs/graphics/algorithms-faq/（转（））

　　From: orourke@cs.smith.edu (Joseph O'Rourke)

　　Newsgroups: comp.graphics.algorithms

　　Subject: comp.graphics.algorithms Frequently Asked Questions

　　Date: Sat, 15 Feb 2003 16:16:44 +0000 (UTC)

　　Sender: orourke@grendel.csc.smith.edu

　　Message-ID: <graphics/algorithms-faq-1-1045325804@cs.smith.edu>

　　Reply-To: orourke@cs.smith.edu (Joseph O'Rourke)

　　Keywords: faq computer graphics algorithms geometry

　　X-Content-Currency: This FAQ changes regularly. See item (0.03) for instructions

　　on how to obtain a new copy via FTP.

　　Posted-By: auto-faq 3.3.1 beta (Perl 5.006)

　　Archive-name: graphics/algorithms-faq

　　Posting-Frequency: bi-weekly

　　Welcome to the FAQ for comp.graphics.algorithms!

　　Thanks to all who have contributed. Corrections and contributions

　　(to orourke@cs.smith.edu) always welcome.

　　----------------------------------------------------------------------

　　This article is Copyright 2003 by Joseph O'Rourke. It may be freely

　　redistributed in its entirety provided that this copyright notice is

　　not removed.

　　----------------------------------------------------------------------

　　Changed items this posting (|): 5.04

　　New items this posting (+): none

　　----------------------------------------------------------------------

　　History of Changes (approx. last six months):

　　----------------------------------------------------------------------

　　Changes in 15 Feb 03 posting:

　　5.04: Fixed broken link in clipping article. [Thanks to Keith Forbes.]

　　Changes in 1 Feb 03 posting:

　　0.04: Ashdown Radiosity back in print. [Thanks to Ian Ashdown.]

　　0.06: Update BSP FAQ links [Thanks to Ken Shoemake.]

　　0.07: Update CGAL links in source article.

　　3.11: Broken link re course based on Perlin's Noise book. [Thanks to Mikkel Gjoel.]

　　6.01: Add CGAL link to Voronoi source article. [Thanks to Andreas Fabri.]

　　7.02: All contributor email addresses removed to protect them from spam.

　　Changes in 15 Jan 03 posting:

　　0.06: Query re reality.sgi.com/bspfaq/ [Thanks to <warp@subphase.de

　　>.]

　　0.07: Update moved link on WINGED.ZIP. [Thanks to Ben Landon.]

　　0.07: Update Ferrar's ++ 3D rendering library link. [Thanks to F.Iannarilli, Jr.]

　　1.06: Added ref to AT&T Graphviz. [Thanks to Michael Meire.]

　　2.08: Fix sloan ear-clipping link. [Thanks to logicalink@juno.com.]

　　5.09: Update moved link re caustics. [Thanks to Ben Landon.]

　　5.18: Formula for distance between two 3D lines. [Thanks to Daniel Zwick.]

　　5.27: New article on transforming normals by Ken Shoemake.

　　6.08: Random points on sphere in terms of longitude & latitude [Thanks to Uffe Kousgaard.]

　　Changes in 1 Jul 02 posting:

　　3.14: Correct GIF author info, add URL. [Thanks to Greg Roelofs.]

　　Changes in 1 May 02 posting:

　　0.04: Errata for Watt & Watt book added. [Thanks to Jacob Marner.]

　　5.14: 3D viewing revised by Ken Shoemake.

　　5.23: Remove (erroneous) 3D medial axis info.

　　5.25: New article on quaternions by Ken Shoemake.

　　5.26: New article on camera aiming and quaternions by Ken Shoemake.

　　6.01: Add (correct) 3D medial axis info. (Thanks to Tamal Dey.)

　　6.09: Plucker coordinates article revised by Ken Shoemake.

　　Changes in 15 Apr 02 posting:

　　3.05: Scaling bitmaps revised by Ken Shoemake.

　　3.09: Morphing article written by Ken Shoemake.

　　6.08: Added references on random points on a sphere (Ken Shoemake).

　　Changes in 1 Apr 02 posting:

　　1.01: 2D point rotation revised by Ken Shoemake.

　　1.01: 2D segment intersection revised by Ken Shoemake.

　　5.01: 3D point rotation revised by Ken Shoemake.

　　0.07: Greg Ferrar's 3D rendering library no longer available.

　　Changes in 15 Mar 02 posting:

　　2.03: Reference Dan Sunday's winding number algorithm.

　　4.04: More detail on Beziers approximating a circle.

　　(Thanks to William Gibbons.)

　　5.22: Added NASA's "Intersect" code for intersecting triangulated

　　surfaces.

　　5.23: Updated Cocone software description.

　　Changes in 15 Feb 02 posting:

　　5.03: Noted that Sutherland-Hodgman can clip against any convex polygon.

　　(Thanks to Ben Landon.)

　　5.15: More links on simplifying meshes. (Thanks to Stefan Krause.)

　　Changes in 1 Jan 02 posting:

　　2.03: Fixed link to Franklin's code. (Thanks to Keith M. Briggs.)

　　5.13: Update to SWIFT++; add Terdiman's collision lib.

　　(Thanks to Pierre Terdiman.)

　　Changes in 1 Nov 01 posting:

　　6.01,02,03: Update to Qhull 3.1 release (Thanks to Brad Barber.)

　　Changes in 15 Sep 01 posting:

　　0.04: "Radiosity: A Programmer's Perspective" out of print.

　　0.05: CQUANT97 link no longer available; RADBIB info updated.

　　(Thanks to Ian Ashdown for both.)

　　2.01: Explained indices in more efficient formula, and restored

　　Sunday's version. (Thanks to Dan Sunday.)

　　4.04: Link for approximating a circle via a Bezier curve

　　(Thanks to John McDonald, Jr.)

　　5.10: Add in link to Jules Bloomenthal's list of papers for algorithms

　　that could substitute for the marching cubes algorithm.

　　5.11: Refer to 5.10. (Thanks to Eric Haines for both.)

　　Changes in 1 Sep 01 posting:

　　2.01: Fixed indices in efficient area formula

　　(Thanks to peter@Glaze.phys.dal.ca.)

　　2.03: Link to classic "Point in Polygon Strategies" article.

　　(Thanks to Eric Haines.)

　　5.09: Additional references for caustics (Thanks to Lars Brinkhoff.)

　　5.11: New links for marching cubes patent (Thanks to John Stone.)

　　5.17: Stale link notice.

　　5.23: New Cocone link for surface reconstruction.

　　----------------------------------------------------------------------

　　Table of Contents

　　----------------------------------------------------------------------

　　0. General Information

　　0.01: Charter of comp.graphics.algorithms

　　0.02: Are the postings to comp.graphics.algorithms archived?

　　0.03: How can I get this FAQ?

　　0.04: What are some must-have books on graphics algorithms?

　　0.05: Are there any online references?

　　0.06: Are there other graphics related FAQs?

　　0.07: Where is all the source?

　　1. 2D Computations: Points, Segments, Circles, Etc.

　　1.01: How do I rotate a 2D point?

　　1.02: How do I find the distance from a point to a line?

　　1.03: How do I find intersections of 2 2D line segments?

　　1.04: How do I generate a circle through three points?

　　1.05: How can the smallest circle enclosing a set of points be found?

　　1.06: Where can I find graph layout algorithms?

　　2. 2D Polygon Computations

　　2.01: How do I find the area of a polygon?

　　2.02: How can the centroid of a polygon be computed?

　　2.03: How do I find if a point lies within a polygon?

　　2.04: How do I find the intersection of two convex polygons?

　　2.05: How do I do a hidden surface test (backface culling) with 2D points?

　　2.06: How do I find a single point inside a simple polygon?

　　2.07: How do I find the orientation of a simple polygon?

　　2.08: How can I triangulate a simple polygon?

　　2.09: How can I find the minimum area rectangle enclosing a set of points?

　　3. 2D Image/Pixel Computations

　　3.01: How do I rotate a bitmap?

　　3.02: How do I display a 24 bit image in 8 bits?

　　3.03: How do I fill the area of an arbitrary shape?

　　3.04: How do I find the 'edges' in a bitmap?

　　3.05: How do I enlarge/sharpen/fuzz a bitmap?

　　3.06: How do I map a texture on to a shape?

　　3.07: How do I detect a 'corner' in a collection of points?

　　3.08: Where do I get source to display (raster font format)?

　　3.09: What is morphing/how is it done?

　　3.10: How do I quickly draw a filled triangle?

　　3.11: D Noise functions and turbulence in Solid texturing.

　　3.12: How do I generate realistic sythetic textures?

　　3.13: How do I convert between color models (RGB, HLS, CMYK, CIE etc)?

　　3.14: How is "GIF" pronounced?

　　4. Curve Computations

　　4.01: How do I generate a Bezier curve that is parallel to another Bezier?

　　4.02: How do I split a Bezier at a specific value for t?

　　4.03: How do I find a t value at a specific point on a Bezier?

　　4.04: How do I fit a Bezier curve to a circle?

　　5. 3D computations

　　5.01: How do I rotate a 3D point?

　　5.02: What is ARCBALL and where is the source?

　　5.03: How do I clip a polygon against a rectangle?

　　5.04: How do I clip a polygon against another polygon?

　　5.05: How do I find the intersection of a line and a plane?

　　5.06: How do I determine the intersection between a ray and a triangle?

　　5.07: How do I determine the intersection between a ray and a sphere?

　　5.08: How do I find the intersection of a ray and a Bezier surface?

　　5.09: How do I ray trace caustics?

　　5.10: What is the marching cubes algorithm?

　　5.11: What is the status of the patent on the "marching cubes" algorithm?

　　5.12: How do I do a hidden surface test (backface culling) with 3D points?

　　5.13: Where can I find algorithms for 3D collision detection?

　　5.14: How do I perform basic viewing in 3D?

　　5.15: How do I optimize/simplify a 3D polygon mesh?

　　5.16: How can I perform volume rendering?

　　5.17: Where can I get the spline description of the famous teapot etc.?

　　5.18: How can the distance between two lines in space be computed?

　　5.19: How can I compute the volume of a polyhedron?

　　5.20: How can I decompose a polyhedron into convex pieces?

　　5.21: How can the circumsphere of a tetrahedron be computed?

　　5.22: How do I determine if two triangles in 3D intersect?

　　5.23: How can a 3D surface be reconstructed from a collection of points?

　　5.24: How can I find the smallest sphere enclosing a set of points in 3D?

　　5.25: What's the big deal with quaternions?

　　5.26: How can I aim a camera in a specific direction?

　　5.27: How can I transform normals?

　　6. Geometric Structures and Mathematics

　　6.01: Where can I get source for Voronoi/Delaunay triangulation?

　　6.02: Where do I get source for convex hull?

　　6.03: Where do I get source for halfspace intersection?

　　6.04: What are barycentric coordinates?

　　6.05: How do I generate a random point inside a triangle?

　　6.06: How do I evenly distribute N points on (tesselate) a sphere?

　　6.07: What are coordinates for the vertices of an icosohedron?

　　6.08: How do I generate random points on the surface of a sphere?

　　6.09: What are Plucker coordinates?

　　7. Contributors

　　7.01: How can you contribute to this FAQ?

　　7.02: Contributors. Who made this all possible.

　　Search e.g. for "Section 6" to find that section.

　　Search e.g. for "Subject 6.04" to find that item.

　　----------------------------------------------------------------------

　　Section 0. General Information

　　----------------------------------------------------------------------

　　Subject 0.01: Charter of comp.graphics.algorithms

　　comp.graphics.algorithms is an unmoderated newsgroup intended as a forum

　　for the discussion of the algorithms used in the process of generating

　　computer graphics. These algorithms may be recently proposed in

　　published journals or papers, old or previously known algorithms, or

　　hacks used incidental to the process of computer graphics. The scope of

　　these algorithms may range from an efficient way to multiply matrices,

　　all the way to a global illumination method incorporating raytracing,

　　radiosity, infinite spectrum modeling, and perhaps even mirrored balls

　　and lime jello.

　　It is hoped that this group will serve as a forum for programmers and

　　researchers to exchange ideas and ask questions on recent papers or

　　current research related to computer graphics.

　　comp.graphics.algorithms is not:

　　- for requests for gifs, or other pictures

　　- for requests for image translator or processing software; see

　　alt.binaries.pictures

　　* FAQ

　　alt.binaries.pictures.utilities [now degenerated to pic postings]

　　alt.graphics.pixutils (image format translation)

　　comp.sources.misc (image viewing source code)

　　sci.image.processing

　　comp.graphics.apps.softimage

　　fj.comp.image

　　- for requests for compression software; for these try:

　　alt.comp.compression

　　comp.compression

　　comp.compression.research

　　- specifically for game development; for this try:

　　comp.games.development.programming.misc

　　comp.games.development.programming.algorithms

　　----------------------------------------------------------------------

　　Subject 0.02: Are the postings to comp.graphics.algorithms archived?

　　Archives may be found at: http://www.faqs.org/

　　----------------------------------------------------------------------

　　Subject 0.03: How can I get this FAQ?

　　The FAQ is posted on the 1st and 15th of every month. The easiest

　　way to get it is to search back in your news reader for the most

　　recent posting, with Subject:

　　comp.graphics.algorithms Frequently Asked Questions

　　It is posted to comp.graphics.algorithms, and cross-posted to

　　news.answers and comp.answers.

　　If you can't find it on your newsreader,

　　you can look at a recent HTML version at the "official" FAQ archive site:

　　http://www.faqs.org/

　　The maintainer also keeps a copy of the raw ASCII, always the

　　latest version, accessible via http://cs.smith.edu/~orourke/FAQ.html .

　　Finally, you can ftp the FAQ from several sites, including:

　　ftp://rtfm.mit.edu/pub/faqs/graphics/algorithms-faq

　　ftp://mirror.seas.gwu.edu/pub/rtfm/comp/graphics/algorithms/

　　The (busy) rtfm.mit.edu site lists many alternative "mirror" sites.

　　Also can reach the FAQ from http://www.geom.umn.edu/software/cglist/

　　,

　　which is worth visiting in its own right.

　　----------------------------------------------------------------------

　　Subject 0.04: What are some must-have books on graphics algorithms?

　　The keywords in brackets are used to refer to the books in later

　　questions. They generally refer to the first author except where

　　it is necessary to resolve ambiguity or in the case of the Gems.

　　Basic computer graphics, rendering algorithms,

　　----------------------------------------------

　　[Foley]

　　Computer Graphics: Principles and Practice (2nd Ed.),

　　J.D. Foley, A. van Dam, S.K. Feiner, J.F. Hughes, Addison-Wesley

　　1990, ISBN 0-201-12110-7;

　　Computer Graphics: Principles and Practice, C version

　　J.D. Foley, A. van Dam, S.K. Feiner, J.F. Hughes, Addison-Wesley

　　ISBN: 0-201-84840-6, 1996, 1147 pp.

　　[Rogers:Procedural]

　　Procedural Elements for Computer Graphics, Second Edition

　　David F. Rogers, WCB/McGraw Hill 1998, ISBN 0-07-053548-5

　　[Rogers:Mathematical]

　　Mathematical Elements for Computer Graphics 2nd Ed.,

　　David F. Rogers and J. Alan Adams, McGraw Hill 1990, ISBN

　　0-07-053530-2

　　[Watt:3D]

　　_3D Computer Graphics, 2nd Edition_,

　　Alan Watt, Addison-Wesley 1993, ISBN 0-201-63186-5

　　[Glassner:RayTracing]

　　An Introduction to Ray Tracing,

　　Andrew Glassner (ed.), Academic Press 1989, ISBN 0-12-286160-4

　　[Gems I]

　　Graphics Gems,

　　Andrew Glassner (ed.), Academic Press 1990, ISBN 0-12-286165-5

　　http://www.graphicsgems.org/ for all the Gems.

　　[Gems II]

　　Graphics Gems II,

　　James Arvo (ed.), Academic Press 1991, ISBN 0-12-64480-0

　　[Gems III]

　　Graphics Gems III,

　　David Kirk (ed.), Academic Press 1992, ISBN 0-12-409670-0 (with

　　IBM disk) or 0-12-409671-9 (with Mac disk)

　　See also "AP Professional Graphics CD-ROM Library,"

　　Academic Press, ISBN 0-12-059756-X, which contains Gems I-III.

　　[Gems IV]

　　Graphics Gems IV,

　　Paul S. Heckbert (ed.), Academic Press 1994, ISBN 0-12-336155-9

　　(with IBM disk) or 0-12-336156-7 (with Mac disk)

　　[Gems V]

　　Graphic Gems V,

　　Alan W. Paeth (ed.), Academic Press 1995, ISBN 0-12-543455-3

　　(with IBM disk)

　　[Watt:Animation]

　　Advanced Animation and Rendering Techniques,

　　Alan Watt, Mark Watt, Addison-Wesley 1992, ISBN 0-201-54412-1

　　(Unofficial) errata: http://www.rolemaker.dk/other/AART/

　　[Bartels]

　　An Introduction to Splines for Use in Computer Graphics and

　　Geometric Modeling,

　　Richard H. Bartels, John C. Beatty, Brian A. Barsky, 1987, ISBN

　　0-934613-27-3

　　[Farin]

　　Curves and Surfaces for Computer Aided Geometric Design:

　　A Practical Guide, 4th Edition, Gerald E. Farin, Academic Press

　　1996. ISBN 0122490541.

　　[Prusinkiewicz]

　　The Algorithmic Beauty of Plants,

　　Przemyslaw W. Prusinkiewicz, Aristid Lindenmayer, Springer-Verlag,

　　1990, ISBN 0-387-97297-8, ISBN 3-540-97297-8

　　[Oliver]

　　Tricks of the Graphics Gurus,

　　Dick Oliver, et al. (2) 3.5 PC disks included, $39.95 SAMS Publishing

　　[Hearn]

　　Introduction to computer graphics,

　　Hearn & Baker

　　[Cohen]

　　Radiosity and Realistic Imange Sythesis,

　　Michael F. Cohen, John R. Wallace, Academic Press Professional

　　1993, ISBN 0-12-178270-0 [limited reprint 1999]

　　[Ashdown]

　　Radiosity: A Programmer's Perspective

　　Ian Ashdown, John Wiley & Sons 1994, ISBN 0-471-30444-1, 498 pp.

　　Back in print, Jan 2003. See www.helios32.com.

　　[sillion]

　　Radiosity & Global Illumination

　　Francois X. Sillion snd Claude Puech, Morgan Kaufmann 1994, ISBN

　　1-55860-277-1, 252 pp.

　　[Ebert]

　　Texturing and Modeling - A Procedural Approach (2nd Ed.)

　　David S. Ebert (ed.), F. Kenton Musgrave, Darwyn Peachey, Ken Perlin,

　　Steven Worley, Academic Press 1998, ISBN 0-12-228730-4, Includes CD-ROM.

　　[Schroeder]

　　Visualization Toolkit, 2nd Edition, The: An Object-Oriented Approach to

　　3-D Graphics (Bk/CD) (Professional Description)

　　William J. Schroeder, Kenneth Martin, and Bill Lorensen,

　　Prentice-Hall 1998, ISBN: 0-13-954694-4

　　See Subject 0.07 for source.

　　[Anderson]

　　PC Graphics Unleashed

　　Scott Anderson. SAMS Publishing, ISBN 0-672-30570-4

　　[Ammeraal]

　　Computer Graphics for Java Programmers,

　　Leen Ammeraal, John Wiley 1998, ISBN 0-471-98142-7.

　　Additional information at http://home.wxs.nl/~ammeraal/ .

　　[Eberly]

　　3D Game Engine Design: A Practical Approach to Real-Time Computer Graphics.

　　David Eberly, Morgan Kaufmann/Academic Press, 2001.

　　For image processing,

　　---------------------

　　[Barnsley]

　　Fractal Image Compression,

　　Michael F. Barnsley and Lyman P. Hurd, AK Peters, Ltd, 1993 ISBN

　　1-56881-000-8

　　[Jain]

　　Fundamentals of Image Processing,

　　Anil K. Jain, Prentice-Hall 1989, ISBN 0-13-336165-9

　　[Castleman]

　　Digital Image Processing,

　　Kenneth R. Castleman, Prentice-Hall 1996, ISBN(Cloth): 0-13-211467-4

　　(Description and errata at: "http://www.phoenix.net/~castlman")

　　[Pratt]

　　Digital Image Processing, Second Edition,

　　William K. Pratt, Wiley-Interscience 1991, ISBN 0-471-85766-1

　　[Gonzalez]

　　Digital Image Processing (3rd Ed.),

　　Rafael C. Gonzalez, Paul Wintz, Addison-Wesley 1992, ISBN

　　0-201-50803-6

　　[Russ]

　　The Image Processing Handbook (3rd Ed.),

　　John C. Russ, CRC Press and IEEE Press 1998, ISBN 0-8493-2532-3

　　[Russ & Russ]

　　The Image Processing Tool Kit v. 3.0

　　Chris Russ and John Russ, Reindeer Games Inc. 1999, ISBN 1-928808-00-X

　　[Wolberg]

　　Digital Image Warping,

　　George Wolberg, IEEE Computer Society Press Monograph 1990, ISBN

　　0-8186-8944-7

　　Computational geometry

　　----------------------

　　[Bowyer]

　　A Programmer's Geometry,

　　Adrian Bowyer, John Woodwark, Butterworths 1983,

　　ISBN 0-408-01242-0 Pbk

　　Out of print, but see:

　　Introduction to Computing with Geometry,

　　Adrian Bowyer and John Woodwark, 1993

　　ISBN 1-874728-03-8. Available in PDF:

　　http://www.inge.com/pubs/index.htm

　　[Farin & Hansford]

　　The Geometry Toolbox for Graphics and Modeling

　　by Gerald E. Farin, Dianne Hansford

　　A K Peters Ltd; ISBN: 1568810741

　　[O'Rourke (C)]

　　Computational Geometry in C (2nd Ed.)

　　Joseph O'Rourke, Cambridge University Press 1998,

　　ISBN 0-521-64010-5 Pbk, ISBN 0-521-64976-5 Hbk

　　Additional information and code at http://cs.smith.edu/~orourke/ .

　　[O'Rourke (A)]

　　Art Gallery Theorems and Algorithms

　　Joseph O'Rourke, Oxford University Press 1987,

　　ISBN 0-19-503965-3.

　　[Goodman & O'Rourke]

　　Handbook of Discrete and Computational Geometry

　　J. E. Goodman and J. O'Rourke, editors.

　　CRC Press LLC, July 1997.

　　ISBN:0-8493-8524-5

　　Additional information at http://cs.smith.edu/~orourke/ .

　　[Samet:Application]

　　Applications of Spatial Data Structures: Computer Graphics,

　　Image Processing, and GIS,

　　Hanan Samet, Addison-Wesley, Reading, MA, 1990.

　　ISBN 0-201-50300-0.

　　[Samet:Design & Analysis]

　　The Design and Analysis of Spatial Data Structures,

　　Hanan Samet, Addison-Wesley, Reading, MA, 1990.

　　ISBN 0-201-50255-0.

　　[Mortenson]

　　Geometric Modeling,

　　Michael E. Mortenson, Wiley 1985, ISBN 0-471-88279-8

　　[Preparata]

　　Computational Geometry: An Introduction,

　　Franco P. Preparata, Michael Ian Shamos, Springer-Verlag 1985,

　　ISBN 0-387-96131-3

　　[Okabe]

　　Spatial Tessellations: Concepts and Applications of Voronoi Diagrams,

　　A. Okabe and B. Boots and K. Sugihara,

　　John Wiley, Chichester, England, 1992.

　　[Overmars]

　　Computational Geometry: Algorithms and Applications

　　M. de Berg and M. van Kreveld and M. Overmars and O. Schwarzkopf

　　Springer-Verlag, Berlin, 1997.

　　[Stolfi]

　　Oriented Projective Geometry: A Framework for Geometric Computations

　　Academic Press, 1991.

　　[Hodge]

　　Methods of Algebraic Geometry, Volume 1

　　W.V.D. Hodge and D. Pedoe, Cambridge, 1994.

　　ISBN 0-521-469007-4 Paperback

　　[Tamassia et al 199?]

　　Graph Drawing: Algorithms for the Visualization of Graphs

　　Prentice Hall; ISBN: 0133016153

　　Algorithms books with chapters on computational geometry

　　--------------------------------------------------------

　　[Cormen et al.]

　　Introduction to Algorithms,

　　T. H. Cormen, C. E. Leiserson, R. L. Rivest,

　　The MIT Press, McGraw-Hill, 1990.

　　[Mehlhorn]

　　Data Structures and Algorithms,

　　K. Mehlhorn,

　　Springer-Verlag, 1984.

　　[Sedgewick]

　　R. Sedgewick,

　　Algorithms,

　　Addison-Wesley, 1988.

　　Solid Modelling

　　---------------

　　[Mantyla]

　　Introduction to Solid Modeling

　　Martti Mantyla, Computer Science Press 1988,

　　ISBN 07167-8015-1

　　----------------------------------------------------------------------

　　Subject 0.05: Are there any online references?

　　The computational geometry community maintains its own

　　bibliography of publications in or closely related to that

　　subject. Every four months, additions and corrections are

　　solicited from users, after which the database is updated and

　　released anew. As of 7 Nov 200, it contained 13485 bib-tex

　　entries. See Jeff Erickson's page on "Computational Geometry

　　Bibliographies":

　　http://compgeom.cs.uiuc.edu/~jeffe/compgeom/biblios.html#geombib

　　The bibliography can be retrieved from:

　　ftp://ftp.cs.usask.ca/pub/geometry/geombib.tar.gz - bibliography proper

　　ftp://ftp.cs.usask.ca/pub/geometry/o-cgc19.ps.gz - overview published

　　in '93 in SIGACT News and the Internat. J. Comput. Geom. Appl.

　　ftp://ftp.cs.usask.ca/pub/geometry/ftp-hints - detailed retrieval info

　　Universitat Politecnica de Catalunya maintains a search engine at:

　　http://www-ma2.upc.es/~geomc/geombibe.html

　　The ACM SIGGRAPH Online Bibliography Project, by

　　Stephen Spencer (biblio@siggraph.org

　　).

　　The database is available for anonymous FTP from the

　　ftp://siggraph.org/publications/ directory. Please

　　download and examine the file READ_ME in that directory for more

　　specific information concerning the database.

　　'netlib' is a useful source for algorithms, member inquiries for

　　SIAM, and bibliographic searches. For information, send mail to

　　netlib@ornl.gov

　　, with "send index" in the body of the mail

　　message.

　　You can also find free sources for numerical computation in C via

　　ftp://ftp.usc.edu/pub/C-numanal/ . In particular, grab

　　numcomp-free-c.gz in that directory.

　　Check out Nick Fotis's computer graphics resources FAQ -- it's

　　packed with pointers to all sorts of great computer graphics

　　stuff. This FAQ is posted biweekly to comp.graphics

　　.

　　This WWW page contains links to a large number

　　of computer graphic related pages:

　　http://www.dataspace.com:84/vlib/comp-graphics.html

　　There's a Computer Science Bibliography Server at:

　　http://glimpse.cs.arizona.edu:1994/bib/

　　with Computer Graphics, Vision and Radiosity sections

　　A comprehensive bibliography of color quantization papers and articles

　　(CQUANT97) was available at http://www.ledalite.com/library-/cgis.htm.

　　[Link no longer available -- replacement? --JOR]

　　Modelling physically based systems for animation:

　　http://www.cc.gatech.edu/gvu/animation/Animation.html

　　The University of Manchester NURBS Library:

　　ftp://unix.hensa.ac.uk/pub/misc/unix/nurbs/

　　For an implementation of Seidel's algorithm for fast trapezoidation

　　and triangulation of polygons. You can get the code from:

　　ftp://ftp.cs.unc.edu/pub/users/narkhede/triangulation.tar.gz

　　Ray tracing bibliography:

　　http://www.acm.org/tog/resources/bib/

　　Quaternions and other comp sci curiosities:

　　ftp://ftp.netcom.com/pub/hb/hbaker/hakmem/

　　Directory of Computational Geometry Software,

　　collected by Nina Amenta (nina@cs.utexas.edu

　　)

　　Nina Amenta is maintaining a WWW directory to computational

　　geometry software. The directory lives at The Geometry Center.

　　It has pointers to lots of convex hull and voronoi diagram programs,

　　triangulations, collision detection, polygon intersection, smallest

　　enclosing ball of a point set and other stuff.

　　http://www.geom.umn.edu/software/cglist/

　　A compact reference for real-time 3D computer graphics programming:

　　http://www.math.mcgill.ca/~loisel/

　　RADBIB is a comprehensive bibliography of radiosity and

　　related global illumination papers, articles, and

　　books. It currently includes 1,972 references.

　　This bibliography is available in BibTex format

　　(with a release date of 15 Jul 01) from:

　　http://www.helios32.com/ under "Resources."

　　The "Electronic Visualization Library" (EVlib) is a domain-

　　secific digital library for Scientific Visualization and

　　Computer Graphics: http://visinfo.zib.de/

　　3D Object Intersection: http://www.realtimerendering.com/int/

　　This page presents information about a wide variety of 3D object/object

　　intersection tests. Presented in grid form, each axis lists ray, plane,

　　sphere, triangle, box, frustum, and other objects. For each combination

　　(e.g. sphere/box), references to articles, books, and online resources

　　are given.

　　Ray Tracing News, ed. Eric Haines: http://www.raytracingnews.com .

　　----------------------------------------------------------------------

　　Subject 0.06: Are there other graphics related FAQs?

　　BSP Tree FAQ by Bretton Wade

　　http://www.andrew.cmu.edu/~rrost/bsp/

　　ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html

　　ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.txt

　　and see

　　ftp://ftp.sgi.com/other/bspfaq/

　　Gamma and Color FAQs by Charles A. Poynton has

　　ftp://ftp.inforamp.net/pub/users/poynton/doc/colour/

　　http://www.inforamp.net/~poynton/

　　The documents are mirrored in Darmstadt, Germany at

　　ftp://ftp.igd.fhg.de/pub/doc/colour/

　　----------------------------------------------------------------------

　　Subject 0.07: Where is all the source?

　　Graphics Gems source code.

　　http://www.graphicsgems.org

　　This site is now the offical distribution site for Graphics Gems code.

　　Master list of Computational Geometry software:

　　http://www.geom.umn.edu/software/cglist

　　Described in [Goodman & O'Rourke], Chap. 52.

　　Jeff Erikson's software list:

　　http://compgeom.cs.uiuc.edu/~jeffe/compgeom/compgeom.html

　　Dave Eberly's extensive collection of free geometry, graphics,

　　and image processing software:

　　http://www.magic-software.com/

　　General 'stuff'

　　ftp://wuarchive.wustl.edu/graphics/

　　There are a number of interesting items in

　　http://graphics.lcs.mit.edu/~seth including:

　　- Code for 2D Voronoi, Delaunay, and Convex hull

　　- Mike Hoymeyer's implementation of Raimund Seidel's

　　O( d! n ) time linear programming algorithm for

　　n constraints in d dimensions

　　- geometric models of UC Berkeley's new computer science

　　building

　　Sources to "Computational Geometry in C", by J. O'Rourke

　　can be found at http://cs.smith.edu/~orourke/books/compgeom.html

　　or ftp://cs.smith.edu/pub/compgeom .

　　Greg Ferrar's C++ 3D rendering library is available at

　　http://www.flowerfire.com/ferrar/Graph3D.html

　　TAGL is a portable and extensible library that provides a subset

　　of Open-GL functionalities.

　　ftp://sunsite.unc.edu/pub/packages/programming/graphics/

　　Try ftp://x2ftp.oulu.fi for /pub/msdos/programming/docs/graphpro.lzh by

　　Michael Abrash. His XSharp package has an implementation of Xiaoulin

　　Wu's anti-aliasing algorithm (in C).

　　Example sources for BSP tree algorithms can be found at

　　http://reality.sgi.com/bspfaq/, item 24.

　　Mel Slater (mel@dcs.qmw.ac.uk

　　) also made some implementations of

　　BSP trees and shadows for static scenes using shadow volumes

　　code available

　　http://www.dcs.qmw.ac.uk/~mel/BSP.html

　　ftp://ftp.dcs.qmw.ac.uk/people/mel/BSP

　　The Visualization Toolkit (A visualization textbook, C++ library

　　and Tcl-based interpreter) (see [Schroeder]):

　　http://www.kitware.com/vtk.html

　　WINGED.ZIP, a C++ implementation of Baumgart's winged-edge data structure:

　　ftp://ftp.ledalite.com/pub/

　　CGAL, the Computational Geometry Algorithms Library, is written in C++

　　and is available at http://www.cgal.org

　　.

　　CGAL contains algorithms and data structures for 2D computations

　　(convex hull, Delaunay, constrained Delaunay, Voronoi diagram,

　　regular traingulation, (weighted) Alpha shapes, polytope distance,

　　boolean operations on polygons, decomposition of polygons in

　　monotone or convex parts, arrangements, etc.), 3D, and arbitrary

　　dimensions.

　　A C++ NURBS library written by Lavoie Philippe. Version 2.1.

　　Results may be exported as POV-Ray, RIB (renderman) or VRML files.

　　It also offers wrappers to OpenGL:

　　http://yukon.genie.uottawa.ca/~lavoie/software/nurbs/

　　Paul Bourke has code for several problems, including isosurface

　　generation and Delauney triangulation, at:

　　http://www.swin.edu.au/astronomy/pbourke/geometry/

　　http://www.swin.edu.au/astronomy/pbourke/modeling/

　　A nearly comprehensive list of available 3D engines

　　(most with source code):

　　http://cg.cs.tu-berlin.de/~ki/engines.html

　　See also 5.17:

　　Where can I get the spline description of the famous teapot etc.?

　　Interactive Geometry Software called "Cinderella":

　　http://www.cinderella.de

　　----------------------------------------------------------------------

　　Section 1. 2D Computations: Points, Segments, Circles, Etc.

　　----------------------------------------------------------------------

　　Subject 1.01: How do I rotate a 2D point?

　　In 2D, you make (X,Y) from (x,y) with a rotation by angle t so:

　　X = x cos t - y sin t

　　Y = x sin t + y cos t

　　As a 2x2 matrix this is very simple. If you want to rotate a

　　column vector v by t degrees using matrix M, use

　　M = [cos t -sin t]

　　[sin t cos t]

　　in the product M v.

　　If you have a row vector, use the transpose of M (turn rows into

　　columns and vice versa). If you want to combine rotations, in 2D

　　you can just add their angles, but in higher dimensions you must

　　multiply their matrices.

　　----------------------------------------------------------------------

　　Subject 1.02: How do I find the distance from a point to a line?

　　Let the point be C (Cx,Cy) and the line be AB (Ax,Ay) to (Bx,By).

　　Let P be the point of perpendicular projection of C on AB. The parameter

　　r, which indicates P's position along AB, is computed by the dot product

　　of AC and AB divided by the square of the length of AB:

　　(1) AC dot AB

　　r = ---------

　　||AB||^2

　　r has the following meaning:

　　r=0 P = A

　　r=1 P = B

　　r<0 P is on the backward extension of AB

　　r>1 P is on the forward extension of AB

　　0<r<1 P is interior to AB

　　The length of a line segment in d dimensions, AB is computed by:

　　L = sqrt( (Bx-Ax)^2 + (By-Ay)^2 + ... + (Bd-Ad)^2)

　　so in 2D:

　　L = sqrt( (Bx-Ax)^2 + (By-Ay)^2 )

　　and the dot product of two vectors in d dimensions, U dot V is computed:

　　D = (Ux * Vx) + (Uy * Vy) + ... + (Ud * Vd)

　　so in 2D:

　　D = (Ux * Vx) + (Uy * Vy)

　　So (1) expands to:

　　(Cx-Ax)(Bx-Ax) + (Cy-Ay)(By-Ay)

　　r = -------------------------------

　　L^2

　　The point P can then be found:

　　Px = Ax + r(Bx-Ax)

　　Py = Ay + r(By-Ay)

　　And the distance from A to P = r*L.

　　Use another parameter s to indicate the location along PC, with the

　　following meaning:

　　s<0 C is left of AB

　　s>0 C is right of AB

　　s=0 C is on AB

　　Compute s as follows:

　　(Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)

　　s = -----------------------------

　　L^2

　　Then the distance from C to P = |s|*L.

　　----------------------------------------------------------------------

　　Subject 1.03: How do I find intersections of 2 2D line segments?

　　This problem can be extremely easy or extremely difficult; it

　　depends on your application. If all you want is the intersection

　　point, the following should work:

　　Let A,B,C,D be 2-space position vectors. Then the directed line

　　segments AB & CD are given by:

　　AB=A+r(B-A), r in [0,1]

　　CD=C+s(D-C), s in [0,1]

　　If AB & CD intersect, then

　　A+r(B-A)=C+s(D-C), or

　　Ax+r(Bx-Ax)=Cx+s(Dx-Cx)

　　Ay+r(By-Ay)=Cy+s(Dy-Cy) for some r,s in [0,1]

　　Solving the above for r and s yields

　　(Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy)

　　r = ----------------------------- (eqn 1)

　　(Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)

　　(Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)

　　s = ----------------------------- (eqn 2)

　　(Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)

　　Let P be the position vector of the intersection point, then

　　P=A+r(B-A) or

　　Px=Ax+r(Bx-Ax)

　　Py=Ay+r(By-Ay)

　　By examining the values of r & s, you can also determine some

　　other limiting conditions:

　　If 0<=r<=1 & 0<=s<=1, intersection exists

　　r<0 or r>1 or s<0 or s>1 line segments do not intersect

　　If the denominator in eqn 1 is zero, AB & CD are parallel

　　If the numerator in eqn 1 is also zero, AB & CD are collinear.

　　If they are collinear, then the segments may be projected to the x-

　　or y-axis, and overlap of the projected intervals checked.

　　If the intersection point of the 2 lines are needed (lines in this

　　context mean infinite lines) regardless whether the two line

　　segments intersect, then

　　If r>1, P is located on extension of AB

　　If r<0, P is located on extension of BA

　　If s>1, P is located on extension of CD

　　If s<0, P is located on extension of DC

　　Also note that the denominators of eqn 1 & 2 are identical.

　　References:

　　[O'Rourke (C)] pp. 249-51

　　[Gems III] pp. 199-202 "Faster Line Segment Intersection,"

　　----------------------------------------------------------------------

　　Subject 1.04: How do I generate a circle through three points?

　　Let the three given points be a, b, c. Use _0 and _1 to represent

　　x and y coordinates. The coordinates of the center p=(p_0,p_1) of

　　the circle determined by a, b, and c are:

　　A = b_0 - a_0;

　　B = b_1 - a_1;

　　C = c_0 - a_0;

　　D = c_1 - a_1;

　　E = A*(a_0 + b_0) + B*(a_1 + b_1);

　　F = C*(a_0 + c_0) + D*(a_1 + c_1);

　　G = 2.0*(A*(c_1 - b_1)-B*(c_0 - b_0));

　　p_0 = (D*E - B*F) / G;

　　p_1 = (A*F - C*E) / G;

　　If G is zero then the three points are collinear and no finite-radius

　　circle through them exists. Otherwise, the radius of the circle is:

　　r^2 = (a_0 - p_0)^2 + (a_1 - p_1)^2

　　Reference:

　　[O' Rourke (C)] p. 201. Simplified by Jim Ward.

　　----------------------------------------------------------------------

　　Subject 1.05: How can the smallest circle enclosing a set of points be found?

　　This circle is often called the minimum spanning circle. It can be

　　computed in O(n log n) time for n points. The center lies on

　　the furthest-point Voronoi diagram. Computing the diagram constrains

　　the search for the center. Constructing the diagram can be accomplished

　　by a 3D convex hull algorithm; for that connection, see, e.g.,

　　[O'Rourke (C), p.195ff]. For direct algorithms, see:

　　S. Skyum, "A simple algorithm for computing the smallest enclosing circle"

　　Inform. Process. Lett. 37 (1991) 121--125.

　　J. Rokne, "An Easy Bounding Circle" [Gems II] pp.14--16.

　　----------------------------------------------------------------------

　　Subject 1.06: Where can I find graph layout algorithms?

　　See the paper by Eades and Tamassia, "Algorithms for Drawing

　　Graphs: An Annotated Bibliography," Tech Rep CS-89-09, Dept. of

　　CS, Brown Univ, Feb. 1989.

　　A revised version of the annotated bibliography on graph drawing

　　algorithms by Giuseppe Di Battista, Peter Eades, and Roberto

　　Tamassia is now available from

　　ftp://wilma.cs.brown.edu/pub/papers/compgeo/gdbiblio.tex.gz and

　　ftp://wilma.cs.brown.edu/pub/papers/compgeo/gdbiblio.ps.gz

　　Commercial software includes the Graph Layout Toolkit from Tom Sawyer

　　Software http://www.tomsawyer.com and Northwoods Software's GO++

　　http://www.nwoods.com/go/ .

　　Perhaps the best code is the AT&T Research Labs open C source:

　　http://www.research.att.com/sw/tools/graphviz/

　　----------------------------------------------------------------------

　　Section 2. 2D Polygon Computations

　　----------------------------------------------------------------------

　　Subject 2.01: How do I find the area of a polygon?

　　The signed area can be computed in linear time by a simple sum.

　　The key formula is this:

　　If the coordinates of vertex v_i are x_i and y_i,

　　twice the signed area of a polygon is given by

　　2 A( P ) = sum_{i=0}^{n-1} (x_i y_{i+1} - y_i x_{i+1}).

　　Here n is the number of vertices of the polygon, and index

　　arithmetic is mod n, so that x_n = x_0, etc. A rearrangement

　　of terms in this equation can save multiplications and operate on

　　coordinate differences, and so may be both faster and more

　　accurate:

　　2 A(P) = sum_{i=0}^{n-1} ( x_i (y_{i+1} - y_{i-1}) )

　　Here again modular index arithmetic is implied, with n=0 and -1=n-1.

　　This can be avoided by extending the x[] and y[] arrays up to [n+1]

　　with x[n]=x[0], y[n]=y[0] and y[n+1]=y[1], and using instead

　　2 A(P) = sum_{i=1}^{n} ( x_i (y_{i+1} - y_{i-1}) )

　　References: [O' Rourke (C)] Thm. 1.3.3, p. 21; [Gems II] pp. 5-6:

　　"The Area of a Simple Polygon", Jon Rokne. Dan Sunday's explanation:

　　http://GeometryAlgorithms.com/Archive/algorithm_0101/ where

　　To find the area of a planar polygon not in the x-y plane, use:

　　2 A(P) = abs(N . (sum_{i=0}^{n-1} (v_i x v_{i+1})))

　　where N is a unit vector normal to the plane. The `.' represents the

　　dot product operator, the `x' represents the cross product operator,

　　and abs() is the absolute value function.

　　[Gems II] pp. 170-171:

　　"Area of Planar Polygons and Volume of Polyhedra", Ronald N. Goldman.

　　----------------------------------------------------------------------

　　Subject 2.02: How can the centroid of a polygon be computed?

　　The centroid (a.k.a. the center of mass, or center of gravity)

　　of a polygon can be computed as the weighted sum of the centroids

　　of a partition of the polygon into triangles. The centroid of a

　　triangle is simply the average of its three vertices, i.e., it

　　has coordinates (x1 + x2 + x3)/3 and (y1 + y2 + y3)/3. This

　　suggests first triangulating the polygon, then forming a sum

　　of the centroids of each triangle, weighted by the area of

　　each triangle, the whole sum normalized by the total polygon area.

　　This indeed works, but there is a simpler method: the triangulation

　　need not be a partition, but rather can use positively and

　　negatively oriented triangles (with positive and negative areas),

　　as is used when computing the area of a polygon. This leads to

　　a very simple algorithm for computing the centroid, based on a

　　sum of triangle centroids weighted with their signed area.

　　The triangles can be taken to be those formed by any fixed point,

　　e.g., the vertex v0 of the polygon, and the two endpoints of

　　consecutive edges of the polygon: (v1,v2), (v2,v3), etc. The area

　　of a triangle with vertices a, b, c is half of this expression:

　　(b[X] - a[X]) * (c[Y] - a[Y]) -

　　(c[X] - a[X]) * (b[Y] - a[Y]);

　　Code available at ftp://cs.smith.edu/pub/code/centroid.c (3K).

　　Reference: [Gems IV] pp.3-6; also includes code.

　　----------------------------------------------------------------------

　　Subject 2.03: How do I find if a point lies within a polygon?

　　The definitive reference is "Point in Polygon Strategies" by

　　Eric Haines [Gems IV] pp. 24-46. Now also at

　　http://www.erichaines.com/ptinpoly

　　.

　　The code in the Sedgewick book Algorithms (2nd Edition, p.354) fails

　　under certain circumstances. See

　　http://condor.informatik.Uni-Oldenburg.DE/~stueker/graphic/index.html

　　for a discussion.

　　The essence of the ray-crossing method is as follows.

　　Think of standing inside a field with a fence representing the polygon.

　　Then walk north. If you have to jump the fence you know you are now

　　outside the poly. If you have to cross again you know you are now

　　inside again; i.e., if you were inside the field to start with, the total

　　number of fence jumps you would make will be odd, whereas if you were

　　ouside the jumps will be even.

　　The code below is from Wm. Randolph Franklin <wrf@ecse.rpi.edu

　　>

　　(see URL below) with some minor modifications for speed. It returns

　　1 for strictly interior points, 0 for strictly exterior, and 0 or 1

　　for points on the boundary. The boundary behavior is complex but

　　determined; in particular, for a partition of a region into polygons,

　　each point is "in" exactly one polygon.

　　(See p.243 of [O'Rourke (C)] for a discussion of boundary behavior.)

　　int pnpoly(int npol, float *xp, float *yp, float x, float y)

　　{

　　int i, j, c = 0;

　　for (i = 0, j = npol-1; i < npol; j = i++) {

　　if ((((yp[i]<=y) && (y<yp[j])) ||

　　((yp[j]<=y) && (y<yp[i]))) &&

　　(x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))

　　c = !c;

　　}

　　return c;

　　}

　　The code may be further accelerated, at some loss in clarity, by

　　avoiding the central computation when the inequality can be deduced,

　　and by replacing the division by a multiplication for those processors

　　with slow divides. For code that distinguishes strictly interior

　　points from those on the boundary, see [O'Rourke (C)] pp. 239-245.

　　For a method based on winding number, see Dan Sunday,

　　"Fast Winding Number Test for Point Inclusion in a Polygon,"

　　http://softsurfer.com/algorithms.htm

　　, March 2001.

　　References:

　　Franklin's code:

　　http://www.ecse.rpi.edu/Homepages/wrf/research/geom/pnpoly.html

　　[Gems IV] pp. 24-46

　　[O'Rourke (C)] Sec. 7.4.

　　[Glassner:RayTracing]

　　----------------------------------------------------------------------

　　Subject 2.04: How do I find the intersection of two convex polygons?

　　Unlike intersections of general polygons, which might produce a

　　quadratic number of pieces, intersection of convex polygons of n

　　and m vertices always produces a polygon of at most (n+m) vertices.

　　There are a variety of algorithms whose time complexity is proportional

　　to this size, i.e., linear. The first, due to Shamos and Hoey, is

　　perhaps the easiest to understand. Let the two polygons be P and

　　Q. Draw a horizontal line through every vertex of each. This

　　partitions each into trapezoids (with at most two triangles, one

　　at the top and one at the bottom). Now scan down the two polygons

　　in concert, one trapezoid at a time, and intersect the trapezoids

　　if they overlap vertically.

　　A more difficult-to-describe algorithm is in [O'Rourke (C)], pp. 252-262.

　　This walks around the boundaries of P and Q in concert, intersecting

　　edges. An implementation is included in [O'Rourke (C)].

　　----------------------------------------------------------------------

　　Subject 2.05: How do I do a hidden surface test (backface culling) with 2D points?

　　c = (x1-x2)*(y3-y2)-(y1-y2)*(x3-x2)

　　x1,y1, x2,y2, x3,y3 = the first three points of the polygon.

　　If c is positive the polygon is visible. If c is negative the

　　polygon is invisible (or the other way).

　　----------------------------------------------------------------------

　　Subject 2.06: How do I find a single point inside a simple polygon?

　　Given a simple polygon, find some point inside it. Here is a method

　　based on the proof that there exists an internal diagonal, in

　　[O'Rourke (C), 13-14]. The idea is that the midpoint of a diagonal

　　is interior to the polygon.

　　1. Identify a convex vertex v; let its adjacent vertices be a and b.

　　2. For each other vertex q do:

　　2a. If q is inside avb, compute distance to v (orthogonal to ab).

　　2b. Save point q if distance is a new min.

　　3. If no point is inside, return midpoint of ab, or centroid of avb.

　　4. Else if some point inside, qv is internal: return its midpoint.

　　Code for finding a diagonal is in [O'Rourke (C), 35-39], and is part

　　of many other software packages. See Subject 0.07: Where is all the

　　source?

　　----------------------------------------------------------------------

　　Subject 2.07: How do I find the orientation of a simple polygon?

　　Compute the signed area (Subject 2.01). The orientation is

　　counter-clockwise if this area is positive.

　　A slightly faster method is based on the observation that it isn't

　　necessary to compute the area. Find the lowest vertex (or, if

　　there is more than one vertex with the same lowest coordinate,

　　the rightmost of those vertices) and then take the cross product

　　of the edges fore and aft of it. Both methods are O(n) for n vertices,

　　but it does seem a waste to add up the total area when a single cross

　　product (of just the right edges) suffices. Code for this is

　　available at ftp://cs.smith.edu/pub/code/polyorient.C (2K).

　　The reason that the lowest, rightmost (or any other such extreme) point

　　works is that the internal angle at this vertex is necessarily convex,

　　strictly less than pi (even if there are several equally-lowest points).

　　----------------------------------------------------------------------

　　Subject 2.08: How can I triangulate a simple polygon?

　　Triangulation of a polygon partitions its interior into triangles

　　with disjoint interiors. Usually one restricts corners of the

　　triangles to coincide with vertices of the polygon, in which case

　　every polygon of n vertices can be triangulated, and all triangulations

　　contain n-2 triangles, employing n-3 "diagonals" (chords between

　　vertices that otherwise do not touch the boundary of the polygon).

　　Triangulations can be constructed by a variety of algorithms,

　　ranging from a naive search for noncrossing diagonals, which is

　　O(n^4), to "ear" clipping, which is O(n^2) and relatively straightforward

　　to implement [O'Rourke (C), Chap. 1], to partitioning into

　　monotone polygons, which leads to O(n log n) time complexity

　　[O'Rourke (C), Chap. 2; Overmars, Chap. 3], to several randomized

　　algorithms---by Clarkson et al., by Seidel, and by Devillers, which

　　lead to O(n log* n) complexity---to Chazelle's linear-time algorithm,

　　which has yet to be implemented.

　　There is a tradeoff between code complexity and time complexity.

　　Fortunately, several of the algorithms have been implemented and are

　　available:

　　Ear-clipping:

　　http://cs.smith.edu/~orourke/books/compgeom.html

　　ftp://ftp.cis.uab.edu/pub/sloan/Software/triangulation/src/

　　Seidel's Alg:

　　http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html

　　ftp://ftp.cs.unc.edu/pub/users/narkhede/triangulation.tar.gz

　　http://reality.sgi.com/atul/code/chapter.html

　　See also the collection of triangulation links at

　　http://www.geom.umn.edu/software/cglist/

　　References:

　　[O'Rourke (C)]

　　[Overmars]

　　[Gems V]

　　Clarkson, K., Tarjan, R., and VanWyk, C. A fast Las Vegas algorithm for

　　triangulating a simple polygon. Discrete and Computational Geometry,

　　4(1):423--432, 1989.

　　Clarkson, K., Cole, R., Tarjan, R. Randomized parallel algorithms for

　　trapezoidal diagrams. Int. J. Comp. Geom. Appl., 117--133, 1992.

　　http://cm.bell-labs.com/cm/cs/who/clarkson/tri.html

　　Seidel, R. (1991), A simple and fast incremental randomized algorithm for

　　computing trapezoidal decompositions and for triangulating polygons,

　　Comput. Geom. Theory Appl. 1, 51--64.

　　Devillers, O. (1992), Randomization yields simple O(n log* n)

　　algorithms for difficult Omega(n) problems,

　　Internat. J. Comput. Geom. Appl. 2(1), 97--111.

　　Chazelle, B. (1991), Triangulating a simple polygon in linear time,

　　Discrete Comput. Geom. 6, 485--524.

　　Held, M. (1998) "FIST: Fast Industrial-Strength Triangulation".

　　http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html

　　----------------------------------------------------------------------

　　Subject 2.09: How can I find the minimum area rectangle enclosing a set of points?

　　First take the convex hull of the points. Let the resulting convex

　　polygon be P. It has been known for some time that the minimum

　　area rectangle enclosing P must have one rectangle side flush with

　　(i.e., collinear with and overlapping) one edge of P. This geometric

　　fact was used by Godfried Toussaint to develop the "rotating calipers"

　　algorithm in a hard-to-find 1983 paper, "Solving Geometric Problems

　　with the Rotating Calipers" (Proc. IEEE MELECON). The algorithm

　　rotates a surrounding rectangle from one flush edge to the next,

　　keeping track of the minimum area for each edge. It achieves O(n)

　　time (after hull computation). See the "Rotating Calipers Homepage"

　　http://www.cs.mcgill.ca/~orm/rotcal.frame.html for a description

　　and applet.

　　----------------------------------------------------------------------

　　Section 3. 2D Image/Pixel Computations

　　----------------------------------------------------------------------

　　Subject 3.01: How do I rotate a bitmap?

　　The easiest way, according to the comp.graphics faq, is to take

　　the rotation transformation and invert it. Then you just iterate

　　over the destination image, apply this inverse transformation and

　　find which source pixel to copy there.

　　A much nicer way comes from the observation that the rotation

　　matrix:

　　R(T) = { { cos(T), -sin(T) }, { sin(T), cos(T) } }

　　is formed my multiplying three matrices, namely:

　　R(T) = M1(T) * M2(T) * M3(T)

　　where

　　M1(T) = { { 1, -tan(T/2) },

　　{ 0, 1 } }

　　M2(T) = { { 1, 0 },

　　{ sin(T), 1 } }

　　M3(T) = { { 1, -tan(T/2) },

　　{ 0, 1 } }

　　Each transformation can be performed in a separate pass, and

　　because these transformations are either row-preserving or

　　column-preserving, anti-aliasing is quite easy.

　　Another fast approach is to perform first a column-preserving roation,

　　and then a row-preserving rotation. For an image W pixels wide and

　　H pixels high, this requires W+H BitBlt operations in comparison to

　　the brute-force rotation, which uses W*H SetPixel operations (and a

　　lot of multiplying).

　　Reference:

　　Paeth, A. W., "A Fast Algorithm for General Raster Rotation",

　　Proceedings Graphics Interface '89, Canadian Information

　　Processing Society, 1986, 77-81

　　[Note - e-mail copies of this paper are no longer available]

　　[Gems I]

　　----------------------------------------------------------------------

　　Subject 3.02: How do I display a 24 bit image in 8 bits?

　　[Gems I] pp. 287-293, "A Simple Method for Color Quantization:

　　Octree Quantization"

　　B. Kurz. Optimal Color Quantization for Color Displays.

　　Proceedings of the IEEE Conference on Computer Vision and Pattern

　　Recognition, 1983, pp. 217-224.

　　[Gems II] pp. 116-125, "Efficient Inverse Color Map Computation"

　　This describes an efficient technique to

　　map actual colors to a reduced color map,

　　selected by some other technique described

　　in the other papers.

　　[Gems II] pp. 126-133, "Efficient Statistical Computations for

　　Optimal Color Quantization"

　　Xiaolin Wu. Color Quantization by Dynamic Programming and

　　Principal Analysis. ACM Transactions on Graphics, Vol. 11, No. 4,

　　October 1992, pp 348-372.

　　----------------------------------------------------------------------

　　Subject 3.03: How do I fil