Qhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection abou

Time 2021-11-22 06:05:59

Web Name: Qhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection abou

WebSite: http://www.qhull.org

ID:244869

Keywords:

Hull,Delaunay,Triangulation,Convex,Qhull,code,for,Intersection,

Description:

keywords:
description:
URL: http://www.qhull.org News Scholar Images GitHub
To:Download Readme Manual Programs Options FAQ Code Functions

Qhull Qhull computes the convex hull, Delaunay triangulation, Voronoi diagram,halfspace intersection about a point, furthest-site Delaunaytriangulation, and furthest-site Voronoi diagram. The source code runs in2-d, 3-d, 4-d, and higher dimensions. Qhull implements the Quickhullalgorithm for computing the convex hull. It handles roundofferrors from floating point arithmetic. It computes volumes,surface areas, and approximations to the convex hull.

Qhull does not support triangulation of non-convex surfaces, meshgeneration of non-convex objects, medium-sized inputs in 9-Dand higher, alpha shapes, weighted Voronoi diagrams, Voronoi volumes, orconstrained Delaunay triangulations,

If you call Qhull from your program, please use reentrant Qhull (libqhull_r or libqhullstatic_r).If you use Qhull 2003.1, please upgrade or apply poly.c-qh_gethash.patch.

Introduction Gregorius' talk on implementing Quickhull, Lloyd's QuickHull3D in Java, and Newbold's Waterman polyhedra Fukuda's introduction to convex hulls, Delaunay triangulations, Voronoi diagrams, and linear programming LEDA Guide to geometry algorithms MathWorld's Computational Geometry from Wolfram Research Skiena's Computational Geometry from his Algorithm Design Manual. Stony Brook Algorithm Repository, computational geometry

Qhull Documentation and Support Manual for Qhull and rbox Quick reference to Programs and Options When to use Qhull Description of Qhull Imprecision in Qhull qconvex -- convex hull qdelaunay -- Delaunay triangulation qvoronoi -- Voronoi diagram qhalf -- halfspace intersection about a point rbox -- generate point distributions README.txt - installation instructions
COPYING.txt - copyright notice
REGISTER.txt - registration
Geomview for visualizing Qhull FAQ - frequently asked questions about Qhull Changes.txt - change history
Qhull code Performance of Qhull Index to Qhull Functions Qhull build systems Send e-mail to qhull@qhull.org Report bugs to qhull_bug@qhull.org

Related URLs Amenta's directory of computational geometry software BGL Boost Graph Library provides C++ classes for graph data structuresand algorithms, CGAL and Ledalibraries for writing computationalgeometry programs and other combinatorial algorithms Clarkson's hull program with exact arithmetic for convex hulls, Delaunay triangulations, Voronoi volumes, and alpha shapes. Erickson's Computational Geometry Pages and Software Fukuda's cdd program for halfspace intersection and convex hulls (Polco/Java) Gartner's Miniball for fast and robust smallest enclosing balls (up to 20-d) Gold's Voronoi applications for spatial analysis (as of 2008) Mathtools.net of scientific and engineering software Owen's International Meshing Roundtable Schneiders' Finite Element Mesh Generation page Shewchuk's triangle program for 2-d Delaunay Teillaud's Computional Geometry Pages for the Society of Computational Geometry and academic conferences. Tomilov's quickhull.hpp (doc-ru) implements the Quickhull algorithm for points in general position. Young's Internet Finite Element Resources Zolotykh's Skeleton generates all extreme rays of a polyhedral cone using the Double Description Method

FAQs and Newsgroups FAQ for computer graphics algorithms FAQ for linear programming Newsgroup: comp.graphics.algorithms Newsgroup: comp.soft-sys.matlab Newsgroup: sci.math.num-analysis Newsgroup: sci.op-research

The program includes options for input transformations,randomization, tracing, multiple output formats, and executionstatistics. The program can be called from within yourapplication.

You can view the results in 2-d, 3-d and 4-d with Geomview. An alternativeis VTK.

For an article about Qhull, download from ACM or CiteSeer:

Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., The Quickhull algorithm for convex hulls, ACM Trans. on Mathematical Software, 22(4):469-483, Dec 1996, http://www.qhull.org

Abstract:

The convex hull of a set of points is the smallest convex set that contains the points. This article presents a practical convex hull algorithm that combines the two-dimensional Quickhull Algorithm with the general dimension Beneath-Beyond Algorithm. It is similar to the randomized, incremental algorithms for convex hull and Delaunay triangulation. We provide empirical evidence that the algorithm runs faster when the input contains non-extreme points, and that it uses less memory.

Computational geometry algorithms have traditionally assumed that input sets are well behaved. When an algorithm is implemented with floating point arithmetic, this assumption can lead to serious errors. We briefly describe a solution to this problem when computing the convex hull in two, three, or four dimensions. The output is a set of "thick" facets that contain all possible exact convex hulls of the input. A variation is effective in five or more dimensions.

Up: Past SoftwareProjects of the Geometry Center
URL: http://www.qhull.org News Scholar Images GitHub
To:Download Readme Manual Programs Options FAQ Code Functions

The Geometry Center Home Page

Comments to: qhull@qhull.org
Created: May 17 1995 ---

TAGS:Hull Delaunay Triangulation Convex Qhull code for Intersection 

<<< Thank you for your visit >>>

Hot Websites