1<?xml version="1.0" encoding="utf-8"?> 2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> 3 4<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 5 6<head> 7 <meta http-equiv="content-type" content="text/html; charset=utf-8" /> 8 <title>Qhull News, Bugs, and Users</title> 9</head> 10 11<body> 12<!-- Navigation links --> 13<p> 14<a name="TOP"><b>Up:</b></a> <a href="http://www.qhull.org">http://www.qhull.org</a><br/> 15<strong>To:</strong>: <a href="#bugs">Bug and Notes</a> and 16<a href="#users">Qhull Users</a> <br/> 17<strong>Dn</strong>: <a href="../html/qh-faq.htm">FAQ about Qhull</a></p> 18 19<hr/> 20<!-- Main text of document --> 21<h1><a 22href="http://www.geom.uiuc.edu/graphics/pix/Special_Topics/Computational_Geometry/fixed.html"><img 23src="../html/qh--rand.gif" alt="[RANDOM]" align="middle" width="100" 24height="100"/></a> Qhull News, Bugs, and Users</h1> 25 26<p> 27<blockquote> 28<a href="#highlights">Highlights</a> 29 :: 30<a href="#problems">Known Problems</a> 31 :: 32<a href="#bugs">Bugs and Notes</a> 33 :: 34<a href="#users">Qhull Users</a> 35<br> 36<a href="../src/Changes.txt">Change History</a> 37 :: 38<a href="../README.txt">Readme</a> 39 :: 40<a href="http://www.qhull.org/src/libqhull_r">Functions</a> 41 42<!-- 43 :: 44<a href=http://www.qhull.org/stats>Website Statistics</a>. 45<a href="http://www.qhull.org/log00.htm">log00.htm</a>, 46and 47<a href="http://www.qhull.org/log01.htm">log01.htm</a> 48--> 49 50<p>Qhull 2020.2 is available for download (2020/08/31, 8.0.2, <a href="http://www.qhull.org/README.txt">README</a>, <a href="../src/Changes.txt">Changes</a>). 51<ul> 52<li><a href="http://www.qhull.org/download">Download</a> Qhull</li> 53<li><a href="http://github.com/qhull/qhull/wiki">GitHub Qhull</a> ([email protected]:qhull/qhull.git)</li> 54<li><a href="http://github.com/qhull/qhull/wiki/Qhull%202020.1">Qhull 2020.1</a> 55<li><a href="http://github.com/qhull/qhull/wiki/Qhull%202019.1">Qhull 2019.1</a> 56<p><nobr> </nobr> 57<li><a href="http://github.com/qhull/qhull/wiki/Qhull%20build%20systems">Qhull build systems</a> 58<li><a href="../html/qh-code.htm#cpp">Calling Qhull</a> from C++ programs. 59<li><a href="../html/qh-code.htm#debug">How to debug</a> Qhull. 60<li><a href="../html/qh-code.htm#64bit">Qhull on 64-bit</a> computers. 61<li><a href="../html/qh-code.htm#convert">How to convert</a> code to reentrant Qhull. 62</ul> 63 64<p>Qhull 2020.2 2020/08/31 (8.0.2) updates Qhull's builds and Qhull's C++ interface. 65 66<p>Qhull's builds produce a shared library, libqhull_r.so (qhull_r.dll), several static libraries, and 67several applications using these libraries. They do <i>not</i> produce deprecated libraries: 68libqhull.so, qhull.dll, libqhull_p.so, and qhull_p.dll. Users of these libraries should convert 69their code to reentrant Qhull (libqhull_r.so) or link to libqhullstatic.a. 70 71<p>Qhull's Java-style iterators use a copy constructor to avoid subtle errors due to memory management. 72Its C++ interface is compatible with C++98. 73 74<p>Other changes for Qhull 2020.2: 75<ul> 76<li>The installs for <a href "http://github.com/qhull/qhull/wiki/Qhull%20build%20systems">Qhull builds</a> produce nearly the same results. 77<code>/usr/local/share/doc/qhull</code> includes README.txt and html/*.htm. For function documentation, use <a href="http://www.qhull.org/src/libqhull_r">Qhull functions</a>. 78<li>CMake for "MSYS Makefiles" installs to <code>/usr/local</code>. 79<li>CMake adds parameters BUILD_STATIC_LIBS, BUILD_SHARED_LIBS, and LINK_APPS_SHARED. The 80same target name is used for debug and non-debug builds. 81<li>CMake 'uninstall' deletes the files listed in install_manifest.txt. 82<li>C++ classes <code>Coordinates</code> and <code>PointCoordinates</code> do <i>not</i> include 83a Java-style iterator. They would require an expensive copy constructor for <code>std::vector</code> 84<li>Due to C++98 compatibility, <code>user_eg3</code> uses Java-style iterators instead of range-based-for-loops. 85<li> See <a href="../src/Changes.txt">Changes.txt</a> for all changes to Qhull. 86The "To do" section includes 87a top-level design for constructing Voronoi diagrams in C++. 88</ul> 89 90<p>You may call Qhull from your program 91(<a href="../html/qh-code.htm">Qhull Code</a>). 92Qhull includes a C interface, a C++ interface, 93demonstration programs, and test programs. Start with small examples 94that you work out by hand. Compare your program with the results 95from Qhull. Understand the data structures and precision issues. 96 97<p>Programs and libraries that use Qhull should 98upgrade to Qhull 2020.2. The reentrant library, libqhull_r, was 99introduced in Qhull 2015.1. It replaces the qh_QHpointer library, libqhull_p, and the non-reentrant 100library, libqhull. The qh_QHpointer library, libqhull_p, should not be used. The static, non-reentrant 101library, libqhullstatic.a, remains useful for Qhull applications that do not include user co
101de. 102 103<p>Multiple threads may use the reentrant library, libqhull_r, at the same time. Each instance of 104Qhull is a separate run. The first argument for most 105Qhull procedures is a pointer to the qhT data structure. This approach was pioneered by 106Peter Klosterman in 2010. To verify the changes required, a shell script, eg/make-qhull_qh.sh, 107recreates libqhull code from libqhull_r code. A directory-diff checks that the conversion was correct. 108 109<p>The C++ interface is based on the reentrant library. It includes QhullUser and RboxPoints classes. 110Output produced by 'qhull' can be transferred to QhullUser. Most of the output produced by 'rbox' is transferred 111to RboxPoints. 112 113<p>Comments, errors, suggestions are welcome (<a href="mailto:[email protected]">[email protected]</a>). 114 115<p> 116This site also hosts pages on 117<a href="http://www.qhull.org/road/road-faq/xml/cpp-guideline.xml">C++ and Perl Guidelines</a> for advice on writing programs, 118<a href="http://www.qhull.org/bash">Road bash</a> for a portable bash shell for Unix, Mac, Windows XP or Windows 8, 119<a href="http://www.qhull.org/road">Road Intranet</a> for (out-of-date) advice on Windows, Perforce, etc, 120and 121<a href="http://www.qhull.org/ttcnf">ttcnf</a> for truth table CNF. 122Visit <a href=http://www.thesa.com>www.thesa.com</a> for 123a thesaurus of research literature and <a href=https://github.com/namec-git/namec>namec</a> for programming 124with arbitrary names. 125</blockquote> 126 127<p><b>Copyright © 1995-2020 C.B. Barber</b></p> 128 129<p><!-- 130The last documentation update was ... 131--> </p> 132 133<h2><a href="#TOP">»</a> <a name="problems">Known problems</a></h2> 134 135<p><b>All users</b></p> 136 137<p>A performance issue occurs for 3D+ Delaunay triangulation and Voronoi diagram. 138If many input sites are coplanar to their convex hull, qhull performs many, expensive 139facet merges. These sites do not generate separate regions 140(<a href="../html/qdelaun.htm#notes">qdelaunay notes</a>), but they create 141intermediate facets that are merged and discarded. 142For examples, see GitHub issue 143<a href="https://github.com/qhull/qhull/issues/146">Qhull #146 - Runtime increases when a subset of the point cloud are co-planar points</a> 144[C. Sheradil, August 2024]. A similar issue should occur if many input sites are coplanar with 145any facet of the Delaunay triangulation. For convex hulls, a similar issue should occur for many 146points on a (N-3)D dimensional flat. 147 148<p>Qhull uses pointer-intensive data structures. As a result, 64-bit builds of Qhull use more memory than 32-bit builds. 149If the data structures do not fit into cache memory, processing speed 150is reduced. If practical, use 32-bit builds of Qhull. If 64-bit builds are required, monitor the processing 151time per point with option <A href="../html/qh-optt.htm#TFn">TFn</a>. If processing time increases dramatically, 152you may be running out of high-speed memory. A future version of Qhull will improve 64-bit memory and performamce. 153 154<p>In 3-d and higher Delaunay Triangulations or 4-d and higher convex hulls, 155multiple, nearly coincident points may lead to very wide facets. 156For points in the unit cube, 157it occurs when many points are approximately 1e-13 apart. Closer points or further apart points are OK. 158The problem has existed since the beginning of Qhull. 159Qhull 2019.1 introduces an experimental option <a href="../html/qh-optq.htm#Q14">Q14</a> to 160address this issue. It merges vertices that create topological errors. While it repairs some 161problems, it demonstrates the limitations of facet merging. For more information, see "Nearly coincident points within 1e-13" in 162<a href="../html/qh-impre.htm#limit">Limitations of merged facets</a>. A future version of 163Qhull will add per-vertex joggle to avoid topological errors. 164 165<p>The q_benchmark tests of N_PINCHED reveal the interaction between geometric, precision errors and 166topological errors. In Euclidean space with precise arithmetic, the mathematics of convex hulls prevents 167topological errors. With imprecision, topological errors become possible. Qhull handles precision and topological errors with facet and 168vertex merging. With repeated merges, precision errors and topological 169errors eventually become too severe and prevent further processing. An error is reported. 170 171<p>In 3-d and higher, option '<a href="../html/qh-optq.htm#Qt">Qt</a>' does not produce conforming triangulations 172for adjacent, non-simplicial facets. For example, if you have a regular, 3-d array of 173input sites, their Delaunay triangulation consists of cubes. Option 'Qt' will triangulate each 174cube into tetrahedra. Within 175each cube, the triangulation is consistent, but it is not necessarily 176consistent between adjacent cubes [C. Bertoglio; C. de Visser]. How to fix this problem is unknown. 177 178<p>Users of 'qhull d' and 'qhull v' should use 'qhull d Qbb' 179and 'qhull v Qbb' respectively. Option '<A href="../html/qh-optq.htm#Qbb">Qbb</A>' 180is automatically set for 'qdelaunay', 'qvoronoi', and 'QJ'. 181It improves precision by scaling the paraboloid. 182 183<p><b>All programmers</b></p> 184 185<p>qh_findbestfacet [poly2_r.c] returns the facet with the largest signed distance to a given point. 186For Delaunay triangulations, 187this facet is usually, but not always, the facet containing the point. See this <a href="qh_findbestfacet-drielsma.pdf">test of qh_findbestfacet</a> 188by F. Drielsma. For green points, the "best" facet is the lower-left "green" triangle. However, along the 189upper-right edge, the green points are in the upper-right "yellow" triangle. Qhull computes a Delaunay
190triangulation via the convex hull of a paraboloid one dimension higher. Vertices of the convex hull 191correspond tp input sites of the Delaunay triangulation. 192 193<p>For triangulated non-simplicial facets, qh_findbestfacet returns one of several <i>tricoplanar</i> facets. 194These 195facets share the same hyperplane as the original non-simplical facet. For Delaunay triangulations, 196the facet containing the point may be any of the tricoplanar facets or their neighbors. 197 198<p>Both problems may be resolved by testing the returned facet and its neighbors for containment (see, <a href="../html/index.htm#muck96">Mucke, et.al. 1996</a>). 199 200<p>qh_detvnorm [io_r.c] implements Voronoi options '<a href="../html/qh-optf.htm#Fi">Fi</a>' and '<a href="../html/qh-optf.htm#F">Fo</a>' for 201separating hyperplanes. An error is not reported if a hyperplane is degenerate (e.g., 'rbox c P0 D2 | qhull v Fo'). 202Option '<a href="../html/qh-optt.htm#Fi">Tv</a>' collects statistics to verify 'Fi'. 203 204<li>See <a href="#bugs">Bug and Notes</a> for problems in previous Qhull versions. 205 206<h2><a href="#TOP">»</a> <a name="highlights">Highlights</a></h2> 207 208<p> 209[Apr 2018] G. Heinzel designed a "frequency plan", a part of the operational schedule, for the 210planned gravitational detector space mission LISA. He ran millions of tests whether or not a 4D point lies within the 211Minkowski sum of a 4D cuboid and another 5D cuboid linearly distorted into 4D space. See Wikipedia on 212<a href="https://en.wikipedia.org/wiki/Minkowski_addition#Convex_hulls_of_Minkowski_sums">Convex hulls 213of Minkowski sums</a>. 214 215<p> 216[Jan 2016] R. Gonzalez released <a href="http://arxiv.org/abs/1601.06429">PARAVT: Parallel Voronoi Tessellation code</a> 217(<a href="https://github.com/regonzar/paravt">code</a>) for large, astrophysics data sets. 218This is the first package built on reentrant Qhull. 219 220<p> 221[Nov 2014] <a href="http://www.mcs.anl.gov/papers/P5154-0614.pdf">Peterka, Morozov and Phillips</a> used their DIY 222data-parallel programming library for high-performance 223computation of large-scale, 3D Voronoi and Delaunay tesselations. Their code uses either 224CGAL or Qhull. CGAL was substantially more compact and faster. CGAL generates 3D-specific code, while 225Qhull is general dimensional. For 64-bit code, Qhull's data structures nearly double in 226size and reduce the effectiveness of cache memory. A future version of Qhull will provide 227bulk addition of input sites and optimizations for 64-bit code. 228 229<p> 230[Sep 2014] <a href="http://www.3scan.com">3scan</a> uses Qhull for volumetric reconstruction and segmentation of microscopy images. 231They commercialized the "Knife-Edge Scanning Microscope" first developed at Texas A&M�s Brain 232Networks Laboratory. 233 234<p> 235[July 2014] Toronto and McCarthy published <a href="https://ieeexplore.ieee.org/document/6879754">Practically accurate floating-point math</a> in 236<i>Computing in Science & Engineering</i>. They show how to rewrite a computation to 237avoid the "badlands". It would improve Qhull's computations, particularly qh_setfacetplane. 238From the abstract "With the right tools, floating-point code can be debugged like any other code, drastically improving its accuracy and reliability." 239 240<p> 241[Mar 2014] 242D. Gregorius gave a <a href="http://media.steampowered.com/apps/valve/2014/DirkGregorius_ImplementingQuickHull.pdf">tutorial</a> 243on QhullHull at the 2014 Game Developers Conference. It describes the QuickHull algorithm used in Qhull and facet 244merging to handle precision errors. 245 246<p> 247[Jan 2014] I. Thomas added Qhull to <a href="http://www.matplotlib.org">matplotlib</a>, an open-source python plotting library. It will appear in 1.4.0 onwards. 248 249<p> 250[Jun 2013] Miller, Sheehy, and Velingker published a paper on well-space points and approximate delaunay graphs. It builds on work of Shewchuk, Hang, and Alliez et al. and 251may suitable for implementation in Qhull [Miller et al, <i>Symp. on Computational Geometry</i>, 2013]. 252 253<p> 254[Mar 2013] D. Gregorius gave a talk on the <a href=http://twvideo01.ubm-us.net/o1/vault/gdc2013/sli
254des/822403Gregorius_Dirk_TheSeparatingAxisTest.pdf>separating access test (SAT)</a> at 255the Game Developers Conference. SAT in combination with Qhull build a powerful tool for collision detection in computer games. 256 257<p> 258[Feb 2013] M. Lysenko created a JavaScript port of Qhull using Emscripten (<a href="https://github.com/mikolalysenko/qhull-js">https://github.com/mikolalysenko/qhull-js</a>. 259 260<p> 261[Nov 2012] S.P. Ong wrote <a href=https://pypi.org/project/pyhull/>pyhull</a>, a Python wrapper for Qhull. 262 263<p> 264[Nov 2012] J. Milutinovich translated the Qhull home page into <a href="http://science.webhostinggeeks.com/qhull-prirucnik">Serbo-Croatian</a>. 265 266<p> 267[Nov 2011] Grasman, Gramacy, and Sterratt added <a href="http://geometry.r-forge.r-project.org/">Qhull in R</a> via their <a href"http://cran.r-project.org/web/packages/geometry/geometry.pdf">geometry</a> package. 268 269<p> 270[April 2010] V. Le Guilloux, Schmidtke, and Tuffery based <a href=http://fpocket.sourceforge.net>fpocket</a> on Qhull's qvornoi. It is a very fast, open source, protein pocket (cavity) detection algorithm ["Fpocket: An open source platform for ligand pocket detection", <a href="http://www.biomedcentral.com/1471-2105/10/168">www.biomedcentral.com</a>, 2009]. 271 272<p> 273[May 2009] R. Cervellione added Qhull to <a href=https://communities.bentley.com/other/old_site_member_blogs/peer_blogs/b/cervers_blog/posts/minimal-surface-for-gc>GC</a>. GC generates minimal surfaces. 274 275<p> 276[Jan 2009] F. Lee uses Voronoi diagrams to cluster data. He figured out a problem with missing hyperplane
276s generated by 'qvoronoi Fi Fo'. His data was nearly cospherical leading to merged facets. 277See option '<a href="../html/qh-optf.htm#Fv2">Fv</a>' for further discussion. 278 279<p> 280[Feb 2008] Finnigan wrote Python programs for constructing 3-d models of Voronoi diagrams computed by Qhull (zoetrope/voronoi3d) 281 282<p> 283[Nov 2007] Zolotykh wrote <a href="http://www.uic.unn.ru/~zny/skeleton/">Skeleton</a>. It generates all 284extreme rays of a polyhedral cone using the Double Description Method. It supports float, integer, and arbitrary precision arithmetic. 285 286<p> 287[Dec 2006] Geomview may be used on Windows. It provides a good visualization 288of Qhull's results. 289Geomview does not handle CRLF line endings, so pipe qhull's output through Cygwin's 290<code>dos2unix</code>. 291You will need to compile Geomview 292under Cygwin. For detailed instructions, see 293<a href="http://www.ee.surrey.ac.uk/Personal/L.Wood/software/SaVi/building-under-Windows/" 294>Building Savi and Geomview under Windows</a>. To run Geomview, launch X11 with <code>startx</code> and <code>/usr/X11R6/bin</code> in your PATH. Then run <code>./geomview</code> [L. Wood] 295 296<p> 297[Nov 2006] <a href="http://www.xcellerator.info/">xCellerator</a> is an extensible 298Mathematica package for signal transduction modeling. Their 299<a href="http://xlr8r.info/mPower/index.html">mPower</a> package 300includes Mathematica interfaces to qconvex, qdelaunay, and qvoronoi. 301 302<p> 303[Nov 2006] See <a href="http://www.blender.org">Blender</a> for open source 3D modeling, animation, rendering, post-production, interactive creation 304and playback. Qhull is part of their game engine. 305 306<p>[August 2006] Ruebenko wrote QHullInterface, for using Qhull with Mathematica. It is part of his IMTEK Mathematica Supplement. 307 308<p>[March 2006] Engwirda wrote <a href="http://www.mathworks.com/matlabcentral/fileexchange/25555-mesh2d-automatic-mesh-generation">mesh2d</a> for unstructured mesh generation in MATLAB. 309It is based on the iterative method of Persson and generally results in better quality meshes than delaunay refinement. 310 311<p>[September 2005] Hang Si wrote <a href=http://www.tetgen.org/>TetGen</a>, a quality tetrahedral mesh generator and Delaunay triangulator, 312and <a href=http://wias-berlin.de/software/tetgen/tetview.html>TetView</a>, a tetrahedral mesh and piecewise linear complex viewer. 313TetGen produces constrained 3-d Delaunay triangulations using Shewchuk's precise geometric predicates. 314 315<p>[March 2005] Ratcliff released QullLib 1.0 in Sept 2004. It is a Qhull library with a 316clean C++ interface for computing convex hulls. It was the basis for Qhull's RboxPoints.cpp. 317 318<p> 319[Feb 2005] A useful addition to Qhull would be computing the volumes of Voronoi regions. 320For an algorithm, see Max, N., "Computer assisted sphere packing in higher dimensions," 321<i>Proc. 2nd Conf. Visualization '91</i>, p. 102-108, IEEE, 1991. 322For an implementation, see 323Clarkson's <a href="http://www.netlib.org/voronoi/hull.html">hull</a> program. [A. Wouterse]. 324 325<p> 326[2005] <a href="http://library.msri.org/books/Book52/files/23liu.pdf">Li and Snoeyink</a> 327compared five implementations of 3D Delaunay tessellations on data with six digits of precision. 328Qhull used four times as much memory as CGAL and three times as much memory as Shewchuk's 329pyramid code. It ran substantially slower than these codes. Qhull's data structures are 330general dimension, while CGAL and pyramid data structures are 3D. As 64-bit code, Qhull's 331data structures nearly double in size and reduce the effectiveness of cache memory. 332 333<p> 334[Nov 2004] Bruynooghe integrated Qhull with Python and is using Qhull for 335mesh generation. See his <a href="https://pypi.org/project/Delny/">Delny</a> Python package 336[<a href=https://bitbucket.org/flub/delny/src/default/>home page</a>]. 337 338<p> 339[Fall 2004] J.E. Lloyd implemented the <a href=https://www.cs.ubc.ca/~lloyd/java/quickhull3d.html>QuickHull3D</a> 340in Java. As done in Qhull, he used facet merging to handle precision problems. 341D. Gregorius gave a <a href="http://media.steampowered.com/apps/valve/2014/DirkGregorius_ImplementingQuickHull.pdf">
341tutorial</a> 342on QhullHull at the 2014 Game Developers Conference. K. Johnston used QhullHull3D.java for <a href="https://github.com/kjohnston82/VariableStarAnalysis/">VariableStarAnalysis</a> (April 2019). 343 344<p> 345[July 2004] <a href=http://www.mathworks.com>Mathworks</a> released MATLAB R14 with Qhull 2002.1 and 346triangulated output. Triangulated output is significantly more 347accurate than MATLAB's prior use of joggled input. 348MATLAB uses Qhull for Delaunay triangulations, Voronoi diagrams, and convex hulls. 349[P. Anderson] 350 351<p> 352[Feb 2004] 353<a href=http://www.octave.org/>GNU Octave</a> 354[<a href=http://hg.savannah.gnu.org/hgweb/octave/file/63374982750b/scripts/geometry>Geometry</a>] 355upgraded to Qhull 2003.1 with triangulated input. 356Octave uses Qhull for Delaunay triangulations, Voronoi diagrams, and convex hulls. 357[R. Laboissiere]. 358 359<p>[Feb 2003] 360MATLAB implements <b>tsearch</b> by building the Delaunay 361triangulation and searching for the best facet of each test 362point. It should be faster to add the test sites at 363Qhull initialization and process them like coplanar points, 364but without searching nearly coplanar facets until the end. As 365with findDelaunay(), tricoplanar regions will need special 366processing. A later version of Qhull may implement tsearch. 367 368<p>[May 2001] Sugihara's "Robust geometric computation based on topological consistency" 369[ICCS 2001, LNCS 2072:12-26] is a good review of his topological approach to computational 370geometry. Qhull likewise produces topologically consistent structures. Qhull adds a geometric 371test of convexity that applies to imprecise data. Under certain assumptions, Qhull bounds the maximum 372geometric error. In practice, Qhull's maximum error is a small multiple of the minimum, maximum error. 373 374<p>[April 2001] <i>For Qhull library users.</i> 375The <a href=http://www.boost.org/libs/graph/doc/table_of_contents.html>BGL</a> 376Boost Graph Library [aka GGCL] provides C++ classes for graph data structures 377and algorithms [Dr. Dobb's 9/00 p. 29-38; OOPSLA '99 p. 399-414]. It is modelled after the 378Standard Template Library. It would provide a good interface to Qhull. 379If you are interested in adapting BGL to Qhull, please contact 380<a href="mailto:[email protected]">[email protected]</a>. 381 382<p> 383[2001] The Crust, Cocone, PowerCrust, and natural neighbor algorithms of Amenta, Bern, Boissonant, Cazals, Choi, Dey, Kolluri, 384and Leekha, use Voronoi diagrams to reconstruct surfaces from 385sampled points. They can guarantee that the output surface 386is geometrically close to the sampled surface. For a recent paper, see 387[Dey & Giesen, Symp. on Computational Geometry, 2001, p. 257-263]. 388For an implementation using Qhull, see Kumar's 389<a href=http://compgeom.com/~piyush/papers/revive.pdf>Reviver: 390A Practical Provable Surface Reconstructor</a> and his <a href=http://www.compgeom.com/~piyush/reviver/>Reviver home page</a>. Reviver uses joggled 391input with follow-on processing in exact arithmetic. Triangulated output 392may avoid the need for exact arithmetic. 393 394<p>[April 2000] 395Several Qhull users use the Visualization Toolkit (<a href=http://www.vtk.org/>VTK</a>) 396to visualize their results. It should be straightforward to rewrite the Geomview visualizations 397for VTK. If you use VTK with Qhull, please send how-to instructions and code 398to <a href=mailto:[email protected]>[email protected]</a>. 399 400<p>[July 1999] 401Comes and Ziegelmann published "An easy to use implementation of linear perturbations within CGAL", 402[WAE'99, LNCS 1668:169-182, 1999]. They eliminate degerneracy with a random perturbation of the input. 403This is similar to Qhull's joggled input. While Qhull's perturbation is random coordinates within a cube, 404their perturbation is random directions of fixed amplitude. 405 406<p> 407[1999] Devillers published an algorithm for deletion in Delaunay Triangulations 408[<i>ACM Symposium on Computational Geometry</i>, Minneapolis 1999]. He has 409implemented it in 3-d. It should be straightforward to implement 410in Qhull. 411 412<p>[1999] 413Mucke, et al, published an algorithm for fast randomized point location 414in Delaunay triangulations [<i>Computational Geometry: Theory and Applications</i>, 41512:63-83, 1999]. Qhull users frequently ask about point location in Delaunay
416triangulations. For other methods, see the <a href=../html/qh-faq.htm#vclosest>FAQ</a> 417 418<p>[1998] 419Shewchuk published an algorithm for constrained Delaunay 420triangulations [<i>ACM Symposium on Computational Geometry</i>, Minneapolis 1998]. 421An implementation of Shewchuk's algorithm would be a valuable 422addition to Qhull. 423 424<p>If your group would like to maintain and enhance Qhull, please 425send e-mail to <a href="mailto:[email protected]">[email protected]</a>. 426Project ideas include specialized versions, volumes of Voronoi 427regions, constrained Delaunay triangulations, and rewriting Qhull 428in C++ (see <a href="../html/qh-code.htm#enhance">Enhancements to Qhull</a>). 429Constrained Delaunay triangulations have many applications.</p> 430 431<p>To view graphical output under Windows, use Mathematica ('<a 432href="../html/qh-opto.htm#m">m</a>'), 433Maple ('<a href="../html/qh-optf.htm#FM">FM</a>'), 434 or Meyer's <a 435href="http://www.geom.uiuc.edu/~daeron/apps/">3d Java applet</a>. 436and OFF file format [use '<a href="../html/qh-opto.htm#o">o</a>' and 437delete the first line of output]. If you write VRML output for 438Qhull, please send e-mail to <a href="mailto:[email protected]">[email protected]</a>. 439</p> 440 441<h2><a href="#TOP">»</a> <a name="bugs">Bug reports</a>, notes, and work in progress</h2> 442 443<p>Please report problems to <a 444href="mailto:[email protected]">[email protected]</a>. 445</p> 446 447<p>Here are the problems in previous versions of Qhull by version and by date. 448Problems are listed in the most recent version, Except for the current version, they are fixed in more recent versions. 449See <a href="#problems">Known Problems</a> for problems 450in the current release of Qhull. 451See <a href="../src/Changes.txt">Change History</a> for fixed bugs and new features in each release.</p> 452 453<p><b>Qhull 2020.1</b></p> 454<ul> 455<li>The C++ interface contained unnecessary dependencies on C++11. 456<li>C++ Jave-style iterators used a pointer to container instead of a copy constructor. 457When used on temporary sets, subtle memory errors may occur. 458<li><code>/usr/local/lib/pkgconfig</code> for CMake debug builds named the files incorrectly. 459<li><code>QhullSet::toQList</code> (Qt only) failed to compile due to prototype and type errors. 460<li>QhullFacet_test.cpp contained an incorrect test of hyperplane epsilon. 461<li>Function documentation contained many broken links when installed to <code>/usr/local/include/libqhull*</code>. 462Use www.qhull.org instead. 463</ul> 464 465<p><b>Qhull 2019.1</b></p> 466<ul> 467<li>SOVERSION was not incremented despite substantial ABI breakage. 468<li>operator->() was defined incorrectly for QhullLinkedList::const_iterator. 469<li>merge_r.c/qh_appendmergeset,qh_appendvertexmerge,qh_mergefacet,qh_tracemerge: 470 fix error check of index for mergetypes 471</ul> 472 473<p><b>Qhull 2015.2</b></p> 474<ul> 475<li>qh_buildcone_onlygood ('Qg') corrupted memory if it called qh_delfacet. 476<li>qh_check_maxout did not include qh.DISTround when checking f.maxoutside 477<li>qh_distround did not acount for 'Rn' (random roundoff) in option 'QJn' 478<li>qh_findbestfacet should document that it may return an adjacent triangle for Delaunay triangulations [F. Drielsma] 479<li>qh_findfacet_all should not search visible facets or f.upperdelaunay facets [P. Virtanen, S. Dominguez, J.Arkin] 480<li>qh_findgood may report a bad facet for qh.GOODvertex ('QVn'). Restrict the search to good facets. 481<li>qh_freebuild deleted unattached ridges, leading to a double delete 482<li>qh_initial_hull tested 'maybe flipped' instead of 'clearly flipped'. As a result 483facets could be incorrectly oriented, leading immediately to 'Only 4 facets remain' [S. Caron, P. Virtanen, D. Sterratt, others] 484<li>qh_initstatistics was missing initialization. As a result, the final qh_checkoutput may be skipped. 485<li>qh_initstatistics cannot use qh_fprintf to report errors. Use qh_fprintf_stderr 486<li>qh_maxsimplex did not detect nearly flat simplices except for the last vertex. It assumed the max coordinate 487was approximately 1. As a result, Qhull reported false narrow hulls or false low dimensional inputs. [J.R. Roussel, D. Sterratt] 488<li>qh_option could overflow the qh.qhull_options buffer 489<li>qh_partitionpoint could leave an outside point before qh.next_facet, leading to a skipped point. 490<li>qh_stddev was incorrect. It should be sqrt of absolute value. 491<br> 492<p> 493<li>'Qbb' scaled the last coordinate to qh.MAXwidth causing loss of precision. It should be qh.MAXabs_coord. 494<li>'rbox' and 'user_eg3' returned non-zero exit status for their help prompt. Should be 0. 495<li>'rbox Cn,r,m' does not produce points for 'rbox r' 496<li>An error in qh_initqhull_start2 could loop forever. Need to set qh.NOerrexit 497<li>Do not call qh_check_points ('Tv') if reporting an error and qh.FORCEoutput ('Po') 498<li>If 'd' or 'v' was used with 'H', memory corruption occurred. Should be disallowed. 499<li>Improved searching of coplanar facets by qh_findbesthorizon. 500<li>Options '<a href="../html/qh-optp.htm#Pdk">Pdk</a>' and '<a href="../html/qh-optp.htm#Pdk">Pdk</a>' 501always returned the closest facet. This should only occur with option '<a href="../html/qh-optp.htm#Pg">Pg</a>'. 502<li>PointCoordinates::appendPoints should not require whitespace after a point 503<li>Setting qh.MINoutside could lead to verification ('Tv') failures. Fixed by 504setting qh.KEEPnearinside and calling qh_partitionpoint in qh_partitionall 505</ul> 506 507<p><b>Qhull 2015.1</b></p> 508<ul> 509<li>The C++ interface has a memory leak (e.g., 'user-eg3 eg-100') [M. Sandim]. 510<li>QhullLinkList::last() and back() returned a reference to computed results (T&) instead of the results (T) 511<li>CMakeModules was missing from the distribution [C. Rosenvik] 512<li>The DevStudio 2012 builds did not work. 513</ul> 514 515<p><b>Qhull 2012.1</b></p> 516 517<ul> 518<li>Point partition may lead to a rare "all facets flipped or upper Delaunay" [error QH6228, J. Metz, L. Fiaschi, N. Bowler, A. Liebscher, V. Vieira, N. Rhinehart, N. Vance, P. Shafer]. 519<li>If errfile is incorrectly NULL in qh_new_qhull(), qhull goes into an error reporting loop (<a href="https://bugs.debian.org/738339">https://bugs.debian.org/738339</a>) [D. Haley] 520<li>Coverity reported errors for logging after 'delete' and missing checks [K. Schwehr] 521<li>qh_findbestfacet has an incorrect test for isoutside [Coverity, K. Schwehr] 522<li>QHULL_UNUSED is incorrect for C compilers that define __INTEL_COMPILER [R. Stogner] 523</ul> 524 525<p><b>Qhull 2011.2</b></p> 526 527<ul> 528<li>gcc 4 requires -fno-strict-aliasing to compile qset.c. Otherwise qset segfaults on most input. 529<li>qh_setappend_set fails to append an empty set to a full set (does not occur in qhull). An error or segfault occurs when using the resulting set. 530</ul> 531 532<p><b>Qhull 2011.1</b></p> 533 534<ul> 535<li>Qhull-go reports a not-compatible error. The code itself is OK. 536<li>Qhull may silently overflow on 64-bit hosts (e.g., rbox 64 D32 | qhull). [X. Cheng] 537<li>If programmers set outfile=0, qh_prepare_output is not called. Triangulation, area, volume, Voronoi vertices, statistics, good facets are not done. [A. Aldoma] 538<li>gcc 4 requires -fno-strict-aliasing to compile qset.c. Otherwise qset segfaults on most input. 539<li>qh_setappend_set fails to append an empty set to a full set (does not occur in qhull). An error or segfault occurs when using the resulting set. 540</ul> 541 542<p><b>Qhull 2010.1</b></p> 543 544<ul> 545<li>Qhull-go reports a not-compatible error on 64-bit hosts. The code itself is OK. 546<li>If programmers set outfile=0, qh_prepare_output is not called. Triangulation, area, volume, Voronoi vertices, statistics, good facets are not done. 547<li>Output of QhullVertex throws error QH10034 and does not define defineVertexNeighbors(). [renangms] 548<li>QhullFacet::PrintRideges did not check hasNextRidge3d 549<li>Qhull may silently overflow on 64-bit hosts (e.g., rbox 64 D32 | qhull). 550<li>gcc 4 requires -fno-strict-aliasing to compile qset.c. Otherwise qset segfaults on most input. 551<li>qh_setappend_set fails to append an empty set to a full set (does not occur in qhull). An error or segfault occurs when using the resulting set. 552</ul> 553 554<p><b>Qhull 2009.1</b></p> 555 556<ul> 557<li>qh_gethash causes an overwrite or segfault on 32-bit hosts running in high memory (<a href="http://www.qhull.org/download/poly.c-qh_gethash.patch">poly.c-qh_gethash.patch</a>). 558<li>'TO' and 'TI' options did not allow filenames starting with 'd' or 'v'. 559<li>rbox ignored flags that were not separated by spaces 560<li>qh_pointid was incorrect if ptr_intT was unsigned 561<li>qh_build_withrestart did not clear qh.STOPcone for option 'QJn' 562<li>qh_findfacet_all used 'REALmin' instead of '-REALmax' so the search did not always work. [L.A. Taylor] 563<li>Triangulated facets freed facet->centrum twice. 564<li>findbest_test initialized mindist incorrectly if testcentrum=0 [Ratcliff] 565<li>rbox could overflow the 'command' buffer when appending seedbuf. 566<li>qh_initqhull_globals used an incorrect upper bound for the sanity check of qh_RANDOMmax 567<li>qh_eachvoronoi segfaults if fp=0 and printvridge=1. [D. Szczerba] 568<li>qhmem computed totshort incorrectly 569<li>many warnings reported when compiled [kwilliams] 570<li>Qhull may silently overflow on 64-bit hosts (e.g., rbox 64 D32 | qhull). 571<li>gcc 4 requires -fno-strict-aliasing to compile qset.c. Otherwise qset segfaults on most input. 572<li>qh_setappend_set fails to append an empty set to a full set (does not occur in qhull). An error or segfault occurs when using the resulting set. 573</ul> 574 575<p><b>Qhull 2003.1</b></p> 576 577<ul> 578<li>Undefined evaluation order for pre-incremented arguments to strtod in rbox 579<li>qh_produce_output and qh_initstatistics used '%d' instead of '%lu' for size_t arguments 580<li>See Qhull 2009.1 for other problems. 581</ul> 582 583<p><b>Problems by date</b></p> 584<p> 585[Sept 2011] <i>For Qhull library users.</i>
585 qh_new_qhull should call qh_prepare_output if outfile is not defined [A. Aldoma]. 586qh_prepare_output handles options that are computed after the convex hull (e.g., area and volume). 587 588<p> 589[Apr 2011] In 3-d and higher, option '<a href="../html/qh-optq.htm#Qt">Qt</a>' does not produce conforming triangulations 590for adjacent, non-simplicial facets. This remains an open problem. See <a href="#problems">Known Problems</a>. Related entries are [May 2007], and [Dec 2006] below. 591 592<p> 593[Apr 2011] qh_newhashtable, qh_setnew, and qh_memalloc should report an error if the size argument is negative [X. Cheng]. 594Negative arguments may occur on 64-bit hosts due to integer overflow. Qhull uses 32-bit ints for identifiers, counts, and sizes. 595 596<p> 597[Jan 2009] Qhull's qh_gethash [poly.c] allows a negative return value, leading to an overwrite 598 or segfault. 599 Upgrade to 2011.2 or 2009.1.2 or apply <a href=http://www.qhull.org/download/poly.c-qh_gethash.patch>poly.c-qh_gethash.patch</a>. 600 . 601<p> 602[Apr 2008] Qhull's qset.c does not compile correctly under gcc 4.1 and later with option -O2 (4.0.1 works OK [B. Shapiro]). 603These versions of gcc work correctly 604when compiled with -fno-strict-aliasing [R. Laboissiere]. 605gcc 4.4 appears to work OK. 606A workaround is to replace FOREACHsetelement_ with FOREACHsetelement_i_ 607in qh_setlast and qh_setappend of qset.c [A. Rossiter]. 608D. Szczerba also reported the problem. 609The following patch works on both 32-bit (ix86) and 61064-bit (amd64) Linux PCs [S.D. Lee]. 611<pre> 612--- Makefile 2003-12-31 11:20:50.000000000 +0800 613+++ Makefile 2008-04-09 15:20:13.192023303 +0800 614@@ -95,7 +95,8 @@ 615 merge.o: $(HFILES) 616 poly.o: $(HFILES) 617 poly2.o: $(HFILES) 618-qset.o: qset.h mem.h 619+qset.o: qset.c qset.h mem.h 620+ $(CC) -c $(CCOPTS1) -fno-strict-aliasing $< 621 stat.o: $(HFILES) 622 user.o: $(HFILES) 623</pre> 624 625 626<p> 627[May 2007] 628de Visser produced an <a href="Delaunay3Dgridinvalid.png">example</a> of the Dec 2006 'Qt' bug (see following) using 629Matlab. Notice that the triangulation is nonconforming between the non-simplicial regions (i.e., the cubes). 630Option 'QJ1e-8' may be useful as a workaround. It forces a triagulation by perturbing the input sites. 631 632<p> 633[Dec 2006] In 3-d and higher with adjacent, non-simplicial regions, 634the output triangulation generated by option 'Qt' does not 635conform to the triangulation of the region's ridges, nor to the triangulation 636of its neighboring facets. For example, if you have a regular array of 637input sites, their Delaunay triangulation consists of cubes. 638Option 'Qt' will triangulate each cube into tetrahedra. Within 639each cube, the triangulation is consistent, but it is not necessarily 640consistent between adjacent cubes [C. Bertoglio; C. de Visser]. To visualize the qhull bug in geomview, load 641Qhull-Qt-bug.oogl as generated by 642<blockquote> 643 rbox 32 M1,0,1 | qhull d Qbb Qt Gt | dos2unix > Qhull-Qt-bug.oogl 644</blockquote> 645 646<p> 647[August 2004] Qhull may incorrectly report a coplanar input set if the max or min points 648along the coordinate axes are nearly coplanar and they include nearly 649coincident subsets. 650If so, the point set and inital simplex may be full dimensional, 651while at the same time, the initial simplex is not clearly convex. 652Other point sets can cause the same problem. 653These cases appear to be unlikely for most users. A workaround is to use 654option 'Qs'. [E. Voth] 655 656<p> 657[Jan 2004] <i>For qhalf users.</i> The identity pipe for Qhull reveals some precision questions for 658halfspace intersections. The identity pipe creates the convex hull of
659a set of points and intersects the facets' hyperplanes. It should return the input 660points, but narrow distributions may drop points while offset distributions may add 661points. It may be better to normalize the input set about the origin. 662For example, compare the first results with the later two results: [T. Abraham] 663<blockquote> 664 rbox 100 s t | tee r | qconvex FV n | qhalf Fp | cat - r | /bin/sort -n | tail 665<br/> 666 rbox 100 L1e5 t | tee r | qconvex FV n | qhalf Fp | cat - r | /bin/sort -n | tail 667<br/> 668 rbox 100 s O10 t | tee r | qconvex FV n | qhalf Fp | cat - r | /bin/sort -n | tail 669</blockquote> 670 671<p> 672[Dec 2003] <i>For Qhull library users.</i> If you are writing code for Delaunay triangulations using 673the Qhull library, findDelaunay() in user_eg.c does not work for triangulated 674ouput ('Qt'). If the input sites are cospherical, findDelaunay will return 675one of several "tricoplanar" regions. Additional code will 676be needed to identify the correct region. 677See <a href="../html/qh-code.htm#findfacet">locate a facet with 678qh_findbestfacet()</a>. 679 680</blockquote> 681<h2><a href="#TOP">»</a> <a name="users">How</a> is Qhull used?</h2> 682<blockquote> 683 684<p>If you find Qhull helpful, please let me know about your 685application. Send e-mail to <a href="mailto:[email protected]">[email protected]</a> 686and I'll add you to the list below. If you publish a paper that 687mentions Qhull, please send a reference and abstract. 688Please use the following citation. 689See <a href="#highlights">Highlights</a> and 690<a href="http://scholar.google.com/scholar?cites=13151392091060773178&as_sdt=40000005">Google Scholar</a> 691for other Qhull references. 692 693<blockquote> 694 Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., 695 "The Quickhull algorithm for convex hulls," <i>ACM Transactions on Mathematical Software</i>, 696 22(4):469-483, Dec 1996, http://www.qhull.org 697</blockquote> 698<p> 699<b>Qhull Users</b> 700 701<ul> 702<li>[Apr 2019] 703K. Johnston incorporated Lloyd's QuickHull3D.java as part of his VariableStarAnalysis. 704See <a href="https://github.com/kjohnston82/VariableStarAnalysis/blob/master/common/utilities/math-utilities/src/main/java/fit/astro/vsa/common/utilities/math/geometry/convex/QuickHull3D.java">VariableStarAnalysis/blob/master/common/utilities/math-utilities/.../QuickHull3D.java</a> (github) 705and QuickHull3D.java under 'Fall 2004' <a href="#highlights">highlights</a> above. 706<p> 707<li>[Mar 2019] S. V. Rakovic uses Qhull for model predictive control. 708<p> 709<li>[Jun 2018] F. Drielsma published <a href="https://pos.sissa.it/295/099">Measurement of Phase Space Density Evolution in MICE</a> on the Muon Ionization Cooling Experiment (MICE). He used 710Qhull to compute the volume of the fractional emittance. 711<p> 712<li>[Feb 2018] J. Mangelson used Qhull for some research on convex robotic trajectory alignment. 713<p> 714<li>[Feb 2017] Using Qhull, Easwar added 3-d convex hulls to OriginLab <a href="http://www.originlab.com/fileExchange/details.aspx?fid=356">DataAnalysis > 3D Convex Hull</a>. 715<p> 716<li>[Oct 2016] J. de Brumath uses Qhull for the <a href="https://cfdm.forumperso.com/t217-0072-09-10-16-jerome-bertin-215-km-pas-homologue">CFDM : French Cup of Distance with Powered Paraglider</a> 717(<a href="https://cfdm.forumperso.com/f2-vols-homologues">all entries</a>, <a href="https://cfdm.forumperso.com/t563-cfdm-in-english?tt=1">explanation</a>). 718The whole competition is based on the convex hull of the GPS trace of each submitted flight, 719<p> 720<li>[Jul 2016] M. Faes computes the volume of 4-d and higher convex hulls for non-probabilistic uncertainty quantification. 721<p> 722<li>[Feb 2016] C. Carson and J. Levine studied x-ray computed tomographic images of foamed cement and their 2-d cross sections. Other applications 723include porous media transport and crack-tip propagation [<a href=https://onlinelibrary.wiley.com/doi/abs/10.1111/jmi.12388>Journal of Microscopy, 2016</a>. 724<p> 725<li>[Jul 2015] A. Tomilov implemented the Quickhull algorithm for points in general dimension (<a href="https://github.com/tomilov/quickhull/blob/master/include/quickhull.hpp">quickhull.hpp</a>, 726<a href="http://habrahabr.ru/post/245221/">doc-ru</a>). 727It checks that the output is clearly convex. 728<p> 729<li>[Jun 2015] G. Sicherman determined the smalled polyomino whose convex hull is an N-gon. 730<p> 731<li>[Jun 2015] C. Carson computes 3-d tessellations of closed pore materials. He uses the Scipy implementation of Qhull. 732<p> 733<li>[Nov 2014] Heylen and Scheunders used Qhull in their algorithm to estimate the pixel purity index for hyperspectral image processing [<a href="http://ieeexplore.ieee.org/iel5/36/4358825/06392932.pdf?arnumber=6392932">Tran. Geosci. Remote Sensing</a>, 2003]. 734<p> 735<li>[Aug 2014] J. Pavia analyzed proportion configurations that produce a particular share of seats in a Parliament after using d'hondt rule and other constraints. 736<p> 737<li>[Jul 2014] Q. Zhang constructed surrogate models for mixed-integer linear programs and data-driven optimizations 738<p> 739<li>[Jan 2014] <a href="http://niftools.sourceforge.net/wiki/NifTools">NifTools</a> includes Qhull for building the <a href="http://www.emergent.net/">NetImmerse/GameBryo</a> game engine. 740<p> 741<li>[Oct 2013] M. Peigney studied the quasiconvex hull of energy-minimizing, stress-free strains of martensitic structures (<a href="http://www.sciencedirect.com/science/article/pii/S0022509613000070"><i>J. Mechanics and Physics of Solids</i></a>, <b>61</b>.6 (2013). 742<p> 743<li>[Apr 2013] Y. Xu found galaxy clusters from the Second Center for Astrophysics Galaxy Catalog (<a href="http://adsabs.harvard.edu/abs/2004AAS...20516106X">abstract</a>). They match the known clusters very well. 744<p> 745<li>[Mar 2013] <a href="http://www.leica-geosystems.com/en">Leica Geosystems</a> uses Qhull to help view and process point clouds from 3d scanners. 746<p> 747<li>[Mar 2013] M. Freese added Qhull to <a href="http://www.coppeliarobotics.com/">v-rep</a>, a virtual robot experimentation platform. 748<p> 749<li>[Feb 2013] M. Treacy finds open space in crystalline zeolite structures. 750<p> 751<li>[July 2012] B. Bahlberg et. al. measured the technical inefficiency of a firm using the principle of least action.
752They used Qhull to determine the supporting hyperplanes for the efficiency boundary. 753<p> 754<li>[May 2012] <a href="http://www.khirevich.com">Khirevich</a> et al. 755studied advection-diffusion transport in the pore space of random 756sphere packings, used Qhull to analyze geometry of the pore space, and 757based on this analysis derived scalar geometrical descriptors 758demonstrating a strong correlation with the simulated transport 759coefficients (<a 760href="http://dx.doi.org/10.1016/j.chroma.2010.05.019">hydrodynamic 761dispersion coefficient</a> and <a 762href="http://dx.doi.org/10.1016/j.chroma.2011.07.066">effective 763diffusion coefficient</a>). 764<p> 765<li>[Dec 2010] <a href="http://www.flashfotoinc.com/">Flash Foto, Inc</a> uses qhull for face-hair segmentation, which separates the face and 766hair of a person from the background - on most people, the top of the head is convex. 767 768<p> 769<li>[Nov 2010] Robert's <a href="https://www.hexagonmi.com/products/software/pc-dmis">PC-DMIS</a> controls coordinate 770measuring machines for manufactured parts. It uses qhull to compute some of the geometry from sampled points. 771 772<p> 773<li>[Nov 2010] Vasilakis and Fudos computed the convex hull and half-space intersection for their 774refined skeleton extration method. See "GPU rigid skinning based on a refined skeletonization method" 775[<a href="http://onlinelibrary.wiley.com/doi/10.1002/cav.382/abstract">paper</a>]. 776 777<p> 778<li>[Aug 2010] Brinch and Hogerheijde developed LIME for 779solving the molecular and atomic excitation and radiation transfer problem in a molecular gas and predicting emergent spectra [<a href="http://adsabs.harvard.edu/abs/2010arXiv1008.1492B">abstract and paper</a>] 780 781<p> 782<li>[June 2010] Reuter triangulates point clouds from astrophysical Smoothed-Particle Hydrodynamics 783simulations. The output is used for visualization. 784See their <a href="https://docplayer.net/18594561-Scientific-visualization-of-hpc-simulation-data-introduction-and-overview-on-mpg-projects.html">project description</a>. 785 786<p> 787<li>[Mar 2010] Fallavollita integrated fluoroscopic and electrical data from RF catheters 788to assist cardiac ablation procedures [<a href="https://link.springer.com/article/10.1155/2010/871409">paper</a>] 789 790<p> 791<li>[Feb 2010] Mac Dermed and Isbell produced an approximation algorithm for stochastic 792games with multi-agent reinforcement learning 793[<a href="http://books.nips.cc/papers/files/nips22/NIPS2009_1185.pdf">paper</a>]; 794 795<p> 796<li>[April 2009] Dalbey constructed predictive simulation and model based hazard maps of geophysical mass flows. 797 798<p> 799<li>[April 2009] Kruip and Paaredekooper construct Voronoi-Delaunay structures for their radiative transfer method SimpleX. 800 801<p> 802<li>[June 2008] Jena computed the surface mesh for point clouds generated from radiotherapy treatment planning data in brain tumours. 803 804<p> 805<li>[May 2008] Bhamidipati modeled grain geometry in a polycrystalline material. 806 807<p> 808<li>[May 2007] Mughal studied topological defects in the 809crystalline state of one-component plasmas of non-uniform density 810[<a href="http://arxiv.org/abs/cond-mat/0702652">paper</a>; 811to appear in <i>Phy. Re E.</i>] 812 813<p> 814<li>[April 2007] Grossman created metal sculptures with a mathematical twist, 815<a href="http://www.bathsheba.com">Bathsheba Sculpture</a>. 816 817<p> 818<li>[April 2007] <a href="http://www.antiprism.com">Antiprism</a> is a collection of programs 819for generating, manipulating, transforming, and visualizing polyhedra. Includes 820transforms from OFF format to VRML and other formats. 821 822<p> 823<li>[April 2007] Myers' <a href="http://www.tc.cornell.edu/~myers/PyXL">PyXL</a>
824modeled synthetic microstructrues of polycrystalline materials. 825 826<p> 827<li>[Mar 2007] Rodrigues modeled damping controllers for electric power systems 828 829<p> 830<li>[Mar 2007] Yoshizawa approximated the 3-D medial axis with a Voronoi-based 831<a href="http://www2.riken.jp/brict/Yoshizawa/Research/Skeleton.html">skeletal mesh</a>. 832 833 834<p> 835<li>[Mar 2007] blitz3d used a Qhull 1.0 library to simplify collision tests. 836 837<p> 838<li>[Dec 2006] Boyle located the nuclei of cells in a devaloping embryo (e.g., 839<a href="http://waterston.gs.washington.edu/~biowolp/boundaries/p15P.png">section</a> thru a C elgans embryo at the 88 cell stage). 840 841<p> 842<li>[Nov 2006] Oesterle and Knauss of KOOK Architecture visualized 3-d Voronoi diagrams 843with Rhino. See the <a href=../html/qvoronoi.htm>qvoronoi</a> page. 844<p> 845<li>[Nov 2006] Gardener generated triangular meshes for point cloud data in 846Daylon's <a href="http://www.daylongraphics.com/products/leveller/">Leveller</a>, 847a heightfield/bumpmap/terrain modeler. 848A common source of point cloud data is ocean seafloor scans or 849radar altimetry. 850 851<p> 852<li>[Nov 2006] King wrote <a href="http://www.math.umd.edu/~hck/MorseExtract.html">MorseExtract</a> to convert 853functions over a 3-d simplicial complex to a discrete Morse function in the sense of Forman. 854 855<p> 856 <li>[June 2006] Belov thermodynamically calculated the phase diagram of heterogeneous systems using Gibbs energies 857 [<i>Russian J Physical Chemistry</i>, <b>77</b>.10:1685-1694, 2003]. 858<p> 859 <li>[March 2006] Schmeja measured the area and volume of young star clusters. See 860 S. Schmeja & R.S. Klessen, "Evolving structures of star-forming clusters," 861<i>Astronomy & Astrophysics</i>, 449 (2006), 862151, <a href="http://arxiv.org/abs/astro-ph/0511448">preprint</a>. 863 <p> 864 <li>[Dec 2005] Petrek uses qconvex in <a href="http://loschmidt.chemi.muni.cz/caver/index.php">CAVER</a>. 865CAVER provides rapid, accurate and fully automated calculation of pathways leading from 866buried cavities to outside solvent in static and dynamic protein structures. Study of 867these pathways is important in drug design and molecular enzymology to understand 868binding of inhibitors to the receptors, substrate binding and product egress from 869the enzyme active sites. Calculated pathways can be visualized by graphic program 870PyMol dissecting anatomy and dynamics of entrance tunnels. 871<p> 872 <li>[Nov 2005] Ritzerveld, Icke, and Rijkhorst computed radiation transport on unstructured 873 grids using their SimpleX method (<a href="http://arxiv.org/abs/astro-ph/0312301">paper</a>). They performed large scale cosmological simulations on a 874 simple desktop computer. 875 For archived samples, see 876 <a href="http://web.archive.org/web/20100206063538/http://www.strw.leidenuniv.nl/~ritzervj/Research/Docs/TriangRad.pdf">TrianRad poster</a> 877and <a href="http://web.archive.org/web/20080109194157/http://www.strw.leidenuniv.nl/~ritzervj/Research/Reionization.html">Reionization</a>. 878 879 <p> 880 <li>[May 2005] Ferri et al evaluated classifiers in machine learning by computing the volume under 881 receiver operating characteristic surfaces [Ferri, C., Hern?ndez-Orallo, J.. Salido, M.A., 882 "Volume under the ROC Surface for Multi-class Problems," 883 <i>14th European Conference on Machine Learning</i>, 108-120, 2003]. 884 <p> 885 <li>[April 2005] Landman found asymptotic solutions of boundary value problems 886 involving vibrations of rotating thin shells of revolution. The algorithm 887 permits the symbolic integration of the governing equations for any range of 888 values of the parameters appearing in these equations. 889 <p> 890 <li>[Feb 2005] Jaramillo analyzed sesmic data using Voronoi diagrams as described in Gardner and Canning, 891 "Reducing 3-D acquisition footprint for 3-D DMO and 3-D prestack migration," 892 <i>Geophysics</i>, VOL 63, No 4 (July-August 1998). 893 <p> 894 <li>[Jan 2005] Piche identified thermodynamically valid sets of coexisting minerals (phases) for any given rock composition. 895 <p> 896 <li>[Jan 2005] Galvao investigated a conjecture concerning probability polytopes arising from 897 measurements in quantum theory. He used Qhull to compute the convex hull of 30 points in 898 24 dimensions. See Galvao, E.F., "Discrete Wigner functions and quantum computational speed-up," 899 <a href=http://aps.arxiv.org/abs/quant-ph/0405070>to be published</a> in a journal of <i>Physics Review A</i>. 900 <p> 901 <li>[Sept 2004] Xu found galaxy clusters at Los Alamos National Lab. 902 <p> 903 <li>[August 2004] Casale studied bottleneck analysis of queueing networks models. 904 See Casale G., Serazzi G., 905 "Bottlenecks Identification in Multiclass Queueing Networks using Convex Polytopes," 906 <i>Proc. 12th IEEE/ACM Inter. Symp. on Modeling, Analysis, and Simulation of Comp. and 907 Tlc. Systems (MASCOTS 2004)</i> 908 (<a href="http://www.elet.polimi.it/upload/casale/pubs/casale04bottlenecks.pdf">PDF</a>). 909 <p> 910 <li>[July 2004] Moon is using Qhull to determine 911 the atomistic configurations at the grain boundaries of materials. 912 Knowledge on local volume along grain boundary gives insight on the 913 segregation phenomena. 914 <p> 915 <li>[June 2004] Taylor found the attainable region of a set of chemical reactions. 916 <p> 917 <li>[May 2004] Erleben added Qhull to <a href=http://www.opentissue.org>OpenTIssue</a>: An Open-source Library for Physics-based Animation. 918 <p> 919 920 <li>[Mar 2004] From Dr. Anis Limaiem, Wilcox Associates (PC-DMIS): 921 <blockquote> 922 I started using qhull a couple of weeks ago. It is really an excellent tool. Even though it is not 923 written in an API form and is not object oriented, once you understand its data structure and its different 924 features you can do miracles . I used it to implement curve and surface reconstruction using the crust algorithm 925 as well as discrete curvature estimation. 926 </blockquote> 927 <p> 928 929 <li>[Mar 2004] Errami used Qhull to tessellate protein surfaces in <a href=https://www.researchgate.net/publication/7682562_Friend_an_integrated_analytical_front-end_application_for_bioinformatics>Friend</a>. 930 Qhull was much faster than their previous implementation. 931 Friend is aimed to interactively manipulate hundreds of proteins, visualize spatial structures, amino-acid and nucleotide sequences and alignments, active and binding sites, fragments, and domains in protein and gene families. 932 <p> 933 934 <li>[Feb 2004] Laboissiere <i>et. al.</i> used Qhull in the scientific plotting 935 library, <a href=http://plplot.sourceforge.net/>PLplot</a>. They used Qhull 936 to obtain grid data from irregularly sampled data 937 [<a href=http://plplot.sourceforge.net/examples-data/demo21/x21.03.png>Examples</a>]. 938 <p> 939 940 <li>[Feb 2004] Neyrinck found haloes in cosmological N-body simulations 941 [<a href=http://skysrv.pha.jhu.edu/~neyrinck/voboz/>VOBOZ</a>]. These 942 simulations simulate the gravitational clustering of dark-matter particles 943 in the universe, which form clumps where galaxies can form, called haloes. 944 He used Qhull to find the Voronoi diagram of these particles, which finds 945 both a natural set of neighbors and an estimate of the density 946 (1/Volume(Voronoi cell)). He also used Qhull to find the volume of each 947 cell. 948 <p> 949 <li>[Jan 2004] Shea released 950 <a href=https://sourceforge.net/projects/tesselsphere/>TesselSphere 1.1</a>. It uses 951 Qhull to generate vertexia for rendering pollen, viruses and radiolaria (an 952 <a href=https://a.fsdn.com/con/app/proj/tesselsphere/screenshots/scheherazade_01a.jpg/max/max/1>example</a>). 953 <p> 954 955 <li>Alcock and Hare studied the excited states of particles 956 on a sphere. </li> 957 <li>Alfs simulated the kinematic configuration control of redundant robots. 958 <li>Allen et al. computed support structures for objects in 959 layered manufacturing [submitted to <i>Journal of Design & 960Manufacturing</i>, 1995]. </li> 961 <li>Archer wrote the game 'VGA Planets'. It uses Voronoi 962 diagrams for the political maps of galaxies. </li> 963 <li>Bapat computed the straightness and flatness tolerance 964 for a set of Coordinate Measuring Machine data points. </li> 965 <li> Bacik rendered the great outdoors with <a href=http://www.gamasutra.com/features/20020717/bacik_04.htm>fast occlusion culling</a> 966 <li>Bishop studied phase field simulations of microstructural 967evolution in ceramics. 968 <li>Begnis computed grain boundaries for simulating the 969 precipitation of carbo-nitrides in a nitrided alloyed 970 steel. </li> 971 <li>Belsis classified molecules by their biological activity. 972 </li> 973 <li>Blekas, Likas, and Stafylopatis built a neural network classifier based on 974geometrical fuzzy sets [<i>IEEE International Conference on Tools with 975Artificial Intelligence</i> (ICTAI'97), Nov. 1997} 976 <li>Boardman determined the principal components of spectral 977 data. </li> 978 <li>Bolson et al. analyzed 3-d models of heart chambers. </li> 979 <li>Bordignon, [<i>Journal of 980Guidance, Control, and Dynamics</i>, 18.5, 1995]. 981 <li>
981Braun estimated the emittance of extracted beams from the 982 Tevatron Fixed Target lattice. </li> 983 <li>Bromley studied the rotation of a supermassive black hole 984 in active galaxy MCG-6-30-15. </li> 985 <li>Buddenhagen visualized the <a href="http://www.buddenbooks.com/jb/pack/sphere/mult/multpics.htm">polyhedra</a> 986 that maximized the minimum distance between vertices. 987 <li>Butte used Qhull for x-ray crystallography research. 988 <li>Cameron wrote <a 989 href="http://www.comlab.ox.ac.uk/oucl/users/stephen.cameron/distances.html">code</a> 990 to compute the distance between convex polyhedra. </li> 991 <li>Cornell's <a href=http://pikachu.tc.cornell.edu/Research/CompMatSci/Multiscale>Multiscale 992 Materials Modeling Collaboration</a> tessellated a 993 <a href=http://www.tc.cornell.edu/Research/CMI/Multiscale/PictureGallery/polyc10000.jpg>cube with 10000 grains</a>. 994 <li><a 995 href="http://www.fracturedreservoirs.com/niper/database/reports/696/frdf696.htm">Dershowitz</a> 996 improved the secondary recovery from fractured oil 997 reservoirs. </li> 998 <li>Didwania computed the Delaunay triangulation for random 999 sphere packings. </li> 1000 <li>Donolato modelled multicrystalline solar cells. [<i>Semiconductor Science and Technology</i>, 99/00?]</li> 1001 <li>Eberwein determined the operating characteristics of 1002 process equipment. </li> 1003 <li>Ehmann implemented <a href=http://www.cs.unc.edu/~geom/SWIFT++/>SWIFT++</a> for collision detection. 1004 <li>Ekawati and Bahri assessed the controllability of an 1005 industrial five effects evaporator process utilizing the Modified Dynamic Operability Framework. 1006 [submitted to <i>Journal of Process Control</i>, April 2002] 1007 <li>Faken studied the structure of high-dimensional clusters.</li> 1008 <li>Gibson studied the simultaneous stabilization of two 1009 systems.</li> 1010 <li>Goddyn studied circuits of matroids that form a Hilbert 1011 base. </li> 1012 <li>Goslinga investigated stationary and optimal solutions to 1013 the <a href=http://www.geom.uiuc.edu/~bradb/M33_OPT.jpg>Points on a Sphere</a> problem.</li> 1014 <li>Grenestedt generated cell structures of closed cell 3D 1015 cellular solids (e.g., expanded PVC and foamed metals). </li> 1016 <li>Grundmann designed non-linear controllers for controlling 1017 vibration [Ph.D. thesis, 1018 "Robust Control of a Two-Mass-Oscillator by linear State Feedback and Nonlinear, Time-Optimal Control Rules," 1019 TU Dresden 1997]. </li> 1020 <li>Guyler used Qhull and MATLAB to visualize the printing gamuts of 1021 various wide gamut ink systems in 3D true color. Qhull 1022 solved their previous connectivity problems with gamut 1023 surface visualization.</li> 1024 <li>Habel added Qhull to <a href=http://www.octave.org/>GNU Octave</a> for 1025 <a href=https://octave.org/doc/v4.4.0/Delaunay-Triangulation.html>Delaunay triangulation</a>, 1026 <a href=https://octave.org/doc/v4.4.0/Voronoi-Diagrams.html>Voronoi Diagrams</a> and 1027 <a href=https://octave.org/doc/v4.4.0/Convex-Hull.html>Convex Hull</a>. 1028 Octave is an open source clone of MATLAB. 1029 <li>Harmon calculated the 1030 morphological disparity among groups of species in the context of their 1031 evolutionary history.</li> 1032 <li>Harris reproduced some of Zilles's work on human brain 1033 cortical convolution measurement. </li> 1034 <li>Hase found the largest gaps in between the reference points of 1035 of a global reference frame. This was work for the 1036 Transportable Integrated Geodetic Observatory. 1037 <li>Hemkemeier constructed a very dense sphere packing of the 1038 E^9 lattice. </li> 1039 <li>Hirota reconstructed the surface of a patient's body from 1040 sampled points. </li> 1041 <li>Holley studied globular protein folding by computing the 1042 convex hull of hydrophobic sidechain atoms. </li> 1043 <li>Indumathi classified handwritten digits. </li> 1044 <li>
1044Ierapetritou developed and analyzed efficient models and 1045 solution methodologies for product and process design 1046 and process operations.</li> 1047 <li>Irisa extended scaled particle theory and calculated the 1048 hydration free energy of protein. </li> 1049 <li>Jackson analyzed and visualized contaminant plumes based 1050 on groundwater samples. </li> 1051 <li>Jervis and Briant studied stable vortex arrays in rotating superfluid helium.</li> 1052 <li>Johnson analyzed remote sensor images with 300,000+ pixels, each with 44 channels of spectral data. 1053 <li>Joshi et. al. studied the spatial organization of a 1054 deciduous forest. </li> 1055 <li>Kelly computed the volume of home ranges for ringed seals 1056 under the Arctic icepack. </li> 1057 <li>Kristiansen estimated urinary bladder volume based on surface points obtained from compound ultrasound scanning. 1058 <li>Kumar released <a href=http://www.compgeom.com/~piyush/reviver/>Reviver</a> [<a href=http://compgeom.com/~piyush/papers/revive.pdf>paper</a>] for 1059 provable surface reconstruction from sample points.</li> 1060 <li>Kuss converted MS Flightsimulator planes to 1061 <a href=http://home.t-online.de/home/Wolfram.Kuss>Flight Gear Flight Simulator</a> format. 1062 <li>Levy simulated the collision of galaxies 1063 <li>Littlewood, Drakopoulos, and Subbarayan minimized ink during 1064 CIELAB to CMYK color conversion for printer color management [<i>ACM Transactions on Graphics</i>, 21.2:132-175, 4/02] 1065 <li>Lovejoy studied nonlinear forecasting with fractal 1066 dynamics. </li> 1067 <li>Majhi, Janardan, Smid, and Gupta improved the surface 1068 finish of parts in layered manufacturing 1069 [<i>ACM Workshop on Applied Computational Geometry</i>, June 1996]. </li> 1070 <li>Masubuchi simulated a spatial database system to evaluate 1071 spatial tessellations for indexing. </li> 1072 <li>Michel, Giavitto, and Cohen added Delaunay graphs and 1073 Voronoi neighborhoods to their language, 1074 <a href=http://mgs.lami.univ-evry.fr>mgs</a>. 1075 <li>Mirtich developed <a 1076 href="https://www.merl.com/publications/TR97-05">V-clip</a> 1077 (Voronoi-clip) for collision detection of polyhedral 1078 objects. </li> 1079 <li>Montesinos wrote NormNewPoly, abbreviation for Normals to Newton Polyhedra. 1080 <li>Mouat solved Radial Basis Function surface fitting problems in 2 and 3 dimensions. 1081 <li>Nagle detected <a href="http://www.animats.com">collisions</a> 1082 between a falling robot and its environment. </li> 1083 <li>Netanyahu et al. let robots learn how to navigate. </li> 1084 <li>Orlando simulated silicon detectors for a proposed calorimeter. 1085 <li>Pearlmutter triangulated brain 1086magnetoencephalogrphic data for publication. 1087 <li>Perez-Minana analyzed the training sets for a multi-layer 1088 perceptron model. </li> 1089 <li>Porter built micromagnetic models with irregular grain 1090 structures. </li> 1091 <li>Powers studied the creep rupture behavior of ceramic 1092 materials. </li> 1093 <li><a href="http://www.cs.huji.ac.il/~arir/cda-abs.html">Rappoport 1094 and Spitz</a> interactively construct solid geometry 1095 models for conceptual design [SIGGRAPH'97].</li> 1096 <li>Rasanen built geographical information systems. </li> 1097 <li>Roosen et al developed <a 1098 href="http://www.ctcms.nist.gov/wulffman/">Wulffman</a> 1099 for interactively examining the Wulff shapes of crystals 1100 with specified symmetries. </li> 1101 <li>Rosenthal mapped global snow cover from satellite data 1102 using unsupervised spectral unmixing. </li> 1103 <li><a href="http://rses.anu.edu.au/geodynamics/nn/nn.html">Sambridge 1104 et al. </a>modeled subduction zones of tectonic plates 1105 and studied fluid flow and crystal deformation [<i>Nature</i>, 376:655-660, 1995]. </li> 1106 <li>Seynaeve computed serving areas for a GSM cellular 1107 operator. </li> 1108 <li>Schkolne investigated interactive 3-d shape modeling. </li> 1109 <li>Schmidt determined point neighborhoods for cluster 1110 analysis.</li> 1111 <li>
1111Schreier et al. found invariant sets for delta-sigma 1112 modulators. </li> 1113 <li>Schwarzkopf wrote <a 1114 href="http://ipe.otfried.org/">Ipe</a>, 1115 an extendible drawing editor. It includes an extension 1116 for drawing Voronoi diagrams, Delaunay triangulations, 1117 order-2 and order-3 Voronoi diagrams, furthest point 1118 Voronoi diagrams, and the medial axis of a convex 1119 polygon. </li> 1120 <li>Silva found efficient facets in a DEA 1121 (data envelopment analysis) context. 1122 <li>Singh analyzed protein 3D structure. </li>quick 1123 <li>Sullivan studied the neighbors of the origin in the R^8 1124 lattice. </li> 1125 <li>Thibout produced virtual reality systems.</li> 1126 <li>Thompson produced supports for mechanical parts from a 1127 gas deposition rapid prototyping system. </li> 1128 <li>Urner built <a href=http://www.4dsolutions.net/ocn/wgraphics.html>Waterman 1129 polyhedra</a>. 1130 <li>van den Bergen developed <a 1131 href="http://solid.sourceforge.net/">SOLID</a> 1132 for collision detection of 3-d objects 1133 undergoing rigid motion and deformation. </li> 1134 <li>Velez performed discrete simulations of incompressible 1135 viscous fluids using vortex methods. </li> 1136 <li><a href=http://www.acolyte-color.com/>Viggiano and Hoagland</a> 1137 determined the color gamuts for 1138 six-color lithographic printing 1139 <li><a href="http://web.archive.org/web/20041020040805/http://www.endocardial.com/physician/procedure.html">Voth</a> 1140 determined the shape of the left ventricle for electrical 1141 analysis of hearts. </li> 1142 <li>Walker showed the movement of an object while recording 1143 stresses. </li> 1144 <li>Weeks studied the <a href="http://web.archive.org/web/20100407153239/http://www.seas.harvard.edu/projects/weitzlab/research/glasses.html">physics of colloidal glasses</a> (archived) 1145 with a <a href=http://www.physics.emory.edu/faculty/weeks/confocal/>confocal microscope</a> [<a href=https://science.sciencemag.org/content/287/5453/627>Weeks, et. al., Science, 2000</a>] 1146 <li>Wloka wrote a <a href=http://www.google.com/url?sa=U&start=1&q=http://developer.nvidia.com/attach/1284&e=7629>cloth simulation</a> 1147 demo for NVidia with a <a href=http://www.paulsprojects.net/opengl/cloth/cloth.html>demo</a>. 1148 <li>Wright and independently, Hayashi, created 6-d 1149 "wrench spaces" to measure the stability of 1150 robot grasps. </li> 1151 <li>Xavier simulated rigid-body dynamics with intermittent 1152 and continuous contact. </li> 1153 <li>Zheng et al. computed 3-d, unstructured meshes for 1154 computational fluid dynamics. </li> 1155 <li>Zaboj wrote a convex hull plugin for 1156 <a href=http://k3studio.sourceforge.net>k3studio</a> 1157 <li>Zwick computed the smallest enclosing annuli by 1158 intersecting the Voronoi diagram with the furthest-site 1159 Voronoi diagram. </li> 1160</ul> 1161</blockquote> 1162 1163<p><!-- Navigation links --> </p> 1164 1165<hr/> 1166 1167<p><b>Up:</b> <a href="http://www.qhull.org">http://www.qhull.org</a><br/> 1168<strong>To:</strong>: <a href="#bugs">Bug and Notes</a> and 1169<a href="#users">Qhull Users</a> <br/> 1170<strong>Dn</strong>: <a href="../html/qh-faq.htm">FAQ about Qhull</a></p> 1171<!-- GC common information --> 1172<hr/> 1173 1174<p><a href="http://www.geom.uiuc.edu/"><img src="../html/qh--geom.gif" alt="[HOME]" 1175align="middle"></a> <i>The Geometry Center Home Page</i> </p> 1176 1177<p>Comments to: <a href="mailto:[email protected]">[email protected]</a> <br/> 1178Created: Sept. 25, 1995 --- <!-- hhmts start --> Last modified: see top <!-- hhmts end --> </p> 1179</body> 1180</html>
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.