计算几何与计算机图形学方面的一些资源及源代码收藏(英文版)

zhouningyi1

资料都非常好， 很多问题自己觉得花了很多力气，其实却是国外很久以前的热点了。计算几何是参数化的算法基础，很基础很重要，在这方面我们和国外的差距是非常大的，有兴趣的同学可以关注一下。 在鄙人小站数学的美学世界小站也发了一稿，另外也有些别的数字资源，欢迎关注 http://zhan.renren.com/mathart This page lists "small" pieces of geometric software available on the Internet. Most of the software is available free of charge. Unless otherwise specified, C or C++ source code is available for all programs. Software libraries and collections and programs that can be run interactively over the web are listed on separate web pages.Caveat Surfor ! I can't make any claims about the usefulness or quality of the programs listed here. I don't have the time or equipment to try them all. If you have experience with any of these programs, either positive or negative, please tell me about it . The programs on this page are divided into several categories, some of which are divided into further sub-categories. (Eventually, each category will get its own separate web page.) Each program is listed only once, but I've provided cross-links between overlapping categories, and I've tried to arrange similar categories near each other.

• Robust low-level primitives
• Combinatorics and discrete math
• Geometric optimization
• Convex hulls and convex polyhedra
• Voronoi diagrams and Delaunay triangulations
• Operations on polygons
• Mesh generation and manipulation
• Geometric modeling
• Visibility computation
• Visualization tools
• Other

Each category also includes links to relevant pages in Nina Amenta 's comprehensive Directory of Computational Geometry Software , which I strongly encourage you to visit! Items marked have been recently added or modified. Robust low-level primitivesAvoid roundoff and precision errors! Use this code instead of naïve floating point or integer arithmetic.

• Relevant pages from DCGS:
  • Numerical and algebraic computation
• Ken Clarkson's Hull contains code to compute signs of determinants. See this paper for a description of his algorithms.
• Sylvain Pion 's Modular package, based on the algorithms in \"Modular Arithmetic for Geometric Predicates\" byHervé Brönnimann , Ioannis Z. Emiris , Victor Pan and Sylvain Pion .
• Adaptive precision floating point predicates used in Jonathan Shewchuk's Triangle package.
• Libraries for affine arithmetic and interval arithmetic (the first requires the second) from Jorge Stolfi's software collection
• Several algorithms to compute the exact sign of a deteminant (also here ), collected by Mariette Yvinec . Part of the PRISME project at INRIA Sophia-Antipolis.
• The LEDA libraries includes code for exact arbitrary-precision integer, rational, floating point, and "real" arithmetic.

zhouningyi1

Combinatorics and discrete math

• LINK: A Software System for Discrete Mathematics under development at DIMACS
• Ulli Hund 's program om2ps for visualizing oriented matroids as arrangements of pseudospheres. Sample output is available.
• Jorjeta Jetcheva 's program to draw \"clusters of stars\" , using an algorithm of Ileana Strienu (requires LEDA )
• Komei Fukuda's Reverse Search mathematica package for enumerating triangulations and connected induced subgraphs. Requires Steve Skiena's Combinatorica package.

Geometric optimization

• Relevant pages from DCGS:
  • Linear programming, smallest enclosing ball and center point
• Code by Ken Clarkson :
  • Fixed-dimensional linear programming
  • Approximate center points
• From Graphics Utilities by David Eberly :
  • Minimum enclosing circle
  • Minimum enclosing sphere (3d only)
• Mike Hohmeyer's implementation of Seidel's linear programming algorithm, courtesy of Seth Teller
• ANN: Library for Approximate Nearest Neighbor Searching , by David Mount and Sunil Arya
• Dave White's smallest enclosing ball software

Convex hulls and convex polyhedraMost convex hull programs will also compute Voronoi diagrams and Delaunay triangulations. (Actually, all of them do, if you look at them the right way.) Relevant pages from DCGS:

• Arbitrary dimensional convex hull, Voronoi diagram, Delaunay triangulation
• Low dimensional convex hull, Voronoi diagram and Delaunay triangulation

Low-dimensional convex hulls

• Two-dimensional convex hulls by Ken Clarkson
• From Graphics Utilities by David Eberly :
  • 2d convex hulls: conhull2.h , conhull2.c
  • 3d convex hulls: conhull3.h , conhull3.c
• ZRAM, a library of parallel search algorithms and data structures by Ambros Marzetta and others, includes a parallel implementation of Avis and Fukuda's reverse search algorithm.
• Geometric software by Darcy Quesnel :
  • Randomized parallel 3D convex hull , with documentation
  • 2D Delaunay triangulation, Voronoi diagram, and convex hull (requires LEDA )
• Harald Rosenberger's implementation of the beneath-beyond method for 3- and 4-dimensional convex hulls, courtesy of Ernst Mücke's GeomDir .

Arbitrary-dimensional convex hulls

• lrs 3.1 : the first "official" distribution of David Avis' implementation of Avis and Fukuda's reverse search algorithm for vertex/facet enumeration. (This is an updated version of an earlier preliminary implementation .) An extensive user's guide is included.
• Qhull by Brad Barber, David Dobkin, and Hannu Huhdanpaa
  • Also available from this mirror site in Spain
  • The latest version (2.5) was released February 4, 1998.
• Primal-dual methods for vertex and facet enumeration by David Bremner , Komei Fukuda , and Ambros Marzetta
• Hull: Arbitrary-dimensional convex hulls, Voronoi diagrams, Delaunay triangulations, and alpha shapes, by Ken Clarkson
• PORTA , a collection of tools for analyzing polytopes and polyhedra, by Thomas Christof and Andreas Loebel , featured in Günter Ziegler's Lectures on Polytopes .
• Computational geometry software by Ioannis Emiris : perturbed convex hulls in arbitrary dimensions, exact convex hulls in two and three dimensions, mixed volume in arbitrary dimensions, and mixed subdivisions in the plane.
• Polytope software by Komei Fukuda
  • cdd and cdd+ : arbitrary-dimensional convex hulls using Motzkin's double description method
  • A Mathematica package for Vertex enumeration of polytopes and arrangements
• Kurt Mehlhorn's programs for generating higher dimensional convex hulls and Delaunay triangulations and checking geometric structures. (C++WEB output only)

红环针管笔

楼主，，这个该怎么学习的！是建立在计算机语言上学习的么？

zhouningyi1

Measure properties

• Vinci (also here ): a program for computing volumes of convex polytopes, presented as either the convex hull of a set of points, the intersection of a set of halfspaces, or both (with the vertex-facet incidence graph). Extensive online documentation and sample polytope files are available. Written by Benno Büeler , Andreas Enge , and Komei Fukuda .
• Ehrhart , a program to count integer points in convex polyhedra and compute Ehrhart polynomials , by Philippe Claus , Vincent Loechner , and Doran Wilde .
• Fast and accurate computation of polyhedral mass properties by Brian Mirtich , published in journal of graphics tools 1.2:31-50 (1996)

Boolean operations on polyhedra

• Polymake , a general-purpose polytope and polyhedron manipulation tool by Ewgenij Gawrilow and Michael Joswig Requires either cdd+ , lrs , or porta for some computations and geomview for visualization. [C++ and Perl]
• Polylib, a library of polyhedral functions by Doran Wilde , includes code to compute convex hulls and perform boolean operations on unions of polytopes in any dimension.

Interesting and/or pathological polytope data

• Examples of pathological polytopes collected by David Bremner. See \"How Good are Convex Hull Algorithms?\" by Avis, Bremner, and Seidel for details. (data only)
• A collection of polytopes , mostly due to Günther Ziegler, from the polymake web site. (data only)

Miscellaneous

• A Mathematica package for unfolding 3D polytopes (README ) by Komei Fukuda ; see \"Strange Unfoldings of Convex Polytopes\" for details.
• PUNTOS , a Maple package for computing triangulations of polytopes, regular triangulations of point sets, and their underlying oriented matroids, by Jesús de Loera
• Convex polyhedron code from a collection of mathematical programming software at the Konrad-Zuse-Zentrum für Informationstechnik , Berlin.

Voronoi diagrams and Delaunay triangulationsSee also the implementation page from Christopher Gold's site www.Voronoi.com . Relevant pages from DCGS:

• Arbitrary dimensional convex hull, Voronoi diagram, Delaunay triangulation
• Low dimensional convex hull, Voronoi diagram and Delaunay triangulation
• Medial axis and constrained Delaunay triangulation

Voronoi diagrams and Delaunay triangulations of pointsMany convex hull programs can also compute Voronoi diagrams and Delaunay triangulations.

• 2d and 3d Delaunay triangulations by Jean-Daniel Boissonnat, Olivier Devillers, Stefan Meiser, and Monique Teillaud, from the PRISME project at INRIA Sophia-Antipolis.
• The Delaunay hieararchy , a data structure for 2d Delaunay triangulations that supports dynamic insertions (and deletions, but those aren't implemented), by Olivier Devillers, from the PRISME project at INRIA Sophia-Antipolis. (Solaris and SGI executables only)
• Graphics utilities by David Eberly :
  • 2d Delaunay triangulations: delaun2.c
  • 3d Delaunay triangulations: delaun3.c
• GAMBINI: a program for constructing multiplicatively weighted Voronoi diagrams for points in the plane, by Barry Boots . (Windows 3.1/95/NT executable only)
• Ernst Mücke's Detri , from his GeomDir , robustly computes 3D Delaunay triangulations.
• A simple divide-and-conquer Delaunay triangulation algorithm from Jorge Stolfi's software collection . Requires Stolfi's quad edge data structure library .
• Software by John Sullivan includes code to compute either standard Voronoi diagrams in Euclidean 3-space or periodic Voronoi diagrams in the 3-torus.
• Dave Watson 's incremental convex hull/Delaunay triangulation program nnsort.c and a description of the algorithm
• Roman Waupotitsch's MinMaxer generates Delaunay, regular, and various other triangulations of two-dimensional point sets.
• Software on the Web , from the CNR-Pisa Visual Computing Group , includes code for 3D Delaunay triangulations

zhouningyi1

• GAMBINI: a program for constructing multiplicatively weighted Voronoi diagrams for points in the plane, by Barry Boots . (Windows 3.1/95/NT executable only)
• Ernst Mücke's Detri , from his GeomDir , robustly computes 3D Delaunay triangulations.
• A simple divide-and-conquer Delaunay triangulation algorithm from Jorge Stolfi's software collection . Requires Stolfi's quad edge data structure library .
• Software by John Sullivan includes code to compute either standard Voronoi diagrams in Euclidean 3-space or periodic Voronoi diagrams in the 3-torus.
• Dave Watson 's incremental convex hull/Delaunay triangulation program nnsort.c and a description of the algorithm
• Roman Waupotitsch's MinMaxer generates Delaunay, regular, and various other triangulations of two-dimensional point sets.
• Software on the Web , from the CNR-Pisa Visual Computing Group , includes code for 3D Delaunay triangulations

Constrained Delaunay triangulationsSee also mesh generation and manipulation .

• Super Delaunay , a commercial fully dynamic constrained Delaunay triangulation package from David Kornmann (description only) . Interactive demo versions for Sun Solaris and Linux are available here (binaries and data only) . Demo versions for other architectures are available from the author .
• Dani Lischinski 's incremental constrained Delaunay triangulation program CDT .
• Robert J. Renka's TRIPACK , Collected Algorithms of the ACM#751, computes constrained Delaunay triangulations, convex hulls, polygon areas, nearest neighbors, and shortest paths. (FORTRAN)

Medial axes and Voronoi diagrams of line segments

• Voronoi Diagrams of 2D Shapes by Martin Held . Robust computation of Voronoi diagrams and offset curves for planar shapes bounded by straight line segments and circular arcs. The web site only describes the software and illustrates some of the results; the code is available by email.
• Voronoi diagrams of line segments by Toshiyuki Imai (FORTRAN)
• Robert L. Ogniewicz 's image skeletonization software
• avd , a LEDA extension package to compute abstract Voronoi diagrams in the plane, by Michael Seel. Code for Euclidean Voronoi diagrams of points and line segments is included.

Miscellaneous

• VoronoiImage by Marc Grundland: an image processing program that uses nested Voronoi diagrams to acheive stained-glass effects (Mac binaries only) [Warning: frames!]
• Alpha Shapes project at NCSA [Warning: frames!]
  • Online demo (also requires Java and VRML)
  • User's guide
  • Downloading instructions
  • Installation instructions
  • Documentation from Ernst Mücke's GeomDir

Operations on polygonsRelevant pages from DCGS:

• Medial axis and constrained Delaunay triangulation
• Polygons: decomposition, point location, intersection, visibility
• Triangulation

Point location

• Paul Bourke describes how to tell if a point is inside a polygon and how to calculate the area of a polygon , with C source code. From his Geometry pages .
• PNPOLY : William Randolf Franklin's point-in-polygon test, from the comp.graphics.algorithms FAQ
• Eric Haines' point-in-polygon code and experimental results from Ray Tracing News, Volume 5, Number 3 . Newer, more optimized code is also available in Graphics Gems IV .

zhouningyi1

Simplification

• Michael Garland 's terrain simplification programs scape and terra .
• Qslim : surface simplification code, using quadric error metrics , by Michael Garland
• Jade , a tool for simplifying triangular meshes, from the CNR-Pisa Visual Computing Group .
• Simplification Envelopes from the UNC Research Group on Modeling, Physically-Based Simulation and Applications

Visibility computation

• Heather Alef 's X-windows visibility graph exploration tool
• Fast, minimum storage ray-triangle intersection by Tomas Möller and Ben Trumbore , from journal of graphics tools2.1:21-28 (1997)
• VisPak: a package of visibility-related algorithms implemented by Helen Pinto and Lillanne Jackson at the University of Lethbridge. Requires LEDA to compile, but Sun binaries are provided.
• Michel Pocchiola and Gert Vegter 's Greedy Flip Algorithm in Action , an implementation of the authors' algorithm for constructing visibility complexes by evolving pseudo-triangulations.
• Visibility Graphs and Motion Planning by Kittiphan Techakittiroj (Windows 3.1 executable only)

Visualization toolsYou should also look for the thing being visualized! See also my list of programs that can be run over the web .

• Relevant pages from DCGS:
  • Visualization tools
  • Interactive visualizations
• UNREAL , a GeomView module for "hand-drawing" mathematical objects, by Nina Amenta , Danek Duvall , and Tim Rowley
• Javier Elices 's GeomView module for visualizing the Dobkin-Kirkpatrick hierarchy
• Graphviz , tools for viewing and interacting with graph diagrams, by John Ellson , Eleftherios Koutsofios , andTopoVista : fly over USGS Digital Elevation Models , using right triangular irregular networks to maintain variable levels of detail, courtesy of Will Evans and Gregg Townsend . Requires OpenGL and Glut.
• DUST , a program for visualizing Voronoi diagrams, Delaunay triangulations, minimum spanning trees, and matchings in various metrics. From Michael Jünger's research group at Universität zu Köln.
• Peek by Gordon Kindlmann , a program for visualizing high-dimensional polytopes through their cross-sections and projections (or as Amenta and Ziegler would have it, their shadows and slices ).
• Cinderellas Café , a "dynamic geometry" Java program written by Ulrich Kortenkamp and Jürgen Richter-Gebert, dynamically maintains sets of geometric objects (points, lines, circles, and conics) as the user moves their defining points around, provides primal and polar views of the same objects, supports spherical and hyperbolic geometry, and even includes some automatic theorem proving! A demo version is available. Information is currently available in German only.
• Geomview , the Geometry Center's 3d geometric visualization program, written by Stuart Levy, Tamara Munzner, Mark Phillips, and a cast of thousands. Also available from a mirror site in Berlin .
• JGV , a successor to GeomView written in Java, also from the Geometry Center. (Java, source not available)
• Bob Lewis 's homogeneous coordinates and duality visualization program VideHoc (SGI executable only)
• Michael Murphy 's Ranger , a program for visualizing high-dimensional nearest neighbor and orthogonal range searching data structures. From Steve Skiena 's Practical Algorithm Reference
• The GeoPrO distributed visualization enviornment , by Pedro J. de Rezende , Guilherme Albuquerque Pinto , Alexandre Volpim , and Frederico Guth . (description only so far)
• Otfried Schwarzkopf 's extendible drawing editor Ipe
• Toposcope : Automatic visualization of the topology of 2D cell complexes by Jorge Stolfi , Rober Marcone Rosi , C. F. Xavier de Mendonça , and L. P. Lozada
• Shastra , a geometric modeling and visualization system being developed at Purdue University (descriptions only)
• Software on the Web , from the CNR-Pisa Visual Computing Group , includes code for volume visualization .
• ZEUS , an algorithm animation system developed at DEC SRC (Modula-3)

Other

• Algorithms for partitioning multi-dimensional data sets , collected by Charles Alpert
• DemoKin , a demonstration of kinetic data structures for convex hulls, closest pairs, Voronoi diagrams, and minimum spanning trees, by Julien Basch , Leo Guibas , Craig Silverstein , and Li Zhang . Requires LEDA , XForms , and OpenGL to compile; an SGI executable is available.
• MAXRAD : software to find the maximum radius sphere touching each point (atom) in a set (molecule) using inversion and convex hulls, by Todd Yeates . (FORTRAN)

miniorange

計算幾何的世界真的很大..

benchen

全是英文？

janless

额，有点看不懂

lixuezhizhi

楼主加油啊

benemorphy

小站建的很棒！

云浮

好多关于数学美的东西。。

Efron

额，有点看不懂

a1778188

支持楼主的练习，感觉不错～

Skdyo·L·Dns

楼主这般强大哦

liyuqun

很好很强大