From: orourke@cs.smith.edu (Joseph O'Rourke) Newsgroups: comp.graphics.algorithms,news.answers,comp.answers Subject: comp.graphics.algorithms Frequently Asked Questions Message-ID: Reply-To: orourke@cs.smith.edu (Joseph O'Rourke) Followup-To: comp.graphics.algorithms Distribution: world Approved: news-answers-request@MIT.EDU Expires: 10/16/97 01:11:01 EDT Supersedes: 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. Originator: orourke@grendel.csc.smith.edu NNTP-Posting-Host: grendel.csc.smith.edu Date: 1 Oct 97 05:10:50 GMT Organization: Smith College, Northampton Mass, USA Lines: 2338 Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!hecate.umd.edu!cs.umd.edu!zombie.ncsc.mil!alnews.ncsc.mil!uunet!in5.uu.net!nntprelay.mathworks.com!cam-news-hub1.bbnplanet.com!cam-news-feed5.bbnplanet.com!news.bbnplanet.com!umass.edu!news.smith.edu!orourke Xref: senator-bedfellow.mit.edu comp.graphics.algorithms:55575 news.answers:113467 comp.answers:28288 Posted-By: auto-faq 3.2.1.4 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 1997 by Joseph O'Rourke. It may be freely redistributed in its entirety provided that this copyright notice is not removed. ---------------------------------------------------------------------- Changed items this posting (|): 0.03 New items this posting (+): 1.05 ---------------------------------------------------------------------- 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? 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)? 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 polygon? 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 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? 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? 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 (picture source code) 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 ---------------------------------------------------------------------- Subject 0.02: Are the postings to comp.graphics.algorithms archived? Archives may be found at: ftp://wuarchive.wustl.edu/graphics/graphics/mail-lists/comp.graphics.algorithms It is archived in the same manner that all other newsgroups are being archived there, namely there is an Index file with all the subjects, and all the articles are being kept in a hierarchy based on the year and month they are posted. ---------------------------------------------------------------------- |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 the latest HTML version at either of these two sites: | http://www.exaflop.org/docs/cgafaq http://www.cis.ohio-state.edu/hypertext/faq/usenet/graphics/algorithms-faq/faq.html The exaflop version should be up-to-date and is nicely converted; the ohio-state site is sometimes out of date. Finally, you can ftp the FAQ from several sites, including: ftp://rtfm.mit.edu/pub/faqs/graphics/algorithms-faq ftp://ftp.seas.gwu.edu/pub/rtfm/comp/graphics/algorithms/comp.graphics.algorithms_Frequently_Asked_Questions 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, David F. Rogers, McGraw Hill 1985, ISBN 0-07-053534-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 [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 [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, 3rd Edition, Gerald E. Farin, Academic Press 1993. ISBN 0-12-249052-5 [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 [Ebert] Texturing and Modeling - A Procedural Approach David S. Ebert (ed.), F. Kenton Musgrave, Darwyn Peachey, Ken Perlin, Setven Worley, Academic Press 1994, ISBN 0-12-228760-6, ISBN 0-12-2278761-4 (IBM disk) [Schroeder] Visualization Toolkit, The: An Object-Oriented Approach to 3-D Graphics (Bk/CD) (Professional Description) William J. Schroeder, Kenneth Martin and Bill Lorensen, Prentice-Hall 1996, ISBN: 0-13-199837-4 (Published: 02/02/96) See Subject 0.07 for source. [Anderson] PC Graphics Unleashed Scott Anderson. SAMS Publishing, ISBN 0-672-30570-4 Ammeraal, L. (1992) Programming Principles in Computer Graphics, 2nd Edition, Chichester: John Wiley, ISBN 0 471 93128 4. 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, John C. Russ, CRC Press 1992, ISBN 0-8493-4233-3 [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 [O' Rourke] Computational Geometry in C, Joseph O'Rourke, Cambridge University Press 1994, ISBN 0-521-44592-2 Pbk, ISBN 0-521-44034-3 Hdbk [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 [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. 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 February 1996, it contained 7,154 bib-tex entries. It can be retrieved from ftp://ftp.cs.usask.ca/pub/geometry/geombib.tar.Z - bibliography proper ftp://ftp.cs.usask.ca/pub/geometry/geom.ps.Z - PostScript format ftp://ftp.cs.usask.ca/pub/geometry/o-cgc19.ps.Z - 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 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/bibliography 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://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 is available at ftp://hobbes.lbl.gov/pub/doc/cquant95.txt 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: ftp://ftp.eye.com/pub/graphics/papers/rtbib95.tar.Z ftp://ftp.eye.com/pub/graphics/papers/rtbib95.zip Quaternions and other comp sci curiosities: ftp://ftp.netcom.com/pub/hb/hbaker/hakmem/hakmem.html Directory of Computational Geometry Software, collected by Nina Amenta (nina@geom.umn.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/lowdvod.html A compact reference for real-time 3d computer graphics programming: http://www.cs.mcgill.ca/~zed ---------------------------------------------------------------------- Subject 0.06: Are there other graphics related FAQs? BSP Tree FAQ by Bretton Wade http://reality.sgi.com/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 to space provided by Fraunhofer Computer Graphics in Rhode Island, U.S.A. at ftp://elaine.crcg.edu/pub/doc/colour/ 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.acm.org/tog/GraphicsGems/ 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://www.cs.duke.edu/~jeffe/compgeom/code.html General 'stuff' ftp://wuarchive.wustl.edu/graphics/graphics There are a number of interesting items in http://theory.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 You can find useful overviews of a number of computer graphic topics in http://archpropplan.auckland.ac.nz/People/Paul/Paul.html including: - area/orientation of polygons - finding if a point lies within a polygon - generating a circle through 3 points - description and psuedo-code for Delaunay triangulation - basic viewing in 3D etc. Sources to "Computational Geometry in C", by J. O'Rourke can be found at ftp://grendel.csc.smith.edu/pub/compgeom Greg Ferrar has uploaded his heavily commented C++ 3D rendering library at ftp://ftp.math.ohio-state.edu/pub/users/gregt TAGL is a portable and extensible library that provides a subset of Open-GL functionalities. ftp://sunsite.unc.edu/pub/packages/programming/graphics/tagl21.tgz 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 in ftp://ftp.qualia.com/pub/bspfaq/ 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://iuinfo.tuwien.ac.at:8000/htdocs/vtk/ See also 5.17: Where can I get the spline description of the famous teapot etc.? ---------------------------------------------------------------------- Section 1. 2D Computations: Points, Segments, Circles, Etc. ---------------------------------------------------------------------- Subject 1.01: How do I rotate a 2D point? In 2-D, the 2x2 matrix 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 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 2-D 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 (XC,YC) and the line be AB (XA,YA) to (XB,YB). The length of the line segment AB is L: L=((XB-XA)**2+(YB-YA)**2)**0.5 and (YA-YC)(YA-YB)-(XA-XC)(XB-XA) r = ----------------------------- L**2 (YA-YC)(XB-XA)-(XA-XC)(YB-YA) s = ----------------------------- L**2 Let I be the point of perpendicular projection of C onto AB, the XI=XA+r(XB-XA) YI=YA+r(YB-YA) Distance from A to I = r*L Distance from C to I = s*L If r<0 I is on backward extension of AB If r>1 I is on ahead extension of AB If 0<=r<=1 I is on AB If s<0 C is left of AB (you can just check the numerator) If s>0 C is right of AB If s=0 C is on AB ---------------------------------------------------------------------- Subject 1.03: How do I find intersections of 2 2D line segments? This problem can be extremely easy or extremely difficult depends on your applications. 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 XA+r(XB-XA)=XC+s(XD-XC) YA+r(YB-YA)=YC+s(YD-YC) for some r,s in [0,1] Solving the above for r and s yields (YA-YC)(XD-XC)-(XA-XC)(YD-YC) r = ----------------------------- (eqn 1) (XB-XA)(YD-YC)-(YB-YA)(XD-XC) (YA-YC)(XB-XA)-(XA-XC)(YB-YA) s = ----------------------------- (eqn 2) (XB-XA)(YD-YC)-(YB-YA)(XD-XC) Let I be the position vector of the intersection point, then I=A+r(B-A) or XI=XA+r(XB-XA) YI=YA+r(YB-YA) 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 coincident 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, I is located on extension of AB If r<0, I is located on extension of BA If s>1, I is located on extension of CD If s<0, I is located on extension of DC Also note that the denominators of eqn 1 & 2 are identical. References: [O'Rourke] 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] 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, p.195ff]. For a direct algorithm, see: | S. Skyum, "A simple algorithm for computing the smallest enclosing circle" | Inform. Process. Lett. 37 (1991) 121--125. ---------------------------------------------------------------------- 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 ---------------------------------------------------------------------- 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. References: [O' Rourke] pp. 18-27; [Gems II] pp. 5-6: "The Area of a Simple Polygon", Jon Rokne. 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 one fixed 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://grendel.csc.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 Polyon Strategies" by Eric Haines [Gems IV] pp. 24-46. The code in the Sedgewick book Algorithms (2nd Edition, p.354) is incorrect. 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 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 the references below for more detail. 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