www.archive-org-2014.com » ORG » Q » QHULL

Choose link from "Titles, links and description words view":

Or switch to "Titles and links view".

    Archived pages: 41 . Archive date: 2014-09.

  • Title: Qhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection about a Point
    Descriptive info: .. URL:.. http://www.. qhull.. org.. To:.. News.. Download.. CiteSeer.. Images.. Manual.. FAQ.. Programs.. Options.. Qhull.. Qhull computes the convex hull, Delaunay triangulation, Voronoi diagram, halfspace intersection about a point, furthest-site Delaunay triangulation, and furthest-site Voronoi diagram.. The source code runs in 2-d, 3-d, 4-d, and higher dimensions.. Qhull implements the Quickhull algorithm for computing the convex hull.. It handles roundoff errors from floating point arithmetic.. It computes volumes, surface areas, and approximations to the convex hull.. Qhull does.. not.. support triangulation of non-convex surfaces, mesh generation of non-convex objects, medium-sized inputs in 9-D and higher, alpha shapes, weighted Voronoi diagrams, Voronoi volumes, or constrained Delaunay triangulations,.. Qhull 2012.. 1 fixes qhull-go for Windows 64-bit.. If you use Qhull 2003.. 1.. please upgrade to 2012.. 1 or apply.. poly.. c-qh_gethash.. patch.. and.. Bugs.. about Qhull 2012.. 1 2012/02/18.. Examples.. of Qhull output.. Gitorious.. C++ interface to Qhull (.. wiki.. ,.. changes.. ).. www.. org.. How.. is Qhull used?.. Google Scholar.. references to Qhull.. Google.. Qhull,.. Books.. Patents.. Newsgroups.. Blogs.. , and.. Who is.. Qhull?.. MATLAB.. uses Qhull for their n-d computational geometry functions:.. convhulln.. delaunayn.. griddatan.. voronoin.. The.. geometry.. package of.. R.. provides.. Qhull in R.. Debian build.. of.. GNU Octave.. includes Qhull for computational geometry.. Mathematica.. 's Delaunay interface.. qh-math.. QHullInterface.. Geomview.. for 3-D and 4-D visualization of Qhull output.. Introduction.. Fukuda's introduction.. to convex hulls, Delaunay triangulations, Voronoi diagrams, and linear programming.. Lambert's Java.. visualization of convex hull algorithms.. 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.. for Qhull and rbox.. Description.. of Qhull.. quick reference.. qconvex.. -- convex hull.. qdelaunay.. -- Delaunay triangulation.. qvoronoi.. -- Voronoi diagram.. qhalf.. -- halfspace intersection about a point..  ...   Web Site.. for all things Voronoi.. 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.. for computer graphics algorithms (.. geometric.. structures).. FAQ.. for linear programming.. Newsgroup.. : comp.. graphics.. algorithms.. soft-sys.. matlab.. : sci.. math.. num-analysis.. op-research.. The program includes options for input transformations, randomization, tracing, multiple output formats, and execution statistics.. The program can be called from within your application.. You can view the results in 2-d, 3-d and 4-d with.. An alternative is.. VTK.. For an article about Qhull, download from.. ACM.. or.. :.. 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.. 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 Software Projects of the Geometry Center.. The Geometry Center Home Page.. Comments to:.. Created: May 17 1995 ---..

    Original link path: /
    Open archive

  • Title: Qhull manual
    Descriptive info: Home page.. for Qhull.. about Qhull.. Qhull manual: Table of Contents.. (please wait while loading).. Output.. Formats.. Print.. Precision.. Trace.. Qhull manual.. Qhull is a general dimension code for computing convex hulls, Delaunay triangulations, halfspace intersections about a point, Voronoi diagrams, furthest-site Delaunay triangulations, and furthest-site Voronoi diagrams.. These structures have applications in science, engineering, statistics, and mathematics.. See.. For a detailed introduction, see O'Rourke [.. '94.. ],.. Computational Geometry in C.. There are six programs.. Except for rbox, they use the same code.. -- convex hulls.. -- Delaunay triangulations and furthest-site Delaunay triangulations.. -- halfspace intersections about a point.. qhull.. -- all structures with additional options.. -- Voronoi diagrams and furthest-site Voronoi diagrams.. -- generate point distributions for qhull.. Qhull includes options for hull volume, facet area, multiple output formats, and graphical output.. It can approximate a convex hull.. Qhull handles roundoff errors from floating point arithmetic.. It generates a convex hull with "thick" facets.. A facet's outer plane is clearly above all of the points; its inner plane is clearly below the facet's vertices.. Any exact convex hull must lie between the inner and outer plane.. Qhull uses merged facets, triangulated output, or joggled input.. Triangulated output triangulates non-simplicial, merged facets.. Joggled input also guarantees simplicial output, but it is less accurate than merged facets.. For merged facets, Qhull reports the maximum outer and inner plane.. Brad Barber, Arlington, MA.. Copyright 1995-2012 C.. Barber.. Qhull manual: Table of Contents.. When.. to use Qhull.. for Qhull with new features and reported bugs.. Home.. for Qhull with additional URLs (.. local copy.. for Qhull (.. Qhull (.. Quick.. reference for Qhull and its.. options.. - Unix manual page.. de.. finition.. in.. put.. ou.. tput.. al.. gorithm.. da.. ta structure.. Imprecision.. in Qhull.. Merged facets.. or joggled input.. , Qhull's graphical viewer.. Examples.. of Qhull using Geomview.. Qhull programs.. Related URLs.. for computer graphics algorithms and.. structures.. Amenta's.. Directory of Computational Geometry Software.. Erickson's.. Computational Geometry Software.. Fukuda's.. introduction.. Stony Brook's.. Algorithm Repository.. on computational geometry.. Qhull options.. formats.. Additional.. I/O formats.. output options.. control options.. Qhull internals.. Performance.. of Qhull.. Calling.. Qhull from your program.. Enhancements.. to Qhull.. Qhull functions, macros, and data structures.. What to do.. if something goes wrong.. Email.. Authors.. References.. Acknowledgments.. When to use Qhull.. Qhull constructs convex hulls, Delaunay triangulations, halfspace intersections about a point, Voronoi diagrams, furthest-site Delaunay triangulations, and furthest-site Voronoi diagrams.. For convex hulls and halfspace intersections, Qhull may be used for 2-d upto 8-d.. For Voronoi diagrams and Delaunay triangulations, Qhull may be used for 2-d upto 7-d.. In higher dimensions, the size of the output grows rapidly and Qhull does not work well with virtual memory.. If.. n.. is the size of the input and.. d.. is the dimension (d>=3), the size of the output and execution time grows by.. n^(floor(d/2).. [see.. ].. For example, do not try to build a 16-d convex hull of 1000 points.. It will have on the order of 1,000,000,000,000,000,000,000,000 facets.. On a 600 MHz Pentium 3, Qhull computes the 2-d convex hull of 300,000 cocircular points in 11 seconds.. It computes the 2-d Delaunay triangulation and 3-d convex hull of 120,000 points in 12 seconds.. It computes the 3-d Delaunay triangulation and 4-d convex hull of 40,000 points in 18 seconds.. It computes the 4-d Delaunay triangulation and 5-d convex hull of 6,000 points in 12 seconds.. It computes the 5-d Delaunay triangulation and 6-d convex hull of 1,000 points in 12 seconds.. It computes the 6-d Delaunay triangulation and 7-d convex hull of 300 points in 15 seconds.. It computes the 7-d Delaunay triangulation and 8-d convex hull of 120 points in 15 seconds.. It computes the 8-d Delaunay triangulation and 9-d convex hull of 70 points in 15 seconds.. It computes the 9-d Delaunay triangulation and 10-d convex hull of 50 points in 17 seconds.. The 10-d convex hull of 50 points has about 90,000 facets.. support constrained Delaunay triangulations, triangulation of non-convex surfaces, mesh generation of non-convex objects, or medium-sized inputs in 9-D and higher.. This is a big package with many options.. It is one of the fastest available.. It is the only 3-d code that handles precision problems due to floating point arithmetic.. For example, it implements the identity function for extreme points (see.. Imprecision in Qhull.. ).. If you need a short code for convex hull, Delaunay triangulation, or Voronoi volumes consider Clarkson's.. hull program.. If you need 2-d Delaunay triangulations consider Shewchuk's.. triangle program.. It is much faster than Qhull and it allows constraints.. Both programs use exact arithmetic.. They are in.. netlib.. org/voronoi/.. Qhull.. version 1.. 0.. may also meet your needs.. It detects precision problems, but does not handle them.. is a library for writing computational geometry programs and other combinatorial algorithms.. It includes routines for computing 3-d convex hulls, 2-d Delaunay triangulations, and 3-d Delaunay triangulations.. It provides rational arithmetic and graphical output.. It runs on most platforms.. If your problem is in high dimensions with a few, non-simplicial facets, try Fukuda's.. cdd.. It is much faster than Qhull for these distributions.. Custom software for 2-d and 3-d convex hulls may be faster than Qhull.. Custom software should use less memory.. Qhull uses general-dimension data structures and code.. The data structures support non-simplicial facets.. Qhull is not suitable for mesh generation or triangulation of arbitrary surfaces.. You may use Qhull if the surface is convex or completely visible from an interior point (e.. g.. , a star-shaped polyhedron).. First, project each site to a sphere that is centered at the interior point.. Then, compute the convex hull of the projected sites.. The facets of the convex hull correspond to a triangulation of the surface.. For mesh generation of arbitrary surfaces, see.. Schneiders' Finite Element Mesh Generation.. Qhull is not suitable for constrained Delaunay triangulations.. With a lot of work, you can write a program that uses Qhull to add constraints by adding additional points to the triangulation.. Qhull is not suitable for the subdivision of arbitrary objects.. Use.. to subdivide a convex object.. Description of Qhull.. definition.. convex hull.. of a point set.. P.. is the smallest convex set that contains.. is finite, the convex hull defines a matrix.. A.. and a vector.. b.. such that for all.. x.. in.. Ax+b = [0,.. ].. Qhull computes the convex hull in 2-d, 3-d, 4-d, and higher dimensions.. Qhull represents a convex hull as a list of facets.. Each facet has a set of vertices, a set of neighboring facets, and a halfspace.. A halfspace is defined by a  ...   an inner plane.. The ridges determine a set of neighboring facets, a set of vertices, and an orientation.. Qhull produces a non-simplicial facet when it merges two facets together.. For example, a cube has six non-simplicial facets.. For examples, use option '.. f.. polyhedron operations.. for further design documentation.. Geomview, Qhull's graphical viewer.. is an interactive geometry viewing program for Linux, SGI workstations, Sun workstations, AIX workstations, NeXT workstations, and X-windows.. It is an.. open source project.. under SourceForge.. Besides a 3-d viewer, it includes a 4-d viewer, an n-d viewer and many features for viewing mathematical objects.. You may need to ftp.. ndview.. from the.. newpieces.. directory.. Description of Qhull examples.. Some of the examples have.. pictures.. Options for using Qhull.. Qhull internals.. Internals.. What to do if something goes wrong.. Please report bugs to.. Please report if Qhull crashes.. Please report if Qhull generates an internal error.. Please report if Qhull produces a poor approximate hull in 2-d, 3-d or 4-d.. Please report documentation errors.. Please report missing or incorrect links.. If you do not understand something, try a small example.. program is an easy way to generate test cases.. program helps to visualize the output from Qhull.. If Qhull does not compile, it is due to an incompatibility between your system and ours.. The first thing to check is that your compiler is ANSI standard.. Qhull produces a compiler error if __STDC__ is not defined.. You may need to set a flag (e.. , '-A' or '-ansi').. If Qhull compiles but crashes on the test case (rbox D4), there's still incompatibility between your system and ours.. Sometimes it is due to memory management.. This can be turned off with qh_NOmem in mem.. h.. Please let us know if you figure out how to fix these problems.. If you doubt the output from Qhull, add option '.. Tv.. It checks that every point is inside the outer planes of the convex hull.. It checks that every facet is convex with its neighbors.. It checks the topology of the convex hull.. Qhull should work on all inputs.. It may report precision errors if you turn off merged facets with option '.. Q0.. This can get as bad as facets with flipped orientation or two facets with the same vertices.. You'll get a long help message if you run into such a case.. They are easy to generate with.. If you do find a problem, try to simplify it before reporting the error.. Try different size inputs to locate the smallest one that causes an error.. You're welcome to hunt through the code using the execution trace ('.. T4.. ') as a guide.. This is especially true if you're incorporating Qhull into your own program.. When you report an error, please attach a data set to the end of your message.. Include the options that you used with Qhull, the results of option '.. ', and any messages generated by Qhull.. This allows me to see the error for myself.. Qhull is maintained part-time.. Please send correspondence to Brad Barber at.. and report bugs to.. Let me know how you use Qhull.. If you mention it in a paper, please send a reference and abstract.. If you would like to get Qhull announcements (e.. , a new version) and news (any bugs that get fixed, etc.. ), let us know and we will add you to our mailing list.. If you would like to communicate with other Qhull users, I will add you to the qhull_users alias.. For Internet news about geometric algorithms and convex hulls, look at comp.. algorithms and sci.. num-analysis.. For Qhull news look at.. qhull-news.. html.. C.. Bradford Barber Hannu Huhdanpaa bradb@shore.. net hannu@qhull.. A special thanks to David Dobkin for his guidance.. A special thanks to Albert Marden, Victor Milenkovic, the Geometry Center, and Harvard University for supporting this work.. A special thanks to Mark Phillips, Robert Miner, and Stuart Levy for running the Geometry Center web site long after the Geometry Center closed.. Stuart moved the web site to the University of Illinois at Champaign-Urbana.. Mark and Robert are founders of.. Geometry Technologies.. Mark, Stuart, and Tamara Munzner are the original authors of.. A special thanks to.. Endocardial Solutions, Inc.. of St.. Paul, Minnesota for their support of the internal documentation (.. src/libqhull/index.. htm.. They use Qhull to build 3-d models of heart chambers.. Qhull 1.. 0 and 2.. 0 were developed under National Science Foundation grants NSF/DMS-8920161 and NSF-CCR-91-15793 750-7504.. If you find it useful, please let us know.. The Geometry Center was supported by grant DMS-8920161 from the National Science Foundation, by grant DOE/DE-FG02-92ER25137 from the Department of Energy, by the University of Minnesota, and by Minnesota Technology, Inc.. Aurenhammer.. , F.. , Voronoi diagrams -- A survey of a fundamental geometric data structure,.. ACM Computing Surveys.. , 1991, 23:345-405.. , C.. B.. , D.. Dobkin, and H.. Huhdanpaa, The Quickhull Algorithm for Convex Hulls,.. ACM Transactions on Mathematical Software.. , 22(4):469-483, Dec 1996, www.. org [.. http://portal.. acm.. ;.. http://citeseerx.. ist.. psu.. edu.. Clarkson.. , K.. L.. and P.. W.. Shor, Applications of random sampling in computational geometry, II ,.. Discrete Computational Geometry.. , 4:387-421, 1989.. , K.. Mehlhorn, and R.. Seidel, Four results on randomized incremental construction,.. Computational Geometry: Theory and Applications.. , vol.. 3, p.. 185-211, 1993.. Devillers.. , et.. , "Walking in a triangulation,".. ACM Symposium on Computational Geometry.. , June 3-5,2001, Medford MA.. Dobkin.. , D.. and D.. G.. Kirkpatrick, Determining the separation of preprocessed polyhedra--a unified approach, in.. Proc.. 17th Inter.. Colloq.. Automata Lang.. Program.. , in.. Lecture Notes in Computer Science.. , Springer-Verlag, 443:400-413, 1990.. Edelsbrunner.. , H,.. Geometry and Topology for Mesh Generation.. , Cambridge University Press, 2001.. Gartner, B.. , "Fast and robust smallest enclosing balls",.. Algorithms - ESA '99.. , LNCS 1643.. Fortune, S.. , Computational geometry, in R.. Martin, editor,.. Directions in Geometric Computation.. , Information Geometers, 47 Stockers Avenue, Winchester, SO22 5LB, UK, ISBN 1-874728-02-X, 1993.. Milenkovic, V.. , Robust polygon modeling, Computer-Aided Design, vol.. 25, p.. 546-566, September 1993.. Mucke.. , E.. , I.. Saias, B.. Zhu,.. Fast randomized point location without preprocessing in Two- and Three-dimensional Delaunay Triangulations.. , ACM Symposium on Computational Geometry, p.. 274-283, 1996 [.. GeomDir.. Mulmuley.. Computational Geometry, An Introduction Through Randomized Algorithms.. , Prentice-Hall, NJ, 1994.. O'Rourke.. , J.. , Cambridge University Press, 1994.. Preparata.. and M.. Shamos,.. Computational Geometry.. , Springer-Verlag, New York, 1985.. Qhull manual.. : Table of Contents.. Dn:.. The Geometry Center Home Page.. Created: Sept.. 25, 1995 --- Last modified: see top..

    Original link path: /html/index.htm
    Open archive

  • Title: Qhull quick reference
    Descriptive info: Home page for Qhull.. , macros, and data structures.. Qhull files.. Geom.. Global.. Io.. Mem.. Merge.. Poly.. Set.. Stat.. User.. Qhull quick reference.. This section lists all programs and options in Qhull.. -- convex hull.. sy.. nopsis.. tputs.. co.. ntrols.. gr.. aphics.. no.. tes.. nventions.. op.. tions.. -- Delaunay triangulation.. qdelaunay Qu.. -- furthest-site Delaunay triangulation.. -- halfspace intersection about a point.. -- Voronoi diagram.. qvoronoi Qu.. -- furthest-site Voronoi diagram.. -- generate point distributions for qhull.. ex.. amples.. -- convex hull and related structures.. Fa.. ' Farea.. FA.. ' FArea-total.. Fc.. ' Fcoplanars.. FC.. ' FCentrums.. Fd.. ' Fd-cdd-in.. FD.. ' FD-cdd-out.. FF.. ' FF-dump-xridge.. Fi.. ' Finner.. ' Finner_bounded.. FI.. ' FIDs.. Fm.. ' Fmerges.. FM.. ' FMaple.. Fn.. ' Fneighbors.. FN.. ' FNeigh-vertex.. Fo.. ' Fouter.. ' Fouter_unbounded.. ' FOptions.. Fp.. ' Fpoint-intersect.. FP.. ' FPoint_near.. ' FQhull.. Fs.. ' Fsummary.. FS.. ' FSize.. Ft.. ' Ftriangles.. Fv.. ' Fvertices.. ' Fvoronoi.. FV.. ' FVertex-ave.. Fx.. ' Fxtremes.. Merged facets or joggled input.. PAn.. ' PArea-keep.. ' Pdrop_low.. PDk:n.. ' Pdrop_high.. Pg.. ' Pgood.. PFn.. '  ...   Ghyperplanes.. Gr.. ' Gridges.. Go.. ' Gouter.. GDn.. ' GDrop_dim.. Gt.. ' Gtransparent.. ' T4_trace.. Tc.. ' Tcheck_often.. Ts.. ' Tstatistics.. ' Tverify.. Tz.. ' Tz_stdout.. TFn.. ' TFacet_log.. ' TInput_file.. TPn.. ' TPoint_trace.. TMn.. ' TMerge_trace.. ' TOutput_file.. TRn.. ' TRerun.. TWn.. ' TWide_trace.. TV-n.. ' TVertex_stop_before.. TVn.. ' TVertex_stop_after.. TCn.. ' TCone_stop_after.. A-n.. ' Angle_max_pre.. An.. ' Angle_max_post.. ' Centrum_roundoff.. C-n.. ' Centrum_size_pre.. Cn.. ' Centrum_size_post.. En.. ' Error_round.. Rn.. ' Random_dist.. Vn.. ' Visible_min.. Un.. ' Ucoplanar_max.. Wn.. ' Wide_outside.. ' Qbound_low.. QBk:n.. ' QBound_high.. Qbk:0Bk:0.. ' Qbound_drop.. QbB.. ' QbB-scale-box.. Qbb.. ' Qbb-scale-last.. Qc.. ' Qcoplanar.. Qf.. ' Qfurthest.. Qg.. ' Qgood_only.. QGn.. ' QGood_point.. Qi.. ' Qinterior.. Qm.. ' Qmax_out.. QJn.. ' QJoggle.. Qr.. ' Qrandom.. QRn.. ' QRotate.. Qs.. ' Qsearch_1st.. Qt.. ' Qtriangulate.. Qu.. ' QupperDelaunay.. QVn.. ' QVertex_good.. Qv.. ' Qvneighbors.. ' Qxact_merge.. Qz.. ' Qzinfinite.. ' Q0_no_premerge.. Q1.. ' Q1_no_angle.. Q2.. ' Q2_no_independ.. Q3.. ' Q3_no_redundant.. Q4.. ' Q4_no_old.. Q5.. ' Q5_no_check_out.. Q6.. ' Q6_no_concave.. Q7.. ' Q7_depth_first.. Q8.. ' Q8_no_near_in.. Q9.. ' Q9_pick_furthest.. Q10.. ' Q10_no_narrow.. Q11.. ' Q11_trinormals..

    Original link path: /html/qh-quick.htm
    Open archive

  • Title: qconvex -- convex hull
    Descriptive info: Up.. :.. -- Table of Contents.. tions.. qconvex -- convex hull.. The convex hull of a set of points is the smallest convex set containing the points.. See the detailed introduction by O'Rourke [.. Description of Qhull.. Example:.. rbox 10 D3 | qconvex.. TO result.. Compute the 3-d convex hull of 10 random points.. Write a summary to the console and the points and facets to 'result'.. rbox c | qconvex.. Print the normals for each facet of a cube.. Print the triangulated facets of a cube.. rbox y 500 W0 | qconvex.. Compute the convex hull of a simplex with 500 points on its surface.. rbox x W1e-12 1000 | qconvex.. QR0.. Compute the convex hull of 1000 points near the surface of a randomly rotated simplex.. Report the maximum thickness of a facet.. rbox 1000 s | qconvex.. Compute the convex hull of 1000 cospherical points.. Verify the results and print a summary with the total area and volume.. rbox d D12 | qconvex.. Compute the convex hull of a 12-d diamond.. Randomly rotate the input.. Note the large number of facets and the small volume.. rbox c D7 | qconvex.. TF1000.. Compute the convex hull of the 7-d hypercube.. Report on progress every 1000 facets.. Computing the convex hull of the 9-d hypercube takes too much time and space.. rbox c d D2 | qconvex.. | more.. Dump all fields of all facets for a square and a diamond.. Also print a summary and a list of vertices.. Note the coplanar points.. Except for rbox, all of the qhull programs compute a convex hull.. By default, Qhull merges coplanar facets.. For example, the convex hull of a cube's vertices has six facets.. If you use '.. ' (triangulated output), all facets will be simplicial (e.. , triangles in 2-d).. For the cube example, it will have 12 facets.. Some facets may be degenerate and have zero area.. ' (joggled input), all facets will be simplicial.. The corresponding vertices will be slightly perturbed and identical points will be joggled apart.. Joggled input is less accurate that triangulated output.. See.. The output for 4-d convex hulls may be confusing if the convex hull contains non-simplicial facets (e.. , a hypercube).. Why are there extra points in a 4-d or higher convex hull?.. The 'qconvex' program is equivalent to '.. ' in 2-d to 4-d, and '.. ' in 5-d and higher.. It disables the following Qhull.. d v H Qbb Qf Qg Qm Qr Qu Qv Qx Qz TR E V Fp Gt Q0,etc.. qconvex synopsis.. qconvex- compute the convex hull.. input (stdin): dimension, number of points, point coordinates comments start with a non-numeric character options (qconvex.. htm): Qt - triangulated output QJ - joggle input instead of merging facets Tv - verify result: structure, convexity, and point inclusion.. - concise list of all options - - one-line description of all options output options (subset): s - summary of results (default) i - vertices incident to each facet n - normals with offsets p - vertex coordinates (includes coplanar points if 'Qc') Fx - extreme points (convex hull vertices) FA - compute total area and volume o - OFF format (dim, n, points, facets) G - Geomview output (2-d, 3-d, and 4-d) m - Mathematica output (2-d and 3-d) QVn - print facets that include point n, -n if not TO file- output results to file, may be enclosed in single quotes examples: rbox c D2 | qconvex s n rbox c D2 | qconvex i rbox c D2 | qconvex o rbox 1000 s | qconvex s Tv FA rbox c d D2 | qconvex s Qc Fx rbox y 1000 W0 | qconvex s n rbox y 1000 W0 | qconvex s QJ rbox d G1 D12 | qconvex QR0 FA Pp rbox c D7 | qconvex FA TF1000.. qconvex input.. dimension.. number of points.. point coordinates.. Use I/O redirection (e.. , qconvex data.. txt), a pipe (e.. , rbox 10 | qconvex), or the '.. TI.. ' option (e.. , qconvex TI data.. txt).. Comments start with a non-numeric character.. Error reporting is simpler if there is one point per line.. Dimension and number of points may be reversed.. Here is the input for computing the convex hull of the unit cube.. The output is the normals, one per facet.. rbox c data.. 3 RBOX c 8 -0.. 5 -0.. 5 0.. 5.. qconvex s n data.. Convex hull of 8 points in 3-d: Number of vertices: 8 Number of facets: 6 Number of non-simplicial facets: 6 Statistics for: RBOX c | QCONVEX s n Number of points processed: 8 Number of hyperplanes created: 11 Number of distance tests for qhull: 35 Number of merged facets: 6 Number of distance tests for merging: 84 CPU seconds to compute hull (after input): 0.. 081 4 6 0 0 -1 -0.. 5 0 -1 0 -0.. 5 1 0 0 -0.. 5 -1 0 0 -0.. 5 0 1 0 -0.. 5 0 0 1 -0.. qconvex outputs.. These options control the output of qconvex.. They may be used individually or together.. Vertices.. list extreme points (i.. , vertices).. The first line is the number of extreme points.. Each point is listed, one per line.. The cube example has eight vertices.. list vertices for each facet.. The first line is the number of facets.. Each remaining line starts with the number of vertices.. For the cube example, each facet has four vertices.. The remaining lines list the vertices for each facet.. In 4-d and higher, triangulate non-simplicial facets by adding an extra point..  ...   drop dimension 2.. qconvex notes.. Qhull always computes a convex hull.. The convex hull may be used for other geometric structures.. The general technique is to transform the structure into an equivalent convex hull problem.. For example, the Delaunay triangulation is equivalent to the convex hull of the input sites after lifting the points to a paraboloid.. qconvex conventions.. The following terminology is used for convex hulls in Qhull.. Qhull's data structures.. -.. - extreme point of the input set.. vertices between two neighboring facets.. - halfspace defined by a unit normal and offset.. coplanar point.. - a nearly incident point to a hyperplane.. - a point on the hyperplane for testing convexity.. facet.. - a facet with vertices, ridges, coplanar points, neighboring facets, and hyperplane.. - a facet with.. vertices,.. ridges, and.. neighbors.. - a facet with more than.. vertices.. good facet.. - a facet selected by '.. qconvex options.. qconvex- compute the convex hull http://www.. org input (stdin): first lines: dimension and number of points (or vice-versa).. other lines: point coordinates, best if one point per line comments: start with a non-numeric character options: Qt - triangulated output QJ - joggle input instead of merging facets Qc - keep coplanar points with nearest facet Qi - keep interior points with nearest facet Qhull control options: Qbk:n - scale coord k so that low bound is n QBk:n - scale coord k so that upper bound is n (QBk is 0.. 5) QbB - scale input to unit cube centered at the origin Qbk:0Bk:0 - remove k-th coordinate from input QJn - randomly joggle input in range [-n,n] QRn - random rotation (n=seed, n=0 time, n=-1 time/no rotate) Qs - search all points for the initial simplex QGn - good facet if visible from point n, -n for not visible QVn - good facet if it includes point n, -n if not Trace options: T4 - trace at level n, 4=all, 5=mem/gauss, -1= events Tc - check frequently during execution Ts - print statistics Tv - verify result: structure, convexity, and point inclusion Tz - send all output to stdout TFn - report summary when n or more facets created TI file - input data from file, no spaces or single quotes TO file - output results to file, may be enclosed in single quotes TPn - turn on tracing when point n added to hull TMn - turn on tracing at merge n TWn - trace merge facets when width > n TVn - stop qhull after adding point n, -n for before (see TCn) TCn - stop qhull after building cone for point n (see TVn) Precision options: Cn - radius of centrum (roundoff added).. Merge facets if non-convex An - cosine of maximum angle.. Merge facets if cosine > n or non-convex C-0 roundoff, A-0.. 99/C-0.. 01 pre-merge, A0.. 99/C0.. 01 post-merge Rn - randomly perturb computations by a factor of [1-n,1+n] Un - max distance below plane for a new, coplanar point Wn - min facet width for outside point (before roundoff) Output formats (may be combined; if none, produces a summary to stdout): f - facet dump G - Geomview output (see below) i - vertices incident to each facet m - Mathematica output (2-d and 3-d) n - normals with offsets o - OFF file format (dim, points and facets; Voronoi regions) p - point coordinates s - summary (stderr) More formats: Fa - area for each facet FA - compute total area and volume for option 's' Fc - count plus coplanar points for each facet use 'Qc' (default) for coplanar and 'Qi' for interior FC - centrum for each facet Fd - use cdd format for input (homogeneous with offset first) FD - use cdd format for numeric output (offset first) FF - facet dump without ridges Fi - inner plane for each facet FI - ID for each facet Fm - merge count for each facet (511 max) FM - Maple output (2-d and 3-d) Fn - count plus neighboring facets for each facet FN - count plus neighboring facets for each point Fo - outer plane (or max_outside) for each facet FO - options and precision constants FP - nearest vertex for each coplanar point FQ - command used for qconvex Fs - summary: #int (8), dimension, #points, tot vertices, tot facets, for output: #vertices, #facets, #coplanar points, #non-simplicial facets #real (2), max outer plane, min vertex FS - sizes: #int (0) #real(2) tot area, tot volume Ft - triangulation with centrums for non-simplicial facets (OFF format) Fv - count plus vertices for each facet FV - average of vertices (a feasible point for 'H') Fx - extreme points (in order for 2-d) Geomview output (2-d, 3-d, and 4-d) Ga - all points as dots Gp - coplanar points and vertices as radii Gv - vertices as spheres Gi - inner planes only Gn - no planes Go - outer planes only Gc - centrums Gh - hyperplane intersections Gr - ridges GDn - drop dimension n in 3-d and 4-d output Print options: PAn - keep n largest facets by area Pdk:n - drop facet if normal[k] = n (default 0.. 0) PDk:n - drop facet if normal[k] >= n Pg - print good facets (needs 'QGn' or 'QVn') PFn - keep facets whose area is at least n PG - print neighbors of good facets PMn - keep n facets with most merges Po - force output.. If error, output neighborhood of facet Pp - do not report precision problems.. - list of all options - - one line descriptions of all options..

    Original link path: /html/qconvex.htm
    Open archive

  • Title: qdelaunay -- Delaunay triangulation
    Descriptive info: qdelaunay -- Delaunay triangulation.. The Delaunay triangulation is the triangulation with empty circumspheres.. It has many useful properties and applications.. See the survey article by Aurenhammer [.. '91.. ] and the detailed introduction by O'Rourke [.. rbox r y c G0.. 1 D2 | qdelaunay.. Compute the 2-d Delaunay triangulation of a triangle and a small square.. Write a summary to the console and unoriented regions to 'result'.. Merge regions for cocircular input sites (i.. , the square).. Write a summary and unoriented regions to the console.. Produce triangulated output.. rbox 10 D2 | qdelaunay.. Compute the 2-d Delaunay triangulation of 10 random points.. Joggle the input to guarantee triangular output.. Write a summary to the console and the regions to 'result'.. Qhull computes the Delaunay triangulation by computing a convex hull.. It lifts the input sites to a paraboloid by adding the sum of the squares of the coordinates.. It scales the height of the paraboloid to improve numeric precision ('.. It computes the convex hull of the lifted sites, and projects the lower convex hull to the input.. Each region of the Delaunay triangulation corresponds to a facet of the lower half of the convex hull.. Facets of the upper half of the convex hull correspond to the.. furthest-site Delaunay triangulation.. See the examples,.. Delaunay and Voronoi diagrams.. Qhull FAQ.. - Delaunay and Voronoi diagram questions.. By default, qdelaunay merges cocircular and cospherical regions.. For example, the Delaunay triangulation of a square inside a diamond ('rbox D2 c d G4 | qdelaunay') contains one region for the square.. ' if the input is circular, cospherical, or nearly so.. It improves precision by adding a point "at infinity," above the corresponding paraboloid.. ' (triangulated output), all Delaunay regions will be simplicial (e.. Some regions may be degenerate and have zero area.. Triangulated output identifies coincident points.. ' (joggled input), all Delaunay regions will be simplicial (e.. Coincident points will create small regions since the points are joggled apart.. Joggled input is less accurate than triangulated output ('Qt').. The output for 3-d Delaunay triangulations may be confusing if the input contains cospherical data.. See the FAQ item.. Avoid these problems with triangulated output ('.. ') or joggled input ('.. The 'qdelaunay' program is equivalent to '.. qhull d.. ' in 2-d to 3-d, and '.. ' in 4-d and higher.. d n v H U Qb QB Qc Qf Qg Qi Qm Qr QR Qv Qx TR E V FC Fi Fo Fp Ft FV Q0,etc.. qdelaunay synopsis.. qdelaunay- compute the Delaunay triangulation.. input (stdin): dimension, number of points, point coordinates comments start with a non-numeric character options (qdelaun.. htm): Qt - triangulated output QJ - joggle input instead of merging facets Qu - furthest-site Delaunay triangulation Tv - verify result: structure, convexity, and in-circle test.. - concise list of all options - - one-line description of all options output options (subset): s - summary of results (default) i - vertices incident to each Delaunay region Fx - extreme points (vertices of the convex hull) o - OFF format (shows the points lifted to a paraboloid) G - Geomview output (2-d and 3-d points lifted to a paraboloid) m - Mathematica output (2-d inputs lifted to a paraboloid) QVn - print Delaunay regions that include point n, -n if not TO file- output results to file, may be enclosed in single quotes examples: rbox c P0 D2 | qdelaunay s o rbox c P0 D2 | qdelaunay i rbox c P0 D3 | qdelaunay Fv Qt rbox c P0 D2 | qdelaunay s Qu Fv rbox c G1 d D2 | qdelaunay s i rbox c G1 d D2 | qdelaunay s i Qt rbox M3,4 z 100 D2 | qdelaunay s rbox M3,4 z 100 D2 | qdelaunay s Qt.. qdelaunay input.. , qdelaunay data.. , rbox 10 | qdelaunay), or the '.. , qdelaunay TI data.. For example, this is four cocircular points inside a square.. Its Delaunay triangulation contains 8 triangles and one four-sided figure.. rbox s 4 W0 c G1 D2 data.. 2 RBOX s 4 W0 c D2 8 -0.. 4941988586954018 -0.. 07594397977563715 -0.. 06448037284989526 0.. 4958248496365813 0.. 4911154367094632 0.. 09383830681375946 -0.. 348353580869097 -0.. 3586778257652367 -1 -1 -1 1 1 -1 1 1.. qdelaunay s i data.. Delaunay triangulation by the convex hull of 8 points in 3-d Number of input sites: 8 Number of Delaunay regions: 9 Number of non-simplicial Delaunay regions: 1 Statistics for: RBOX s 4 W0 c D2 | QDELAUNAY s i Number of points processed: 8 Number of hyperplanes created: 18 Number of facets in hull: 10 Number of distance tests for qhull: 33 Number of merged facets: 2 Number of distance tests for merging: 102 CPU seconds to compute hull (after input): 0.. 028 9 1 7 5 6 3 4 2 3 6 7 2 6 2 7 1 0 5 4 3 0 4 0 1 5 1 0 3 2.. qdelaunay outputs.. These options control the output of Delaunay triangulations:.. Delaunay regions.. list input sites for each Delaunay region.. The first line is the number of regions.. The remaining lines list the input sites for each region.. The regions are oriented.. In 3-d and higher, report cospherical sites by adding extra points.. Use triangulated output ('.. ') to avoid non-simpicial regions.. For the circle-in-square example, eight Delaunay regions are triangular and the ninth has four input sites.. Each remaining line starts with the number of input sites.. The regions are unoriented.. list neighboring regions for each Delaunay region..  ...   these scale the last coordinate.. If a point is interior to the convex hull of the input set, it is interior to the adjacent vertices of the Delaunay triangulation.. This is demonstrated by the following pipe for point 0:.. qdelaunay data s FQ QV0 p | qconvex s Qb3:0B3:0 p.. The first call to qdelaunay returns the neighboring points of point 0 in the Delaunay triangulation.. The second call to qconvex returns the vertices of the convex hull of these points (after dropping the lifted coordinate).. If point 0 is interior to the original point set, it is interior to the reduced point set.. qdelaunay conventions.. The following terminology is used for Delaunay triangulations in Qhull for dimension.. The underlying structure is the lower facets of a convex hull in dimension.. d+1.. For further information, see.. convex hull conventions.. input site.. - a point in the input (one dimension lower than a point on the convex hull).. - a point has.. The last coordinate is the sum of the squares of the input site's coordinates.. - a.. coincident.. input site or a deleted vertex.. - a point on the paraboloid.. It corresponds to a unique input site.. point-at-infinity.. - a point added above the paraboloid by option '.. lower facet.. - a facet corresponding to a Delaunay region.. The last coefficient of its normal is clearly negative.. upper facet.. - a facet corresponding to a furthest-site Delaunay region.. The last coefficient of its normal is clearly positive.. Delaunay region.. - a lower facet projected to the input sites.. upper Delaunay region.. - an upper facet projected to the input sites.. - more than.. input sites are cocircular or cospherical.. - a Delaunay region with optional restrictions by '.. qdelaunay options.. qdelaunay- compute the Delaunay triangulation http://www.. other lines: point coordinates, best if one point per line comments: start with a non-numeric character options: Qt - triangulated output QJ - joggle input instead of merging facets Qu - compute furthest-site Delaunay triangulation Qhull control options: QJn - randomly joggle input in range [-n,n] Qs - search all points for the initial simplex Qz - add point-at-infinity to Delaunay triangulation QGn - print Delaunay region if visible from point n, -n if not QVn - print Delaunay regions that include point n, -n if not Trace options: T4 - trace at level n, 4=all, 5=mem/gauss, -1= events Tc - check frequently during execution Ts - print statistics Tv - verify result: structure, convexity, and in-circle test Tz - send all output to stdout TFn - report summary when n or more facets created TI file - input data from file, no spaces or single quotes TO file - output results to file, may be enclosed in single quotes TPn - turn on tracing when point n added to hull TMn - turn on tracing at merge n TWn - trace merge facets when width > n TVn - stop qhull after adding point n, -n for before (see TCn) TCn - stop qhull after building cone for point n (see TVn) Precision options: Cn - radius of centrum (roundoff added).. 01 post-merge Rn - randomly perturb computations by a factor of [1-n,1+n] Wn - min facet width for outside point (before roundoff) Output formats (may be combined; if none, produces a summary to stdout): f - facet dump G - Geomview output (see below) i - vertices incident to each Delaunay region m - Mathematica output (2-d only, lifted to a paraboloid) o - OFF format (dim, points, and facets as a paraboloid) p - point coordinates (lifted to a paraboloid) s - summary (stderr) More formats: Fa - area for each Delaunay region FA - compute total area for option 's' Fc - count plus coincident points for each Delaunay region Fd - use cdd format for input (homogeneous with offset first) FD - use cdd format for numeric output (offset first) FF - facet dump without ridges FI - ID of each Delaunay region Fm - merge count for each Delaunay region (511 max) FM - Maple output (2-d only, lifted to a paraboloid) Fn - count plus neighboring region for each Delaunay region FN - count plus neighboring region for each point FO - options and precision constants FP - nearest point and distance for each coincident point FQ - command used for qdelaunay Fs - summary: #int (8), dimension, #points, tot vertices, tot facets, for output: #vertices, #Delaunay regions, #coincident points, #non-simplicial regions #real (2), max outer plane, min vertex FS - sizes: #int (0) #real (2), tot area, 0 Fv - count plus vertices for each Delaunay region Fx - extreme points of Delaunay triangulation (on convex hull) Geomview options (2-d and 3-d) Ga - all points as dots Gp - coplanar points and vertices as radii Gv - vertices as spheres Gi - inner planes only Gn - no planes Go - outer planes only Gc - centrums Gh - hyperplane intersections Gr - ridges GDn - drop dimension n in 3-d and 4-d output Gt - transparent outer ridges to view 3-d Delaunay Print options: PAn - keep n largest Delaunay regions by area Pdk:n - drop facet if normal[k] = n (default 0.. 0) PDk:n - drop facet if normal[k] >= n Pg - print good Delaunay regions (needs 'QGn' or 'QVn') PFn - keep Delaunay regions whose area is at least n PG - print neighbors of good regions (needs 'QGn' or 'QVn') PMn - keep n Delaunay regions with most merges Po - force output..

    Original link path: /html/qdelaun.htm
    Open archive

  • Title: qvoronoi -- Voronoi diagram
    Descriptive info: qvoronoi -- Voronoi diagram.. The Voronoi diagram is the nearest-neighbor map for a set of points.. Each region contains those points that are nearer one input site than any other input site.. The Voronoi diagram is the dual of the.. Delaunay triangulation.. rbox 10 D3 | qvoronoi.. Compute the 3-d Voronoi diagram of 10 random points.. Write a summary to the console and the Voronoi vertices and regions to 'result'.. The first vertex of the result indicates unbounded regions.. 1 D2 | qvoronoi.. Compute the 2-d Voronoi diagram of a triangle and a small square.. Write a summary to the console and Voronoi vertices and regions to 'result'.. Report a single Voronoi vertex for cocircular input sites.. The origin is the Voronoi vertex for the square.. Write a summary to the console and the Voronoi ridges to 'result'.. Each ridge is the perpendicular bisector of a pair of input sites.. Vertex 0 indicates unbounded ridges.. Vertex 8 is the Voronoi vertex for the square.. Print the bounded, separating hyperplanes for the 2-d Voronoi diagram of a triangle and a small square.. Note the four hyperplanes (i.. , lines) for Voronoi vertex 8.. It is at the origin.. Qhull computes the Voronoi diagram via the.. Each Voronoi vertex is the circumcenter of a facet of the Delaunay triangulation.. Each Voronoi region corresponds to a vertex (i.. , input site) of the Delaunay triangulation.. Qhull outputs the Voronoi vertices for each Voronoi region.. ', it lists all ridges of the Voronoi diagram with the corresponding pairs of input sites.. With options '.. ', it lists the bounded and unbounded separating hyperplanes.. You can also output a single Voronoi region for further processing [see.. graphics.. The 'qvonoroi' program is equivalent to '.. qhull v.. d n v Qbb QbB Qf Qg Qm Qr QR Qv Qx Qz TR E V Fa FA FC FD FS Ft FV Gt Q0,etc.. Voronoi image by KOOK Architecture, Silvan Oesterle and Michael Knauss.. qvoronoi synopsis.. qvoronoi- compute the Voronoi diagram.. input (stdin): dimension, number of points, point coordinates comments start with a non-numeric character options (qh-voron.. htm): Qu - compute furthest-site Voronoi diagram Tv - verify result: structure, convexity, and in-circle test.. - concise list of all options - - one-line description of all options output options (subset): s - summary of results (default) p - Voronoi vertices o - OFF file format (dim, Voronoi vertices, and Voronoi regions) FN - count and Voronoi vertices for each Voronoi region Fv - Voronoi diagram as Voronoi vertices between adjacent input sites Fi - separating hyperplanes for bounded regions, 'Fo' for unbounded G - Geomview output (2-d only) QVn - Voronoi vertices for input point n, -n if not TO file- output results to file, may be enclosed in single quotes examples: rbox c P0 D2 | qvoronoi s o rbox c P0 D2 | qvoronoi Fi rbox c P0 D2 | qvoronoi Fo rbox c P0 D2 | qvoronoi Fv rbox c P0 D2 | qvoronoi s Qu Fv rbox c P0 D2 | qvoronoi Qu Fo rbox c G1 d D2 | qvoronoi s p rbox c P0 D2 | qvoronoi s Fv QV0.. qvoronoi input.. consists of:.. , qvoronoi data.. , rbox 10 | qvoronoi), or the '.. , qvoronoi TI data.. Their Voronoi diagram has nine vertices and eight regions.. Notice the Voronoi vertex at the origin, and the Voronoi vertices (on each axis) for the four sides of the square.. qvoronoi s p data.. Voronoi diagram by the convex hull of 8 points in 3-d: Number of Voronoi regions: 8 Number of Voronoi vertices: 9 Number of non-simplicial Voronoi vertices: 1 Statistics for: RBOX s 4 W0 c D2 | QVORONOI s p Number of points processed: 8 Number of hyperplanes created: 18 Number of facets in hull: 10 Number of distance tests for qhull: 33 Number of merged facets: 2 Number of distance tests for merging: 102 CPU seconds to compute hull (after input): 0.. 094 2 9 4.. 217546450968612e-17 1.. 735507986399734 -8.. 402566836762659e-17 -1.. 364368854147395 0.. 3447488772716865 -0.. 6395484723719818 1.. 719446929853986 2.. 136555906154247e-17 0.. 4967882915039657 0.. 68662371396699 -1.. 729928876283549 1.. 343733067524222e-17 -0.. 8906163241424728 -0.. 4594150543829102 -0.. 6656840313875723 0.. 5003013793414868 -7.. 318364664277155e-19 -1.. 188217818408333e-16.. qvoronoi outputs.. These options control the output of Voronoi diagrams.. Voronoi vertices.. print the coordinates of the Voronoi vertices.. The second line is the number of vertices.. Each remaining line is a Voronoi vertex.. list the neighboring Voronoi vertices for each Voronoi vertex.. The first line is the number of Voronoi vertices.. Each remaining line starts with the number of neighboring vertices.. Negative vertices (e.. ) indicate vertices outside of the Voronoi diagram.. In the circle-in-box example, the Voronoi vertex at the origin has four neighbors.. list the Voronoi vertices for each Voronoi region.. The first line is the number of Voronoi regions.. Each remaining line starts with the number of Voronoi vertices.. In the circle-in-box example, the four bounded regions are defined by four Voronoi vertices.. Voronoi regions.. print the Voronoi regions in OFF format.. The second line is the number of vertices, the number of input sites, and "1".. The third line represents the vertex-at-infinity.. Its coordinates are "-10.. 101".. The next lines are the coordinates of the Voronoi vertices.. Each remaining line starts with the number  ...   2 4 5 1 3 0 1 4 5 1 5 0 1 2 5 2 4 0 4 6 5 2 6 0 2 6 5 3 4 0 4 5 5 3 7 0 1 5 5 4 8 0 6 5 5 5 6 0 2 3 5 5 7 0 1 3 5 6 8 0 6 3 5 7 8 0 3 5.. The output consists of 20 ridges and each ridge lists a pair of input sites and a triplet of Voronoi vertices.. The first eight ridges connect the origin ('P0').. The remainder list the edges of the cube.. Each edge generates an unbounded ray through the midpoint.. The corresponding separating planes ('Fo') follow each pair of coordinate axes.. Options '.. ' (triangulated output) and '.. ' (joggled input) are deprecated.. They may produce unexpected results.. If you use these options, cocircular and cospherical input sites will produce duplicate or nearly duplicate Voronoi vertices.. See also.. qvoronoi conventions.. The following terminology is used for Voronoi diagrams in Qhull.. The underlying structure is a Delaunay triangulation from a convex hull in one higher dimension.. Facets of the Delaunay triangulation correspond to vertices of the Voronoi diagram.. Vertices of the Delaunay triangulation correspond to input sites.. They also correspond to regions of the Voronoi diagram.. Delaunay conventions.. nearly incident.. Delaunay facet.. - a lower facet of the paraboloid.. Voronoi vertex.. - the circumcenter of a Delaunay facet.. Voronoi region.. - the Voronoi vertices for an input site.. The region of Euclidean space nearest to an input site.. Voronoi diagram.. - the graph of the Voronoi regions.. It includes the ridges (i.. , edges) between the regions.. vertex-at-infinity.. - the Voronoi vertex that indicates unbounded Voronoi regions in '.. ' output format.. Its coordinates are.. - a Voronoi vertex with optional restrictions by '.. qvoronoi options.. qvoronoi- compute the Voronoi diagram http://www.. other lines: point coordinates, best if one point per line comments: start with a non-numeric character options: Qu - compute furthest-site Voronoi diagram Qhull control options: QJn - randomly joggle input in range [-n,n] Qs - search all points for the initial simplex Qz - add point-at-infinity to Voronoi diagram QGn - Voronoi vertices if visible from point n, -n if not QVn - Voronoi vertices for input point n, -n if not Trace options: T4 - trace at level n, 4=all, 5=mem/gauss, -1= events Tc - check frequently during execution Ts - statistics Tv - verify result: structure, convexity, and in-circle test Tz - send all output to stdout TFn - report summary when n or more facets created TI file - input data from file, no spaces or single quotes TO file - output results to file, may be enclosed in single quotes TPn - turn on tracing when point n added to hull TMn - turn on tracing at merge n TWn - trace merge facets when width > n TVn - stop qhull after adding point n, -n for before (see TCn) TCn - stop qhull after building cone for point n (see TVn) Precision options: Cn - radius of centrum (roundoff added).. 01 post-merge Rn - randomly perturb computations by a factor of [1-n,1+n] Wn - min facet width for non-coincident point (before roundoff) Output formats (may be combined; if none, produces a summary to stdout): s - summary to stderr p - Voronoi vertices o - OFF format (dim, Voronoi vertices, and Voronoi regions) i - Delaunay regions (use 'Pp' to avoid warning) f - facet dump More formats: Fc - count plus coincident points (by Voronoi vertex) Fd - use cdd format for input (homogeneous with offset first) FD - use cdd format for output (offset first) FF - facet dump without ridges Fi - separating hyperplanes for bounded Voronoi regions FI - ID for each Voronoi vertex Fm - merge count for each Voronoi vertex (511 max) Fn - count plus neighboring Voronoi vertices for each Voronoi vertex FN - count and Voronoi vertices for each Voronoi region Fo - separating hyperplanes for unbounded Voronoi regions FO - options and precision constants FP - nearest point and distance for each coincident point FQ - command used for qvoronoi Fs - summary: #int (8), dimension, #points, tot vertices, tot facets, for output: #Voronoi regions, #Voronoi vertices, #coincident points, #non-simplicial regions #real (2), max outer plane and min vertex Fv - Voronoi diagram as Voronoi vertices between adjacent input sites Fx - extreme points of Delaunay triangulation (on convex hull) Geomview options (2-d only) Ga - all points as dots Gp - coplanar points and vertices as radii Gv - vertices as spheres Gi - inner planes only Gn - no planes Go - outer planes only Gc - centrums Gh - hyperplane intersections Gr - ridges GDn - drop dimension n in 3-d and 4-d output Print options: PAn - keep n largest Voronoi vertices by 'area' Pdk:n - drop facet if normal[k] = n (default 0.. 0) PDk:n - drop facet if normal[k] >= n Pg - print good Voronoi vertices (needs 'QGn' or 'QVn') PFn - keep Voronoi vertices whose 'area' is at least n PG - print neighbors of good Voronoi vertices PMn - keep n Voronoi vertices with most merges Po - force output..

    Original link path: /html/qvoronoi.htm
    Open archive

  • Title: qhalf -- halfspace intersection about a point
    Descriptive info: qhalf -- halfspace intersection about a point.. The intersection of a set of halfspaces is a polytope.. The polytope may be unbounded.. See Preparata Shamos [.. ] for a discussion.. In low dimensions, halfspace intersection may be used for linear programming.. | qhalf.. Print the intersection of the facets of a cube.. rbox c.. generates the vertices of a cube.. qconvex FV n.. returns of average of the cube's vertices (in this case, the origin) and the halfspaces that define the cube.. qhalf Fp.. computes the intersection of the halfspaces about the origin.. The intersection is the vertices of the original cube.. rbox c d G0.. 55 | qconvex.. Print the intersection of the facets of a cube and a diamond.. There are 24 facets and 14 intersection points.. Four facets define each diamond vertex.. Six facets define each cube vertex.. Same as above except triangulate before computing the intersection points.. Three facets define each intersection point.. There are two duplicates of the diamond and four duplicates of the cube.. Qhull computes a halfspace intersection by the geometric duality between points and halfspaces.. halfspace examples.. qhalf notes.. , and option 'p' of.. qhalf outputs.. By default, halfspace intersections may be defined by more than.. halfspaces.. See the previous cube and diamond example.. This is the expected output for halfspace intersection.. You can try triangulated output and joggled input.. It demonstrates that triangulated output is more accurate than joggled input.. ' (triangulated output), all halfspace intersections are simplicial (e.. , three halfspaces per intersection in 3-d).. In 3-d, if more than three halfspaces intersect at the same point, triangulated output will produce duplicate intersections, one for each additional halfspace.. ' (joggled input), all halfspace intersections are simplicial.. This may lead to nearly identical intersections.. For example, replace 'Qt' with 'QJ' above and compare the duplicated intersections.. The 'qhalf' program is equivalent to '.. qhull H.. qhalf synopsis.. qhalf- halfspace intersection about a point.. input (stdin): [dim, 1, interior point] dim+1, n halfspace coefficients + offset comments start with a non-numeric character options (qhalf.. htm): Hn,n - specify coordinates of interior point Qt - triangulated output QJ - joggle input instead of merging facets Tv - verify result: structure, convexity, and redundancy.. - concise list of all options - - one-line description of all options output options (subset): s - summary of results (default) Fp - intersection coordinates Fv - non-redundant halfspaces incident to each intersection Fx - non-redundant halfspaces o - OFF file format (dual convex hull) G - Geomview output (dual convex hull) m - Mathematica output (dual convex hull) QVn - print intersections for halfspace n, -n if not TO file - output results to file, may be enclosed in single quotes examples: rbox d | qconvex n | qhalf s H0,0,0 Fp rbox c | qconvex FV n | qhalf s i rbox c | qconvex FV n | qhalf s o.. qhalf input.. [optional] interior point.. 1.. coordinates of interior point.. dimension + 1.. number of halfspaces.. halfspace coefficients followed by offset.. , qhalf data.. , rbox c | qconvex FV n | qhalf), or the '.. , qhalf TI data.. Qhull needs an interior point to compute the halfspace intersection.. An interior point is inside all of the halfspaces.. Hx+b = 0.. The interior point may be in the input.. If not, option 'Hn,n' defines the interior point as [n,n,0,.. ] where.. is the default coordinate (e.. , 'H0' is the origin).. Use linear programming if you do not know the interior point (see.. halfspace notes.. ),.. The input to qhalf is a set of halfspaces.. Each halfspace is defined by.. coefficients followed by a signed offset.. This defines a linear inequality.. The coefficients define a vector that is normal to the halfspace.. The vector may have any length.. If it has length one, the offset is the distance from the origin to the halfspace's boundary.. This is the same format used for output options '.. ', and '.. ' to use cdd format for the halfspaces.. For example, here is the input for computing the intersection of halfplanes that form a cube.. rbox c | qconvex FQ FV n TO data.. RBOX c | QCONVEX FQ FV n 3 1 0 0 0 4 6 0 0 -1 -0.. qhalf s Fp data.. Halfspace intersection by the convex hull of 6 points in 3-d: Number of halfspaces: 6 Number of non-redundant halfspaces: 6 Number of intersection points: 8 Statistics for: RBOX c | QCONVEX FQ FV n | QHALF s Fp Number of points processed: 6 Number of hyperplanes created: 11 Number of distance tests for qhull: 11 Number of merged facets: 1 Number of distance tests for merging: 45 CPU seconds to compute hull (after input): 0  ...   point [S.. Spitz and S.. Teller].. qhalf conventions.. The following terminology is used for halfspace intersection in Qhull.. This is the hardest structure to understand.. The underlying structure is a convex hull with one vertex per non-redundant halfspace.. interior point.. - a point in the intersection of the halfspaces.. Qhull needs an interior point to compute the intersection.. halfspace input.. halfspace.. coordinates for the normal and a signed offset.. The distance to an interior point is negative.. non-redundant halfspace.. - a halfspace that defines an output facet.. - a dual vertex in the convex hull corresponding to a non-redundant halfspace.. - the dual point corresponding to a similar halfspace.. - the dual point corresponding to a redundant halfspace.. intersection point.. - the intersection of.. or more non-redundant halfspaces.. - a dual facet in the convex hull corresponding to an intersection point.. halfspaces intersect at a point.. - an intersection point that satisfies restriction '.. qhalf options.. qhalf- compute the intersection of halfspaces about a point http://www.. org input (stdin): optional interior point: dimension, 1, coordinates first lines: dimension+1 and number of halfspaces other lines: halfspace coefficients followed by offset comments: start with a non-numeric character options: Hn,n - specify coordinates of interior point Qt - triangulated ouput QJ - joggle input instead of merging facets Qc - keep coplanar halfspaces Qi - keep other redundant halfspaces Qhull control options: QJn - randomly joggle input in range [-n,n] Qbk:0Bk:0 - remove k-th coordinate from input Qs - search all halfspaces for the initial simplex QGn - print intersection if redundant to halfspace n, -n for not QVn - print intersections for halfspace n, -n if not Trace options: T4 - trace at level n, 4=all, 5=mem/gauss, -1= events Tc - check frequently during execution Ts - print statistics Tv - verify result: structure, convexity, and redundancy Tz - send all output to stdout TFn - report summary when n or more facets created TI file - input data from file, no spaces or single quotes TO file - output results to file, may be enclosed in single quotes TPn - turn on tracing when halfspace n added to intersection TMn - turn on tracing at merge n TWn - trace merge facets when width > n TVn - stop qhull after adding halfspace n, -n for before (see TCn) TCn - stop qhull after building cone for halfspace n (see TVn) Precision options: Cn - radius of centrum (roundoff added).. 01 post-merge Rn - randomly perturb computations by a factor of [1-n,1+n] Un - max distance below plane for a new, coplanar halfspace Wn - min facet width for outside halfspace (before roundoff) Output formats (may be combined; if none, produces a summary to stdout): f - facet dump G - Geomview output (dual convex hull) i - non-redundant halfspaces incident to each intersection m - Mathematica output (dual convex hull) o - OFF format (dual convex hull: dimension, points, and facets) p - vertex coordinates of dual convex hull (coplanars if 'Qc' or 'Qi') s - summary (stderr) More formats: Fc - count plus redundant halfspaces for each intersection - Qc (default) for coplanar and Qi for other redundant Fd - use cdd format for input (homogeneous with offset first) FF - facet dump without ridges FI - ID of each intersection Fm - merge count for each intersection (511 max) FM - Maple output (dual convex hull) Fn - count plus neighboring intersections for each intersection FN - count plus intersections for each non-redundant halfspace FO - options and precision constants Fp - dim, count, and intersection coordinates FP - nearest halfspace and distance for each redundant halfspace FQ - command used for qhalf Fs - summary: #int (8), dim, #halfspaces, #non-redundant, #intersections for output: #non-redundant, #intersections, #coplanar halfspaces, #non-simplicial intersections #real (2), max outer plane, min vertex Fv - count plus non-redundant halfspaces for each intersection Fx - non-redundant halfspaces Geomview output (2-d, 3-d and 4-d; dual convex hull) Ga - all points (i.. , transformed halfspaces) as dots Gp - coplanar points and vertices as radii Gv - vertices (i.. , non-redundant halfspaces) as spheres Gi - inner planes (i.. , halfspace intersections) only Gn - no planes Go - outer planes only Gc - centrums Gh - hyperplane intersections Gr - ridges GDn - drop dimension n in 3-d and 4-d output Print options: PAn - keep n largest facets (i.. , intersections) by area Pdk:n- drop facet if normal[k] = n (default 0.. 0) PDk:n- drop facet if normal[k] >= n Pg - print good facets (needs 'QGn' or 'QVn') PFn - keep facets whose area is at least n PG - print neighbors of good facets PMn - keep n facets with most merges Po - force output..

    Original link path: /html/qhalf.htm
    Open archive

  • Title: rbox -- generate point distributions
    Descriptive info: rbox -- generate point distributions.. rbox generates random or regular points according to the options given, and outputs the points to stdout.. The points are generated in a cube, unless 's', 'x', or 'y' are given.. rbox synopsis.. rbox- generate various point distributions.. Default is random in cube.. args (any order, space separated): 3000 number of random points in cube, lens, spiral, sphere or grid D3 dimension 3-d c add a unit cube to the output ('c G2.. 0' sets size) d add a unit diamond to the output ('d G2.. 0' sets size) l generate a regular 3-d spiral r generate a regular polygon, ('r s Z1 G0.. 1' makes a cone) s generate cospherical points x generate random points in simplex, may use 'r' or 'Wn' y same as 'x', plus simplex Pn,m,r add point [n,m,r] first, pads with 0 Ln lens distribution of radius n.. Also 's', 'r', 'G', 'W'.. Mn,m,r lattice (Mesh) rotated by [n,-m,0], [m,n,0], [0,0,r],.. '27 M1,0,1' is {0,1,2} x {0,1,2} x {0,1,2}.. Try 'M3,4 z'.. W0.. 1 random distribution within 0.. 1 of the cube's or sphere's surface Z0.. 5 s random points in a 0.. 5 disk projected to a sphere Z0.. 5 s G0.. 6 same as Z0.. 5 within a 0.. 6 gap Bn bounding box coordinates, default 0.. 5 h output as homogeneous coordinates for cdd n remove command line from the first line of output On offset coordinates by n t use time as the random number seed (default is command line) tn use n as the random number seed z print integer coordinates, default 'Bn' is 1e+06.. rbox outputs.. The format of the output is the following: first line contains the dimension and a comment, second line contains the number of points, and the following lines contain the points, one point per line.. Points are represented by their coordinate values.. rbox c 10 D2.. generates.. 2 RBOX c 10 D2 14 -0.. 4999921736307369 -0.. 3684622117955817 0.. 2556053225468894 -0.. 0413498678629751 0.. 0327672376602583 -0.. 2810408135699488 -0.. 452955383763607 0.. 17886471718444 0.. 1792964061529342 0.. 4346928963760779 -0.. 1164979223315585 0.. 01941637230982666 0.. 3309653464993139 -0.. 4654278894564396 -0.. 4465383649305798 0.. 02970019358182344 0.. 1711493843897706 -0.. 4923018137852678 -0.. 1165843490665633 -0.. 433157762450313 -0.. rbox examples.. rbox 10 10 random points  ...   P0 P0 P0 P0 P0 | qhull QJ'.. r 100 s Z1 G0.. 1 two cospherical 100-gons plus another cospherical point.. 100 s Z1 a cone of points.. 100 s Z1e-7 a narrow cone of points with many precision errors.. rbox notes.. Some combinations of arguments generate odd results.. rbox options.. n number of points Dn dimension n-d (default 3-d) Bn bounding box coordinates (default 0.. 5) l spiral distribution, available only in 3-d Ln lens distribution of radius n.. May be used with 's', 'r', 'G', and 'W'.. Mn,m,r lattice (Mesh) rotated by {[n,-m,0], [m,n,0], [0,0,r],.. }.. Use 'Mm,n' for a rigid rotation with r = sqrt(n^2+m^2).. 'M1,0' is an orthogonal lattice.. For example, '27 M1,0' is {0,1,2} x {0,1,2} x {0,1,2}.. s cospherical points randomly generated in a cube and projected to the unit sphere x simplicial distribution.. It is fixed for option 'r'.. May be used with 'W'.. y simplicial distribution plus a simplex.. Both 'x' and 'y' generate the same points.. Wn restrict points to distance n of the surface of a sphere or a cube c add a unit cube to the output c Gm add a cube with all combinations of +m and -m to the output d add a unit diamond to the output.. d Gm add a diamond made of 0, +m and -m to the output Pn,m,r add point [n,m,r] to the output first.. Pad coordi- nates with 0.. n Remove the command line from the first line of out- put.. On offset the data by adding n to each coordinate.. t use time in seconds as the random number seed (default is command line).. tn set the random number seed to n.. z generate integer coordinates.. Use 'Bn' to change the range.. The default is 'B1e6' for six-digit coordinates.. In R^4, seven-digit coordinates will overflow hyperplane normalization.. Zn s restrict points to a disk about the z+ axis and the sphere (default Z1.. 0).. Includes the opposite pole.. 'Z1e-6' generates degenerate points under single precision.. Zn Gm s same as Zn with an empty center (default G0.. 5).. r s D2 generate a regular polygon r s Z1 G0.. 1 generate a regular cone.. 25, 1995 --- Last modified: August 12, 1998..

    Original link path: /html/rbox.htm
    Open archive

  • Title:
    Descriptive info: Qhull, Copyright (c) 1993-2012 C.. Barber Arlington, MA and The National Science and Technology Research Center for Computation and Visualization of Geometric Structures (The Geometry Center) University of Minnesota email: qhull@qhull.. org This software includes Qhull from C.. Barber and The Geometry Center.. Qhull is copyrighted as noted above.. Qhull is free software and may be obtained via http from www.. It may be freely copied, modified, and redistributed under the following conditions: 1.. All copyright notices must remain intact in all files.. 2.. A copy of this text file must be distributed along with any copies of Qhull  ...   Qhull.. 3.. If you modify Qhull, you must include a notice giving the name of the person performing the modification, the date of modification, and the reason for such modification.. 4.. When distributing modified versions of Qhull, or other software products that include Qhull, you must provide notice that the original source code may be obtained as noted above.. 5.. There is no warranty or other guarantee of fitness for Qhull, it is provided solely "as is".. Bug reports or fixes may be sent to qhull_bug@qhull.. org; the authors may or may not act on them as they desire..

    Original link path: /COPYING.txt
    Open archive

  • Title:
    Descriptive info: Dear Qhull User We would like to find out how you are using our software.. Think of Qhull as a new kind of shareware: you share your science and successes with us, and we share our software and support with you.. If you use Qhull, please send us a note telling us what you are doing with it.. We need to know: (1) What you are working on - an  ...   example, by increasing your productivity or allowing you to do things you could not do before.. If Qhull had a direct bearing on your work, please tell us about this.. We encourage you to cite Qhull in your publications.. To cite Qhull, please use Barber, C.. , "The Quickhull algorithm for convex hulls," ACM Trans.. on Mathematical Software, 22(4):469-483, Dec 1996, http://www.. Please send e-mail to bradb@shore.. net Thank you!..

    Original link path: /REGISTER.txt
    Open archive

  • Title:
    Descriptive info: Name qhull, rbox 2012.. 1 2012/02/18 Convex hull, Delaunay triangulation, Voronoi diagrams, Halfspace intersection Documentation: html/index.. htm http://www.. org/html Available from:.. [out-of-date] News and a paper:.. Version 1 (simplicial only):.. Purpose Qhull is a general dimension convex hull program that reads a set of points from stdin, and outputs the smallest convex set that contains the points to stdout.. It also generates Delaunay triangulations, Voronoi diagrams, furthest-site Voronoi diagrams, and halfspace intersections about a point.. Rbox is a useful tool in generating input for Qhull; it generates hypercubes, diamonds, cones, circles, simplices, spirals, lattices, and random points.. Qhull produces graphical output for Geomview.. This helps with understanding the output.. Environment requirements Qhull and rbox should run on all 32-bit and 64-bit computers.. Use an ANSI C or C++ compiler to compile the program.. The software is self-contained.. It comes with examples and test scripts.. Qhull's C++ interface uses the STL.. The C++ test program uses QTestLib from Nokia's Qt Framework.. Qhull's C++ interface may change without notice.. Eventually, it will move into the qhull shared library.. Qhull is copyrighted software.. Please read COPYING.. txt and REGISTER.. txt before using or distributing Qhull.. To contribute to Qhull Qhull is on Gitorious (http://gitorious.. org:qhull, git@gitorious.. org:qhull/qhull.. git) For internal documentation, see html/qh-code.. htm To install Qhull Qhull is precompiled for Windows, otherwise it needs compilation.. Besides makefiles for gcc, qhull includes CMakeLists.. txt for CMake, vcproj/sln files for Microsoft Visual Studio, and.. pro files for Qt Creator.. It compiles with mingw.. Install and build instructions follow.. See the end of this document for a list of distributed files.. ----------------- Installing Qhull on Windows The zip file contains rbox.. exe, qhull.. exe, qconvex.. exe, qdelaunay.. exe, qhalf.. exe, qvoronoi.. exe, testqset.. exe, user_eg*.. exe, documentation files, and source files.. To install Qhull: - Unzip the files into a directory.. You may use WinZip32.. - Click on QHULL-GO or open a command window into Qhull's bin directory.. To uninstall Qhull - Delete the qhull directory To learn about Qhull: - Execute 'qconvex' for a synopsis and examples.. - Execute 'rbox 10 | qconvex' to compute the convex hull of 10 random points.. - Execute 'rbox 10 | qconvex i TO file' to write results to 'file'.. - Browse the documentation: qhull\html\index.. htm - If an error occurs, Windows sends the error to stdout instead of stderr.. Use 'TO xxx' to send normal output to xxx and error output to stdout To improve the command window - Double-click the window bar to increase the size of the window - Right-click the window bar - Select Properties - Check QuickEdit Mode Select text with right-click or Enter Paste text with right-click - Change Font to Lucinda Console - Change Layout to Screen Buffer Height 999, Window Size Height 55 - Change Colors to Screen Background White, Screen Text Black - Click OK - Select 'Modify shortcut that started this window', then OK If you use qhull a lot, install MSYS (www.. mingw.. org), Road Bash (www.. org/bash), or Cygwin (www.. cygwin.. com).. ----------------- Installing Qhull on Unix with gcc To build Qhull, static libraries, shared library, and C++ interface - Extract Qhull from qhull.. tgz or qhull.. zip - make - export LD_LIBRARY_PATH=$PWD/lib:$LD_LIBRARY_PATH Or, to build Qhull and libqhullstatic.. a - Extract Qhull from qhull.. zip - cd src/libqhull - make The Makefiles may be edited for other compilers.. If 'testqset' exits with an error, qhull is broken ----------------- Installing Qhull with CMake 2.. 6 or later To build Qhull, static libraries, shared library, and C++ interface - Extract Qhull from qhull.. zip - cd build - cmake.. - make - make install On Windows, CMake installs to C:/Program Files/qhull See CMakeLists.. txt for further build instructions ----------------- Installing Qhull with Qt To build Qhull, static libraries, shared library, C++ interface, and C++ test - Extract Qhull from qhull.. zip - cd src - qmake - make ----------------- Installing Qhull with Autoconf [WARNING out-of-date] The tar.. gz tarball contains documentation, source files, and a config directory [R.. Laboissiere].. [Nov 2011] Qhull 2009.. 2 does not include the C++ interface To install Qhull - Extract the files -.. /configure - make - make install ------------------- Working with Qhull's C++ interface Qhull's C++ interface is likely to change.. Stay current with Gitorious.. To clone Qhull's next branch from http://gitorious.. org/qhull git init git clone git://gitorious.. org/qhull/qhull.. git cd qhull git checkout next.. git pull origin next ------------------ Compiling Qhull with Microsoft Visual C++ 2005 or later To compile Qhull with Microsoft Visual C++ - Extract Qhull from Gitorious, qhull.. tgz, or qhull.. zip - Load solution build/qhull.. sln - Build - Project qhulltest requires Qt for DevStudio (http://qt.. nokia.. com/downloads) Set the QTDIR environment variable to your Qt directory (e.. , c:/qt/4.. 7.. 4) If incorrect, precompile will fail with 'Can not locate the file specified' ----------------- Compiling Qhull with Qt Creator Qt (http://qt.. com) is a C++ framework for Windows, Linux, and Macintosh Qhull uses QTestLib to test qhull's C++  ...   txt // Copyright notice QHULL-GO.. lnk // Windows icon for eg/qhull-go.. bat Announce.. txt // Announcement CMakeLists.. txt // CMake build file (2.. 6 or later) File_id.. diz // Package descriptor index.. htm // Home page Makefile // Makefile for gcc and other compilers qhull*.. md5sum // md5sum for all files bin/* // Qhull executables and dll (.. zip only) build/qhull.. sln // DevStudio solution and project files (2005 or later) build/*.. vcproj config/* // Autoconf files for creating configure (Unix only) eg/* // Test scripts and geomview files from q_eg html/index.. htm // Manual html/qh-faq.. htm // Frequently asked questions html/qh-get.. htm // Download page html/qhull-cpp.. xml // C++ style notes as a Road FAQ (www.. org/road) src/Changes.. txt // Change history for Qhull and rbox src/qhull-all.. pro // Qt project eg/ q_eg // shell script for Geomview examples (eg.. 01.. cube) q_egtest // shell script for Geomview test examples q_test // shell script to test qhull q_test-ok.. txt // output from q_test qhulltest-ok.. txt // output from qhulltest (Qt only) rbox consists of (bin, html): rbox.. exe // Win32 executable (.. zip only) rbox.. htm // html manual rbox.. man // Unix man page rbox.. txt qhull consists of (bin, html): qhull.. exe // Win32 executables and dlls (.. zip only) qconvex.. exe qdelaunay.. exe qhalf.. exe qvoronoi.. exe qhull.. dll qhull_p.. dll qhull-go.. bat // command window qconvex.. htm // html manual qdelaun.. htm qdelau_f.. htm qhalf.. htm qvoronoi.. htm qvoron_f.. htm qh-eg.. htm qh-code.. htm qh-impre.. htm index.. htm qh-opt*.. htm qh-quick.. htm qh--*.. gif // images for manual normal_voronoi_knauss_oesterle.. jpg qhull.. man // Unix man page qhull.. txt bin/ msvcr80.. dll // Visual C++ redistributable file (.. zip only) src/ qhull/unix.. c // Qhull and rbox applications qconvex/qconvex.. c qhalf/qhalf.. c qdelaunay/qdelaunay.. c qvoronoi/qvoronoi.. c rbox/rbox.. c user_eg/user_eg.. c // example of using qhull_p.. dll (requires -Dqh_QHpointer) user_eg2/user_eg2.. c // example of using qhull.. dll from a user program user_eg3/user_eg3.. cpp // example of Qhull's C++ interface with libqhullstatic_p.. a qhulltest/qhulltest.. cpp // Test of Qhull's C++ interface using Qt's QTestLib qhull-*.. pri // Include files for Qt projects src/libqhull libqhull.. pro // Qt project for shared library (qhull.. dll) index.. htm // design documentation for libqhull qh-*.. htm qhull-exports.. def // Export Definition file for Visual C++ Makefile // Simple gcc Makefile for qhull and libqhullstatic.. a Mborland // Makefile for Borland C++ 5.. 0 libqhull.. h // header file for qhull user.. h // header file of user definable constants libqhull.. c // Quickhull algorithm with partitioning user.. c // user re-definable functions usermem.. c userprintf.. c userprintf_rbox.. c qhull_a.. h // include files for libqhull/*.. c geom.. c // geometric routines geom2.. h global.. c // global variables io.. c // input-output routines io.. h mem.. c // memory routines, this is stand-alone code mem.. h merge.. c // merging of non-convex facets merge.. h poly.. c // polyhedron routines poly2.. c poly.. h qset.. c // set routines, this only depends on mem.. c qset.. h random.. c // utilities w/ Park & Miller's random number generator random.. h rboxlib.. c // point set generator for rbox stat.. c // statistics stat.. h src/libqhullp libqhullp.. pro // Qt project for shared library (qhull_p.. dll) qhull_p-exports.. def // Export Definition file for Visual C++ src/libqhullstatic/ libqhullstatic.. pro // Qt project for static library src/libqhullstaticp/ libqhullstaticp.. pro // Qt project for static library with qh_QHpointer src/libqhullcpp/ libqhullcpp.. pro // Qt project for static C++ library Qhull.. cpp // Call libqhull.. c from C++ Qhull.. h qt-qhull.. cpp // Supporting methods for Qt qhull_interface.. cpp // Another approach to C++ Coordinates.. cpp // input classes Coordinates.. h PointCoordinates.. cpp PointCoordinates.. h RboxPoints.. cpp // call rboxlib.. c from C++ RboxPoints.. h QhullFacet.. cpp // data structure classes QhullFacet.. h QhullHyperplane.. cpp QhullHyperplane.. h QhullPoint.. cpp QhullPoint.. h QhullQh.. cpp QhullStat.. h QhullVertex.. cpp QhullVertex.. h QhullFacetList.. cpp // collection classes QhullFacetList.. h QhullFacetSet.. cpp QhullFacetSet.. h QhullIterator.. h QhullLinkedList.. h QhullPoints.. cpp QhullPoints.. h QhullPointSet.. cpp QhullPointSet.. h QhullRidge.. cpp QhullRidge.. h QhullSet.. cpp QhullSet.. h QhullSets.. h QhullVertexSet.. cpp QhullVertexSet.. h functionObjects.. h // supporting classes QhullError.. cpp QhullError.. cpp QhullQh.. h UsingLibQhull.. cpp UsingLibQhull.. h src/qhulltest/ qhulltest.. pro // Qt project for test of C++ interface Coordinates_test.. cpp // Test of each class PointCoordinates_test.. cpp Point_test.. cpp QhullFacetList_test.. cpp QhullFacetSet_test.. cpp QhullFacet_test.. cpp QhullHyperplane_test.. cpp QhullLinkedList_test.. cpp QhullPointSet_test.. cpp QhullPoints_test.. cpp QhullPoint_test.. cpp QhullRidge_test.. cpp QhullSet_test.. cpp QhullVertexSet_test.. cpp QhullVertex_test.. cpp Qhull_test.. cpp RboxPoints_test.. cpp UsingLibQhull_test.. cpp src/road/ RoadError.. cpp // Supporting base classes RoadError.. h RoadLogEvent.. cpp RoadLogEvent.. h RoadTest.. cpp // Run multiple test files with QTestLib RoadTest.. h src/testqset/ testqset.. pro // Qt project for test qset.. c with mem.. c testqset.. c ----------------- Authors: C.. Bradford Barber Hannu Huhdanpaa (Version 1.. 0) bradb@shore.. org Qhull 1.. 0 were developed under NSF grants NSF/DMS-8920161 and NSF-CCR-91-15793 750-7504 at the Geometry Center and Harvard University.. If you find Qhull useful, please let us know..

    Original link path: /README.txt
    Open archive





  • Archived pages: 41