~ubuntu-branches/ubuntu/natty/qhull/natty : revision 1

1

<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">

2

<html>

3

4

<head>

5

6

content="text/html; charset=iso-8859-1">

7

8

<title>Qhull manual</title>

9

<!-- Navigation links

10

NOTE -- verify all links by 'grep href=' 'grep name=' add # 'sort /+7'

11

index.htm

12

-->

13

</head>

14

15

<body>

16

17

<a name="TOP">Up:</a> <a

18

href="http://www.geom.umn.edu/locate/qhull">Home page</a> for Qhull

19

Up:<a

20

href="http://www.geom.umn.edu/~bradb/qhull-news.html">News</a> about Qhull

21

Up: <a href="qh-faq.htm">FAQ</a> about Qhull

22

To: <a href="#TOC">Qhull manual: Table of Contents</a>

23

(please wait while loading)

24

To: <a href="qh-quick.htm#programs">Programs</a>

25

<a href="qh-quick.htm#options">Options</a>

26

<a href="qh-opto.htm#output">Output</a>

27

<a href="qh-optf.htm#format">Formats</a>

28

<a href="qh-optg.htm#geomview">Geomview</a>

29

<a href="qh-optp.htm#print">Print</a>

30

<a href="qh-optq.htm#qhull">Qhull</a>

31

<a href="qh-optc.htm#prec">Precision</a>

32

<a href="qh-optt.htm#trace">Trace</a>

33

34

<hr>

35

36

<h1><a

37

href="http://www.geom.umn.edu/graphics/pix/Special_Topics/Computational_Geometry/fixed.html"><img

38

src="qh--rand.gif" alt="[random-fixed]" align="middle"

39

width="100" height="100"></a> Qhull manual </h1>

40

41

Qhull is a general dimension code for computing convex hulls,

42

Delaunay triangulations, halfspace intersections about a point, Voronoi

43

diagrams, furthest-site Delaunay triangulations, and

44

furthest-site Voronoi diagrams. These structures have

45

applications in science, engineering, statistics, and

46

mathematics. See <a

47

href="http://www.ifor.math.ethz.ch/ifor/staff/fukuda/polyfaq/polyfaq.html">Fukuda's

48

introduction</a> to convex hulls, Delaunay triangulations,

49

Voronoi diagrams, and linear programming. For a detailed

50

introduction, see O'Rourke [<a href="#orou94">'94</a>], Computational

51

Geometry in C.

52

53

There are six programs. Except for rbox, they use

54

the same code.

55

56

<ul>

57

<li><a href="qconvex.htm">qconvex</a> -- convex hulls

58

<li><a href="qdelaun.htm">qdelaunay</a> -- Delaunay triangulations and

59

furthest-site Delaunay triangulations

60

<li><a href="qhalf.htm">qhalf</a> -- halfspace intersections about a point

61

<li><a href="qhull.htm">qhull</a> -- all structures with additional options

62

<li><a href="qvoronoi.htm">qvoronoi</a> -- Voronoi diagrams and

63

furthest-site Voronoi diagrams

64

<li><a href="rbox.htm">rbox</a> -- generate point distributions for qhull

65

</ul>

66

</blockquote>

67

68

Qhull implements the Quickhull algorithm for computing the

69

convex hull. Qhull includes options

70

for hull volume, facet area, multiple output formats, and

71

graphical output. It can approximate a convex hull.

72

73

Qhull handles roundoff errors from floating point

74

arithmetic. It generates a convex hull with "thick" facets.

75

A facet's outer plane is clearly above all of the points;

76

its inner plane is clearly below the facet's vertices. Any

77

exact convex hull must lie between the inner and outer plane.

78

79

Qhull uses merged facets, triangulated output, or joggled

80

input. Triangulated output triangulates non-simplicial, merged

81

facets. Joggled input also

82

guarantees simplicial output, but it

83

is less accurate than merged facets. For merged facets, Qhull

84

reports the maximum outer and inner plane.

85

86

Brad Barber, Cambridge MA, October 4, 2001

87

88

89

90

<hr>

91

92

<h2><a href="#TOP">�</a><a name="TOC">Qhull manual: Table of

93

Contents </a></h2>

94

95

<ul>

96

<li><a href="#when">When</a> to use Qhull

97

<ul>

98

<li><a href="../README.txt">README.txt</a> - installation

99

instructions

100

<li><a href="../COPYING.txt">COPYING.txt</a> - copyright notice

101

<li><a href="../REGISTER.txt">REGISTER.txt</a> - registration

102

<li><a href="qh-faq.htm">FAQ</a> - Frequently Asked Questions about Qhull

103

<li><a href="qh-quick.htm#programs">Programs</a> - Program quick reference

104

<li><a href="qh-quick.htm#options">Options</a> - Option quick reference

105

<li><a href="../src/Changes.txt">Changes.txt</a> - change history

106

<li><a href="qhull.txt">qhull.txt</a> - Unix manual page

107

</ul>

108

<li><a href="#description">Description</a> of Qhull

109

<ul>

110

<li><a href="#definition">de</a>finition <a

111

href="#input">in</a>put <a href="#output">ou</a>tput

112

<a href="#algorithm">al</a>gorithm <a

113

href="#structure">da</a>ta structure </li>

114

<li><a href="qh-impre.htm">Imprecision</a> in Qhull</li>

115

<LI><a href="qh-impre.htm#joggle">Joggled input or merged

116

facets</a>

117

<li><a href="#geomview">Geomview</a>, Qhull's graphical

118

viewer</li>

119

<li><a href="qh-eg.htm">Examples</a> of Qhull using Geomview</li>

120

</ul>

121

<li><a href=qh-quick.htm#programs>Qhull programs</a>

122

<ul>

123

<li><a href="qconvex.htm">qconvex</a> -- convex hulls

124

<li><a href="qdelaun.htm">qdelaunay</a> -- Delaunay triangulations and

125

furthest-site Delaunay triangulations

126

<li><a href="qhalf.htm">qhalf</a> -- halfspace intersections about a point

127

<li><a href="qhull.htm">qhull</a> -- all structures with additional options

128

<li><a href="qvoronoi.htm">qvoronoi</a> -- Voronoi diagrams and

129

furthest-site Voronoi diagrams

130

<li><a href="rbox.htm">rbox</a> -- generate point distributions for qhull

131

</ul>

132

<li>Related URLs

133

<ul>

134

<li><a href="http://www.geom.umn.edu/~bradb/qhull-news.html">News page</a> for Qhull

135

with new features and reported bugs.

136

<li><a href="http://www.geom.umn.edu/~bradb/qhull-news.html#use">How</a> is Qhull used?

137

138

<li><a href="http://www.geom.umn.edu/software/qhull/html/qh-faq.htm">Current FAQ</a> for Qhull

139

<li><a href="http://www.geom.umn.edu/locate/qhull">Home page</a> for Qhull with additional URLs

140

<li><a href="news:comp.graphics.algorithms">Newsgroup</a>:

141

comp.graphics.algorithms

142

<li><a

143

href="http://exaflop.org/docs/cgafaq/">FAQ</a> for computer graphics algorithms and

144

<a href="http://exaflop.org/docs/cgafaq/cga6.html">geometric</a> structures.

145

<li>Amenta's <a href="http://www.geom.umn.edu/locate/cglist">Directory

146

of Computational Geometry Software </a></li>

147

<li>Bronnimann's <a

148

href="http://www.inria.fr/prisme/personnel/bronnimann/cgt/WWW.html">Computational

149

Geometry Tribune, WWW sites</a> </li>

150

<li>Erickson's <a

151

href="http://compgeom.cs.uiuc.edu/~jeffe/compgeom/code.html">Computational

152

Geometry Software</a> </li>

153

<li>Fukuda's <a

154

href="http://www.ifor.math.ethz.ch/ifor/staff/fukuda/polyfaq/polyfaq.html">

155

introduction</a> to convex hulls, Delaunay triangulations,

156

Voronoi diagrams, and linear programming.

157

<li>Stony Brook's <a

158

href="http://www.cs.sunysb.edu/~algorith/major_section/1.6.shtml">Algorithm Repository</a> on computational geometry.

159

</li>

160

</ul>

161

<li><a href="qh-quick.htm#options">Qhull options</a><ul>

162

<li><a href="qh-opto.htm#output">Output</a> formats</li>

163

<li><a href="qh-optf.htm#format">Additional</a> I/O

164

formats</li>

165

<li><a href="qh-optg.htm#geomview">Geomview</a>

166

output options</li>

167

<li><a href="qh-optp.htm#print">Print</a> options</li>

168

<li><a href="qh-optq.htm#qhull">Qhull</a> control

169

options</li>

170

<li><a href="qh-optc.htm#prec">Precision</a> options</li>

171

<li><a href="qh-optt.htm#trace">Trace</a> options</li>

172

</ul>

173

</li>

174

<li><a href="qh-in.htm">Qhull internals</a><ul>

175

<li><a href="qh-in.htm#performance">Performance</a>

176

of Qhull</li>

177

<li><a href="qh-in.htm#library">Calling</a> Qhull

178

from your program</li>

179

<li><a href="qh-in.htm#enhance">Enhancements</a> to

180

Qhull</li>

181

<li><a href="../src/index.htm">Qhull functions, macros, and

182

data structures</a> </li>

183

</ul>

184

</li>

185

<li><a href="#bugs">What to do</a> if something goes wrong</li>

186

<li><a href="#email">Email</a></li>

187

<li><a href="#authors">Authors</a></li>

188

<li><a href="#ref">References</a></li>

189

<li><a href="#acknowledge">Acknowledgments</a></li>

190

</ul>

191

<h2><a href="#TOC">�</a><a name="when">When to use Qhull</a></h2>

192

193

194

Qhull constructs convex hulls, Delaunay triangulations,

195

halfspace intersections about a point, Voronoi diagrams, furthest-site Delaunay

196

triangulations, and furthest-site Voronoi diagrams.

197

198

For convex hulls and halfspace intersections, Qhull may be used

199

for 2-d upto 8-d. For Voronoi diagrams and Delaunay triangulations, Qhull may be

200

used for 2-d upto 7-d. In higher dimensions, the size of the output

201

grows rapidly and Qhull does not work well with virtual memory.

202

If n is the size of

203

the input and d is the dimension (d>=3), the size of the output

204

and execution time

205

grows by n^(floor(d/2)

206

[see <a href=qh-in.htm#performance>Performance</a>]. For example, do

207

not try to build a 16-d convex hull of 1000 points. It will

208

have on the order of 1,000,000,000,000,000,000,000,000 facets.

209

210

211

Qhull does not support constrained Delaunay

212

triangulations, triangulation of non-convex surfaces, mesh

213

generation of non-convex objects, or medium-sized inputs in 9-D

214

and higher.

215

216

This is a big package with many options. It is one of the

217

fastest available. It is the only 3-d code that handles precision

218

problems due to floating point arithmetic. For example, it

219

implements the identity function for extreme points (see <a

220

href="qh-impre.htm">Imprecision in Qhull</a>).

221

222

If you need a short code for convex hull, Delaunay

223

triangulation, or Voronoi volumes consider Clarkson's <a

224

href="http://netlib.bell-labs.com/netlib/voronoi/hull.html">hull

225

program</a>. If you need 2-d Delaunay triangulations consider

226

Shewchuk's <a href="http://www.cs.cmu.edu/~quake/triangle.html">triangle

227

program</a>. It is much faster than Qhull and it allows

228

constraints. Both programs use exact arithmetic. They are in <a

229

href="ftp://netlib.bell-labs.com/netlib/voronoi">ftp://netlib.bell-labs.com/netlib/voronoi</a>.

230

Qhull <a

231

href="http://www.geom.umn.edu/software/download/qhull.html">version

232

1.0</a> may also meet your needs. It detects precision problems,

233

but does not handle them.

234

235

<a href=http://www.mpi-sb.mpg.de/LEDA/leda.html>Leda</a> is a

236

library for writing computational

237

geometry programs and other combinatorial algorithms. It

238

includes routines for computing 3-d convex

239

hulls, 2-d Delaunay triangulations, and 3-d Delaunay triangulations.

240

It provides rational arithmetic and graphical output. It runs on most

241

platforms.

242

243

If your problem is in high dimensions with a few,

244

non-simplicial facets, try Fukuda's <a

245

href="http://www.ifor.math.ethz.ch/ifor/staff/fukuda/cdd_home/cdd.html">cdd</a>.

246

It is much faster than Qhull for these distributions.

247

248

Custom software for 2-d and 3-d convex hulls may be faster

249

than Qhull. Custom software should use less memory. Qhull uses

250

general-dimension data structures and code. The data structures

251

support non-simplicial facets.

252

253

Qhull is not suitable for mesh generation or triangulation of

254

arbitrary surfaces. You may use Qhull if the surface is convex or

255

completely visible from an interior point (e.g., a star-shaped

256

polyhedron). First, project each site to a sphere that is

257

centered at the interior point. Then, compute the convex hull of

258

the projected sites. The facets of the convex hull correspond to

259

a triangulation of the surface. For mesh generation of arbitrary

260

surfaces, see <a

261

href="http://www-users.informatik.rwth-aachen.de/~roberts/meshgeneration.html">Schneiders'

262

Finite Element Mesh Generation</a>.

263

264

Qhull is not suitable for constrained Delaunay triangulations.

265

With a lot of work, you can write a program that uses Qhull to

266

add constraints by adding additional points to the triangulation.

267

268

Qhull is not suitable for the subdivision of arbitrary

269

objects. Use <tt>qdelaunay</tt> to subdivide a convex object.

270

271

</blockquote>

272

<h2><a href="#TOC">�</a><a name="description">Description of

273

Qhull </a></h2>

274

275

276

<h3><a href="#TOC">�</a><a name="definition">definition</a></h3>

277

278

279

The convex hull of a point set P is the smallest

280

convex set that contains P. If P is finite, the

281

convex hull defines a matrix A and a vector b such

282

that for all x in P, Ax+b <= [0,...].

283

284

Qhull computes the convex hull in 2-d, 3-d, 4-d, and higher

285

dimensions. Qhull represents a convex hull as a list of facets.

286

Each facet has a set of vertices, a set of neighboring facets,

287

and a halfspace. A halfspace is defined by a unit normal and an

288

offset (i.e., a row of A and an element of b).

289

290

Qhull accounts for round-off error. It returns

291

"thick" facets defined by two parallel hyperplanes. The

292

outer planes contain all input points. The inner planes exclude

293

all output vertices. See <a href="qh-impre.htm#imprecise">Imprecise

294

convex hulls</a>.

295

296

Qhull may be used for the Delaunay triangulation or the

297

Voronoi diagram of a set of points. It may be used for the

298

intersection of halfspaces.

299

300

</blockquote>

301

<h3><a href="#TOC">�</a><a name="input">input format</a></h3>

302

303

304

The input data on <tt>stdin</tt> consists of:

305

306

<ul>

307

<li>first line contains the dimension</li>

308

<li>second line contains the number of input points</li>

309

<li>remaining lines contain point coordinates</li>

310

</ul>

311

312

For example:

313

314

<pre>

315

3 #sample 3-d input

316

5

317

0.4 -0.5 1.0

318

1000 -1e-5 -100

319

0.3 0.2 0.1

320

1.0 1.0 1.0

321

0 0 0

322

</pre>

323

324

Input may be entered by hand. End the input with a control-D

325

(^D) character.

326

327

To input data from a file, use I/O redirection or '<a

328

href="qh-optt.htm#TI">TI file</a>'. The filename may not

329

include spaces or quotes.

330

331

A comment starts with a non-numeric character and continues to

332

the end of line. The first comment is reported in summaries and

333

statistics. With multiple <tt>qhull</tt> commands, use option '<a

334

href="qh-optf.htm#FQ">FQ</a>' to place a comment in the output.

335

336

The dimension and number of points can be reversed. Comments

337

and line breaks are ignored. Error reporting is better if there

338

is one point per line.

339

340

</blockquote>

341

<h3><a href="#TOC">�</a><a name="option">option format</a></h3>

342

343

344

Use options to specify the output formats and control

345

Qhull. The <tt>qhull</tt> program takes all options. The

346

other programs use a subset of the options. They disallow

347

experimental and inappropriate options.

348

349

350

<ul>

351

<li>

352

qconvex == qhull

353

<li>

354

qdelaunay == qhull d Qbb

355

<li>

356

qhalf == qhull H

357

<li>

358

qvoronoi == qhull v Qbb

359

</ul>

360

</blockquote>

361

362

Single letters are used for output formats and precision

363

constants. The other options are grouped into menus for formats

364

('<a href="qh-optf.htm#format">F</a>'), Geomview ('<a

365

href="qh-optg.htm#geomview">G </a>'), printing ('<a

366

href="qh-optp.htm#print">P</a>'), Qhull control ('<a

367

href="qh-optq.htm#qhull">Q </a>'), and tracing ('<a

368

href="qh-optt.htm#trace">T</a>'). The menu options may be listed

369

together (e.g., 'GrD3' for 'Gr' and 'GD3'). Options may be in any

370

order. Capitalized options take a numeric argument (except for '<a

371

href="qh-optp.htm#PG">PG</a>' and '<a href="qh-optf.htm#format">F</a>'

372

options). Use option '<a href="qh-optf.htm#FO">FO</a>' to print

373

the selected options.

374

375

Qhull uses zero-relative indexing. If there are n

376

points, the index of the first point is 0 and the index of

377

the last point is n-1.

378

379

The default options are:

380

381

<ul>

382

<li>summary output ('<a href="qh-opto.htm#s">s</a>') </li>

383

<li>merged facets ('<a href="qh-optc.htm#C0">C-0</a>' in 2-d,

384

3-d, 4-d; '<a href="qh-optq.htm#Qx">Qx</a>' in 5-d and

385

up)</li>

386

</ul>

387

388

Except for bounding box

389

('<a href="qh-optq.htm#Qbk">Qbk:n</a>', etc.), drop facets

390

('<a href="qh-optp.htm#Pdk">Pdk:n</a>', etc.), and

391

Qhull command ('<a href="qh-opto.htm#FQ">FQ</a>'), only the last

392

occurence of an option counts.

393

Bounding box and drop facets may be repeated for each dimension.

394

Option 'FQ' may be repeated any number of times.

395

396

The Unix <tt>tcsh</tt> and <tt>ksh </tt>shells make it easy to

397

try out different options. In Windows 95, use a DOS window with <tt>doskey</tt>

398

and a window scroller (e.g., <tt>peruse</tt>).

399

400

</blockquote>

401

<h3><a href="#TOC">�</a><a name="output">output format</a></h3>

402

403

404

To write the results to a file, use I/O redirection or '<a

405

href="qh-optt.htm#TO">TO file</a>'. Windows 95 users should use

406

'TO file' or the console. If a filename is surrounded by single quotes,

407

it may include spaces.

408

409

410

The default output option is a short summary ('<a

411

href="qh-opto.htm#s">s</a>') to <tt>stdout</tt>. There are many

412

others (see <a href="qh-opto.htm">output</a> and <a

413

href="qh-optf.htm">formats</a>). You can list vertex incidences,

414

vertices and facets, vertex coordinates, or facet normals. You

415

can view Qhull objects with Geomview or Mathematica. You can

416

print the internal data structures. You can call Qhull from your

417

application (see <a href="qh-in.htm#library">Qhull library</a>).

418

419

For example, 'qhull <a href="qh-opto.htm#o">o</a>' lists the

420

vertices and facets of the convex hull.

421

422

Error messages and additional summaries ('<a

423

href="qh-opto.htm#s">s</a>') go to <tt>stderr</tt>. Unless

424

redirected, <tt>stderr</tt> is the console.

425

426

</blockquote>

427

<h3><a href="#TOC">�</a><a name="algorithm">algorithm</a></h3>

428

429

430

Qhull implements the Quickhull algorithm for convex hull

431

[Barber et al. <a href="#bar-dob96">'96</a>]. This algorithm

432

combines the 2-d Quickhull algorithm with the n-d

433

beneath-beyond algorithm [c.f., Preparata & Shamos <a

434

href="#pre-sha85">'85</a>]. It is similar to the randomized

435

algorithms of Clarkson and others [Clarkson & Shor <a

436

href="#cla-sho89">'89</a>; Clarkson et al. <a href="#cla-meh93">'93</a>;

437

Mulmuley <a href="#mulm94">'94</a>]. For a demonstration, see <a

438

href="qh-eg.htm#how">How Qhull adds a point</a>. The main

439

advantages of Quickhull are output sensitive performance (in

440

terms of the number of extreme points), reduced space

441

requirements, and floating-point error handling.

442

443

</blockquote>

444

<h3><a href="#TOC">�</a><a name="structure">data structures</a></h3>

445

446

447

Qhull produces the following data structures for dimension d:

448

449

450

<ul>

451

<li>A coordinate is a real number in floating point

452

format. </li>

453

<li>A point is an array of d coordinates.

454

With option '<a href="qh-optq.htm#QJn">QJ</a>', the

455

coordinates are joggled by a small amount. </li>

456

<li>A vertex is an input point. </li>

457

<li>A hyperplane is d normal coefficients and

458

an offset. The length of the normal is one. The

459

hyperplane defines a halfspace. If V is a normal, b

460

is an offset, and x is a point inside the convex

461

hull, then Vx+b <0.</li>

462

<li>An outer plane is a positive

463

offset from a hyperplane. When Qhull is done, all points

464

will be below all outer planes.</li>

465

<li>An inner plane is a negative

466

offset from a hyperplane. When Qhull is done, all

467

vertices will be above the corresponding inner planes.</li>

468

<li>An orientation is either 'top' or 'bottom'. It is the

469

topological equivalent of a hyperplane's geometric

470

orientation. </li>

471

<li>A simplicial facet is a set of

472

d neighboring facets, a set of d vertices, a

473

hyperplane equation, an inner plane, an outer plane, and

474

an orientation. For example in 3-d, a simplicial facet is

475

a triangle. </li>

476

<li>A centrum is a point on a facet's hyperplane. A

477

centrum is the average of a facet's vertices. Neighboring

478

facets are convex if each centrum is below the

479

neighbor facet's hyperplane. </li>

480

<li>A ridge is a set of d-1 vertices, two

481

neighboring facets, and an orientation. For example in

482

3-d, a ridge is a line segment. </li>

483

<li>A non-simplicial facet is a set of ridges, a

484

hyperplane equation, a centrum, an outer plane, and an

485

inner plane. The ridges determine a set of neighboring

486

facets, a set of vertices, and an orientation. Qhull

487

produces a non-simplicial facet when it merges two facets

488

together. For example, a cube has six non-simplicial

489

facets. </li>

490

</ul>

491

492

For examples, use option '<a href="qh-opto.htm#f">f</a>'. See <a

493

href="../src/qh-poly.htm">polyhedron operations</a> for further

494

design documentation.

495

496

</blockquote>

497

<h3><a href="#TOC">�</a>Imprecision in Qhull</h3>

498

499

500

See <a href="qh-impre.htm">Imprecision in Qhull</a>.

501

502

</blockquote>

503

<h3><a href="#TOC">�</a><a name="geomview">Geomview, Qhull's

504

graphical viewer</a></h3>

505

506

507

<a href="http://www.geomview.org">Geomview</a>

508

is an interactive geometry viewing program for Linux, SGI workstations,

509

Sun workstations, AIX workstations, NeXT workstations, and X-windows.

510

It is an

511

<a href=http://sourceforge.net/projects/geomview>open source project</a>

512

under SourceForge.

513

Besides a 3-d viewer, it includes a 4-d viewer, an n-d viewer and

514

many features for viewing mathematical objects. You may need to

515

ftp <tt>ndview</tt> from the <tt>newpieces</tt> directory.

516

517

</blockquote>

518

<h3><a href="#TOC">�</a>Description of Qhull examples</h3>

519

520

521

See <a href="qh-eg.htm">Examples</a>. Some of the examples

522

have <a

523

href="http://www.geom.umn.edu/graphics/pix/Special_Topics/Computational_Geometry/welcome.html">pictures

524

</a>.

525

526

</blockquote>

527

</blockquote>

528

<h2><a href="#TOC">�</a>Options for using Qhull </h2>

529

530

531

See <a href="qh-quick.htm#options">Options</a>.

532

533

</blockquote>

534

<h2><a href="#TOC">�</a>Qhull internals </h2>

535

536

537

See <a href="qh-in.htm">Internals</a>.

538

539

</blockquote>

540

<h2><a href="#TOC">�</a><a name="bugs">What to do if something

541

goes wrong</a></h2>

542

543

544

Please report bugs to <a

545

href="http://www.geom.umn.edu/software/qhull/qhull-bug-mail.html">qhull_bug@geom.umn.edu

546

</a>. Please report if Qhull crashes. Please report if Qhull

547

generates an "internal error". Please report if Qhull

548

produces a poor approximate hull in 2-d, 3-d or 4-d. Please

549

report documentation errors. Please report missing or incorrect

550

links.

551

552

If you do not understand something, try a small example. The <a

553

href="rbox.htm">rbox</a> program is an easy way to generate

554

test cases. The <a href="#geomview">Geomview</a> program helps to

555

visualize the output from Qhull.

556

557

If Qhull does not compile, it is due to an incompatibility

558

between your system and ours. The first thing to check is that

559

your compiler is ANSI standard. Qhull produces a compiler error

560

if __STDC__ is not defined. You may need to set a flag (e.g.,

561

'-A' or '-ansi').

562

563

If Qhull compiles but crashes on the test case (rbox D4),

564

there's still incompatibility between your system and ours.

565

Sometimes it is due to memory management. This can be turned off

566

with qh_NOmem in mem.h. Please let us know if you figure out how

567

to fix these problems.

568

569

If you doubt the output from Qhull, add option '<a

570

href="qh-optt.htm#Tv">Tv</a>'. It checks that every point is

571

inside the outer planes of the convex hull. It checks that every

572

facet is convex with its neighbors. It checks the topology of the

573

convex hull.

574

575

Qhull should work on all inputs. It may report precision

576

errors if you turn off merged facets with option '<a

577

href="qh-optq.htm#Q0">Q0</a>'. This can get as bad as facets with

578

flipped orientation or two facets with the same vertices. You'll

579

get a long help message if you run into such a case. They are

580

easy to generate with <tt>rbox</tt>.

581

582

If you do find a problem, try to simplify it before reporting

583

the error. Try different size inputs to locate the smallest one

584

that causes an error. You're welcome to hunt through the code

585

using the execution trace ('<a href="qh-optt.htm#Tn">T4</a>') as

586

a guide. This is especially true if you're incorporating Qhull

587

into your own program.

588

589

When you report an error, please attach a data set to the end

590

of your message. Include the options that you used with Qhull,

591

the results of option '<a href="qh-optf.htm#FO">FO</a>', and any

592

messages generated by Qhull. This allows me to see the error for

593

myself. Qhull is maintained part-time.

594

595

</blockquote>

596

<h2><a href="#TOC">�</a><a name="email">Email</a></h2>

597

598

599

Please send correspondence to Brad Barber at <a

600

href="http://www.geom.umn.edu/software/qhull/qhull-mail.html">qhull@geom.umn.edu

601

</a>and report bugs to <a

602

href="http://www.geom.umn.edu/software/qhull/qhull-bug-mail.html">qhull_bug@geom.umn.edu

603

</a>. Let me know how you use Qhull. If you mention it in a

604

paper, please send a reference and abstract.

605

606

If you would like to get Qhull announcements (e.g., a new

607

version) and news (any bugs that get fixed, etc.), let us know

608

and we will add you to our mailing list. If you would like to

609

communicate with other Qhull users, I will add you to the

610

qhull_users alias. For Internet news about geometric algorithms

611

and convex hulls, look at comp.graphics.algorithms and

612

sci.math.num-analysis. For Qhull news look at <a

613

href="http://www.geom.umn.edu/~bradb/qhull-news.html">qhull-news.html</a>.

614

615

</blockquote>

616

<h2><a href="#TOC">�</a><a name="authors">Authors</a></h2>

617

618

619

<pre> C. Bradford Barber Hannu Huhdanpaa

620

bradb@geom.umn.edu hannu@geom.umn.edu

621

622

c/o The Geometry Center

623

University of Minnesota

624

400 Lind Hall

625

207 Church Street S.E.

626

Minneapolis, MN 55455

627

</pre>

628

629

</blockquote>

630

<h2><a href="#TOC">�</a><a name="acknowledge">Acknowledgments</a></h2>

631

632

633

A special thanks to David Dobkin for his guidance. A special

634

thanks to Albert Marden, Victor Milenkovic, the Geometry Center,

635

and Harvard University for supporting this work.

636

637

A special thanks to <a href="http://www.endocardial.com/">Endocardial

638

Solutions, Inc.</a> of St. Paul, Minnesota for their support of the

639

internal documentation (<a href=../src/index.htm>src/index.htm</a>). They use Qhull to build 3-d models of

640

heart chambers.

641

642

The software was developed under National Science Foundation

643

grants NSF/DMS-8920161 and NSF-CCR-91-15793 750-7504. If you find

644

it useful, please let us know.

645

646

The Geometry Center is supported by grant DMS-8920161 from the

647

National Science Foundation, by grant DOE/DE-FG02-92ER25137 from

648

the Department of Energy, by the University of Minnesota, and by

649

Minnesota Technology, Inc.

650

651

</blockquote>

652

<h2><a href="#TOC">�</a><a name="ref">References</a></h2>

653

654

655

<a name="aure91">Aurenhammer</a>, F., "Voronoi diagrams

656

-- A survey of a fundamental geometric data structure," ACM

657

Computing Surveys, 1991, 23:345-405.

658

659

<a name="bar-dob96">Barber</a>, C. B., D.P. Dobkin, and H.T.

660

Huhdanpaa, "The Quickhull Algorithm for Convex Hulls," ACM

661

Transactions on Mathematical Software, Vol. 22, No. 4 (Dec.

662

1996), p. 469-483 [<a

663

href="http://www.acm.org/pubs/citations/journals/toms/1996-22-4/p469-barber/">http://www.acm.org</a>;

664

<a href="ftp://geom.umn.edu/pub/software/qhull-96.ps">ftp://geom.umn.edu</a>].

665

666

667

<a name="cla-sho89">Clarkson</a>, K.L. and P.W. Shor,

668

"Applications of random sampling in computational geometry,

669

II", Discrete Computational Geometry, 4:387-421, 1989

670

671

<a name="cla-meh93">Clarkson</a>, K.L., K. Mehlhorn, and R.

672

Seidel, "Four results on randomized incremental

673

construction," Computational Geometry: Theory and

674

Applications, vol. 3, p. 185-211, 1993.

675

676

<a name="dob-kir90">Dobkin</a>, D.P. and D.G. Kirkpatrick,

677

"Determining the separation of preprocessed polyhedra--a

678

unified approach," in Proc. 17th Inter. Colloq. Automata

679

Lang. Program., in Lecture Notes in Computer Science,

680

Springer-Verlag, 443:400-413, 1990.

681

682

<a name="fort93">Fortune, S.</a>, "Computational

683

geometry," in R. Martin, editor, Directions in Geometric

684

Computation, Information Geometers, 47 Stockers Avenue,

685

Winchester, SO22 5LB, UK, ISBN 1-874728-02-X, 1993.

686

687

<a name="mile93">Milenkovic, V.</a>, "Robust polygon

688

modeling," Computer-Aided Design, vol. 25, p. 546-566,

689

September 1993.

690

691

<a name="muck96">Mucke</a>, E.P., I. Saias, B. Zhu, Fast

692

randomized point location without preprocessing in Two- and

693

Three-dimensional Delaunay Triangulations, ACM Symposium on

694

Computational Geometry, p. 274-283, 1996 [<a

695

href="http://www.geom.umn.edu/software/cglist/GeomDir/">GeomDir</a>].

696

697

698

<a name="mulm94">Mulmuley</a>, K., Computational Geometry,

699

An Introduction Through Randomized Algorithms, Prentice-Hall,

700

NJ, 1994.

701

702

<a name="orou94">O'Rourke</a>, J., Computational Geometry

703

in C, Cambridge University Press, 1994.

704

705

<a name="pre-sha85">Preparata</a>, F. and M. Shamos, Computational

706

Geometry, Springer-Verlag, New York, 1985.

707

708

Qhull is available by anonymous ftp from geom.umn.edu. To

709

retrieve a copy visit <a

710

href="http://www.geom.umn.edu/software/download/qhull.html">Download

711

Qhull</a> or, in Unix, ftp geom.umn.edu, user: anonymous, cd

712

pub/software, get qhull.tar.Z, quit, uncompress qhull.tar.Z, tar

713

xf qhull.tar, cd qhull, make

714

715

</blockquote>

716

717

<hr>

718

719

Up: <a

720

href="http://www.geom.umn.edu/locate/qhull">Home page</a> for Qhull

721

Up:<a

722

href="http://www.geom.umn.edu/~bradb/qhull-news.html">News</a> about Qhull

723

Up: <a href="qh-faq.htm">FAQ</a> about Qhull

724

To: <a href="#TOC">Qhull manual</a>: Table of Contents

725

To: <a href="qh-quick.htm#programs">Programs</a>

726

<a href="qh-quick.htm#options">Options</a>

727

<a href="qh-opto.htm#output">Output</a>

728

<a href="qh-optf.htm#format">Formats</a>

729

<a href="qh-optg.htm#geomview">Geomview</a>

730

<a href="qh-optp.htm#print">Print</a>

731

<a href="qh-optq.htm#qhull">Qhull</a>

732

<a href="qh-optc.htm#prec">Precision</a>

733

<a href="qh-optt.htm#trace">Trace</a>

734

Dn: <a href="qh-impre.htm">Imprecision in Qhull</a>

735

Dn: <a href="qh-eg.htm">Description of Qhull examples</a>

736

Dn: <a href="qh-in.htm">Qhull internals</a>

737

Dn: <a href="../src/index.htm">Qhull functions, macros, and data

738

structures</a>

739

740

<hr>

741

742

<a href="http://www.geom.umn.edu/"><img src="qh--geom.gif"

743

align="middle" width="40" height="40"></a>The Geometry Center

744

Home Page

745

746

Comments to: <a

747

href="http://www.geom.umn.edu/software/qhull/qhull-mail.html">qhull@geom.umn.edu

748

</a>

749

Created: Sept. 25, 1995 ---  Last modified: see top

750

</body>

751

</html>