Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Analysis.AlgorithmBehavior/qhull-2012.1/src/libqhull/qh-geom.htm @ 10207

Last change on this file since 10207 was 10207, checked in by ascheibe, 11 years ago

#1886 added a unit test for volume calculation and the qhull library
File size: 13.0 KB
Line 
1<!-- Do not edit with Front Page, it adds too many spaces -->
2<html>
3<head>
4<meta http-equiv="Content-Type"
5content="text/html; charset=iso-8859-1">
6<title>geom.c, geom2.c -- geometric and floating point routines</title>
7</head>
8
9<body>
10<!-- Navigation links -->
11<p><a name="TOP"><b>Up:</b></a> <a
12href="http://www.qhull.org">Home page</a> for Qhull<br>
13<b>Up:</b> <a href="../../html/index.htm#TOC">Qhull manual</a>: Table of Contents <br>
14<b>Up:</b> <a href="../../html/qh-quick.htm#programs">Programs</a>
15&#149; <a href="../../html/qh-quick.htm#options">Options</a>
16&#149; <a href="../../html/qh-opto.htm#output">Output</a>
17&#149; <a href="../../html/qh-optf.htm#format">Formats</a>
18&#149; <a href="../../html/qh-optg.htm#geomview">Geomview</a>
19&#149; <a href="../../html/qh-optp.htm#print">Print</a>
20&#149; <a href="../../html/qh-optq.htm#qhull">Qhull</a>
21&#149; <a href="../../html/qh-optc.htm#prec">Precision</a>
22&#149; <a href="../../html/qh-optt.htm#trace">Trace</a><br>
23<b>Up:</b> <a href="../../html/qh-code.htm#TOC">Qhull code: Table of Contents</a><br>
24<b>To:</b> <a href="index.htm">Qhull functions</a>, macros, and data structures<br>
25<b>To:</b> <a href="qh-geom.htm#TOC">Geom</a> &#149; <a href="qh-globa.htm">Global</a>
26&#149; <a href="qh-io.htm">Io</a> &#149; <a href="qh-mem.htm">Mem</a>
27&#149; <a href="qh-merge.htm">Merge</a> &#149; <a href="qh-poly.htm">Poly</a>
28&#149; <a href="qh-qhull.htm">Qhull</a> &#149; <a href="qh-set.htm">Set</a>
29&#149; <a href="qh-stat.htm">Stat</a> &#149; <a href="qh-user.htm">User</a>
30</p>
31
32<hr>
33<!-- Main text of document. -->
34
35<h2>geom.c, geom2.c, random.c -- geometric and floating point routines</h2>
36<blockquote>
37<p>Geometrically, a vertex is a point with <em>d</em> coordinates
38and a facet is a halfspace. A <em>halfspace</em> is defined by an
39oriented hyperplane through the facet's vertices. A <em>hyperplane</em>
40is defined by <em>d</em> normalized coefficients and an offset. A
41point is <em>above</em> a facet if its distance to the facet is
42positive.</p>
43
44<p>Qhull uses floating point coordinates for input points,
45vertices, halfspace equations, centrums, and an interior point.</p>
46
47<p>Qhull may be configured for single precision or double
48precision floating point arithmetic (see <a href="user.h#realT">realT</a>
49). </p>
50
51<p>Each floating point operation may incur round-off error (see
52<a href="qh-merge.htm#TOC">Merge</a>). The maximum error for distance
53computations is determined at initialization. The roundoff error
54in halfspace computation is accounted for by computing the
55distance from vertices to the halfspace. </p>
56</blockquote>
57<p><b>Copyright &copy; 1995-2012 C.B. Barber</b></p>
58<hr>
59<p><a href="#TOP">&#187;</a> <b>Geom</b>
60<a name="TOC">&#149;</a> <a href="qh-globa.htm#TOC">Global</a> &#149;
61<a href="qh-io.htm#TOC">Io</a> &#149; <a href="qh-mem.htm#TOC">Mem</a> &#149;
62<a href="qh-merge.htm#TOC">Merge</a> &#149; <a href="qh-poly.htm#TOC">Poly</a> &#149;
63<a href="qh-qhull.htm#TOC">Qhull</a> &#149; <a href="qh-set.htm#TOC">Set</a> &#149;
64<a href="qh-stat.htm#TOC">Stat</a> &#149; <a href="qh-user.htm#TOC">User</a> </p>
65
66<h3>Index to <a href="geom.c">geom.c</a>,
67<a href="geom2.c">geom2.c</a>, <a href="geom.h">geom.h</a>,
68<a href="random.c">random.c</a>, <a href="random.h">random.h</a>
69</h3>
70
71<ul>
72<li><a href="#gtype">geometric data types and constants</a> </li>
73<li><a href="#gmacro">mathematical macros</a>
74</li>
75<li><a href="#gmath">mathematical functions</a> </li>
76<li><a href="#gcomp">computational geometry functions</a> </li>
77<li><a href="#gpoint">point array functions</a> </li>
78<li><a href="#gfacet">geometric facet functions</a> </li>
79<li><a href="#ground">geometric roundoff functions</a></li>
80</ul>
81
82<h3><a href="qh-geom.htm#TOC">&#187;</a><a name="gtype">geometric data types
83and constants</a></h3>
84
85<ul>
86<li><a href="libqhull.h#coordT">coordT</a> coordinates and
87coefficients are stored as realT</li>
88<li><a href="libqhull.h#pointT">pointT</a> a point is an array
89of <tt>DIM3</tt> coordinates </li>
90</ul>
91
92<h3><a href="qh-geom.htm#TOC">&#187;</a><a name="gmacro">mathematical macros</a></h3>
93
94<ul>
95<li><a href="geom.h#fabs_">fabs_</a> returns the absolute
96value of a </li>
97<li><a href="geom.h#fmax_">fmax_</a> returns the maximum
98value of a and b </li>
99<li><a href="geom.h#fmin_">fmin_</a> returns the minimum
100value of a and b </li>
101<li><a href="geom.h#maximize_">maximize_</a> maximize a value
102</li>
103<li><a href="geom.h#minimize_">minimize_</a> minimize a value
104</li>
105<li><a href="geom.h#det2_">det2_</a> compute a 2-d
106determinate </li>
107<li><a href="geom.h#det3_">det3_</a> compute a 3-d
108determinate </li>
109<li><a href="geom.h#dX">dX, dY, dZ</a> compute the difference
110between two coordinates </li>
111</ul>
112
113<h3><a href="qh-geom.htm#TOC">&#187;</a><a name="gmath">mathematical functions</a></h3>
114
115<ul>
116<li><a href="geom.c#backnormal">qh_backnormal</a> solve for
117normal using back substitution </li>
118<li><a href="geom2.c#crossproduct">qh_crossproduct</a>
119compute the cross product of two 3-d vectors </li>
120<li><a href="geom2.c#determinant">qh_determinant</a> compute
121the determinant of a square matrix </li>
122<li><a href="geom.c#gausselim">qh_gausselim</a> Gaussian
123elimination with partial pivoting </li>
124<li><a href="geom2.c#gram_schmidt">qh_gram_schmidt</a>
125implements Gram-Schmidt orthogonalization by rows </li>
126<li><a href="geom2.c#maxabsval">qh_maxabsval</a> return max
127absolute value of a vector </li>
128<li><a href="geom2.c#minabsval">qh_minabsval</a> return min
129absolute value of a dim vector </li>
130<li><a href="geom2.c#mindiff">qh_mindiff</a> return index of
131min absolute difference of two vectors </li>
132<li><a href="geom.c#normalize">qh_normalize</a> normalize a
133vector </li>
134<li><a href="geom.c#normalize2">qh_normalize2</a> normalize a
135vector and report if too small </li>
136<li><a href="geom2.c#printmatrix">qh_printmatrix</a> print
137matrix given by row vectors </li>
138<li><a href="random.c#rand">qh_rand/srand</a> generate random
139numbers </li>
140<li><a href="random.c#randomfactor">qh_randomfactor</a> return
141a random factor near 1.0 </li>
142<li><a href="random.c#randommatrix">qh_randommatrix</a>
143generate a random dimXdim matrix in range (-1,1) </li>
144</ul>
145
146<h3><a href="qh-geom.htm#TOC">&#187;</a><a name="gcomp">computational geometry functions</a></h3>
147
148<ul>
149<li><a href="geom2.c#detsimplex">qh_detsimplex</a> compute
150determinate of a simplex of points </li>
151<li><a href="io.c#detvnorm">qh_detvnorm</a> determine normal for Voronoi ridge </li>
152<li><a href="geom2.c#distnorm">qh_distnorm</a> compute
153distance from point to hyperplane as defined by normal and offset</li>
154<li><a href="geom2.c#facetarea_simplex">qh_facetarea_simplex</a>
155return area of a simplex</li>
156<li><a href="geom.c#getangle">qh_getangle</a> return cosine
157of angle (i.e., dot product) </li>
158<li><a href="geom.c#getcenter">qh_getcenter</a> return
159arithmetic center for a set of vertices </li>
160<li><a href="geom2.c#pointdist">qh_pointdist</a> return
161distance between two points </li>
162<li><a href="geom2.c#rotatepoints">qh_rotatepoints</a> rotate
163numpoints points by a row matrix </li>
164<li><a href="geom2.c#sethalfspace">qh_sethalfspace</a> set
165coords to dual of halfspace relative to an interior point </li>
166<li><a href="geom.c#sethyperplane_det">qh_sethyperplane_det</a>
167return hyperplane for oriented simplex using determinates
168</li>
169<li><a href="geom.c#sethyperplane_gauss">qh_sethyperplane_gauss</a>
170return hyperplane for oriented simplex using Gaussian
171elimination </li>
172<li><a href="geom2.c#voronoi_center">qh_voronoi_center</a>
173return Voronoi center for a set of points </li>
174</ul>
175
176<h3><a href="qh-geom.htm#TOC">&#187;</a><a name="gpoint">point array functions</a></h3>
177<ul>
178<li><a href="geom2.c#copypoints">qh_copypoints</a> return
179malloc'd copy of points</li>
180<li><a href="geom2.c#joggleinput">qh_joggleinput</a> joggle
181input points by qh.JOGGLEmax </li>
182<li><a href="geom2.c#maxmin">qh_maxmin</a> return max/min
183points for each dimension</li>
184<li><a href="geom2.c#maxsimplex">qh_maxsimplex</a> determines
185maximum simplex for a set of points </li>
186<li><a href="geom2.c#printpoints">qh_printpoints</a> print ids for a
187set of points </li>
188<li><a href="geom2.c#projectinput">qh_projectinput</a> project
189input using qh DELAUNAY and qh low_bound/high_bound </li>
190<li><a href="geom2.c#projectpoints">qh_projectpoints</a>
191project points along one or more dimensions </li>
192<li><a href="geom2.c#rotateinput">qh_rotateinput</a> rotate
193input points using row matrix </li>
194<li><a href="geom2.c#scaleinput">qh_scaleinput</a> scale
195input points using qh low_bound/high_bound </li>
196<li><a href="geom2.c#scalelast">qh_scalelast</a> scale last
197coordinate to [0,m] for Delaunay triangulations </li>
198<li><a href="geom2.c#scalepoints">qh_scalepoints</a> scale
199points to new lowbound and highbound </li>
200<li><a href="geom2.c#setdelaunay">qh_setdelaunay</a> project
201points to paraboloid for Delaunay triangulation </li>
202<li><a href="geom2.c#sethalfspace_all">qh_sethalfspace_all</a>
203generate dual for halfspace intersection with interior
204point </li>
205</ul>
206
207<h3><a href="qh-geom.htm#TOC">&#187;</a><a name="gfacet">geometric facet functions</a></h3>
208<ul>
209<li><a href="geom.c#distplane">qh_distplane</a> return
210distance from point to facet </li>
211<li><a href="geom2.c#facetarea">qh_facetarea</a> return area
212of a facet </li>
213<li><a href="geom2.c#facetcenter">qh_facetcenter</a> return
214Voronoi center for a facet's vertices </li>
215<li><a href="geom.c#findbest">qh_findbest</a> find visible
216facet or best facet for a point </li>
217<li><a href="geom.c#findbesthorizon">qh_findbesthorizon</a>
218update best new facet with horizon facets</li>
219<li><a href="geom.c#findbestnew">qh_findbestnew</a> find best
220new facet for point </li>
221<li><a href="geom2.c#getarea">qh_getarea</a> get area of all
222facets in facetlist, collect statistics </li>
223<li><a href="geom.c#getcentrum">qh_getcentrum</a> return
224centrum for a facet </li>
225<li><a href="geom.c#getdistance">qh_getdistance</a> returns
226the max and min distance of a facet's vertices to a
227neighboring facet</li>
228<li><a href="geom2.c#findgooddist">qh_findgooddist</a> find
229best good facet visible for point from facet </li>
230<li><a href="geom2.c#inthresholds">qh_inthresholds</a> return
231True if facet normal within 'Pdn' and 'PDn'</li>
232<li><a href="geom2.c#orientoutside">qh_orientoutside</a>
233orient facet so that <tt>qh.interior_point</tt> is inside</li>
234<li><a href="geom.c#projectpoint">qh_projectpoint</a> project
235point onto a facet </li>
236<li><a href="geom.c#setfacetplane">qh_setfacetplane</a> sets
237the hyperplane for a facet </li>
238<li><a href="geom2.c#sharpnewfacets">qh_sharpnewfacets</a> true
239if new facets contains a sharp corner</li>
240</ul>
241
242<h3><a href="qh-geom.htm#TOC">&#187;</a><a name="ground">geometric roundoff functions</a></h3>
243<ul>
244<li><a href="geom2.c#detjoggle">qh_detjoggle</a> determine
245default joggle for points and distance roundoff error</li>
246<li><a href="geom2.c#detroundoff">qh_detroundoff</a>
247determine maximum roundoff error and other precision constants</li>
248<li><a href="geom2.c#distround">qh_distround</a> compute
249maximum roundoff error due to a distance computation to a
250normalized hyperplane</li>
251<li><a href="geom2.c#divzero">qh_divzero</a> divide by a
252number that is nearly zero </li>
253<li><a href="geom2.c#maxouter">qh_maxouter</a> return maximum outer
254plane</li>
255<li><a href="geom2.c#outerinner">qh_outerinner</a> return actual
256outer and inner planes
257</ul>
258
259<p><!-- Navigation links --> </p>
260<hr>
261<p><b>Up:</b>
262<a href="http://www.qhull.org">Home page for
263Qhull</a> <br>
264<b>Up:</b> <a href="index.htm#TOC">Qhull manual: Table of Contents</a> <br>
265<b>Up:</b> <a href="../../html/qh-quick.htm#programs">Programs</a>
266&#149; <a href="../../html/qh-quick.htm#options">Options</a>
267&#149; <a href="../../html/qh-opto.htm#output">Output</a>
268&#149; <a href="../../html/qh-optf.htm#format">Formats</a>
269&#149; <a href="../../html/qh-optg.htm#geomview">Geomview</a>
270&#149; <a href="../../html/qh-optp.htm#print">Print</a>
271&#149; <a href="../../html/qh-optq.htm#qhull">Qhull</a>
272&#149; <a href="../../html/qh-optc.htm#prec">Precision</a>
273&#149; <a href="../../html/qh-optt.htm#trace">Trace</a><br>
274<b>Up:</b> <a href="../../html/qh-code.htm#TOC">Qhull code: Table of Contents</a> <br>
275<b>To:</b> <a href="index.htm">Qhull functions</a>, macros, and data structures<br>
276<b>To:</b> <a href="qh-geom.htm">Geom</a> &#149;
277<a href="qh-globa.htm">Global</a> &#149; <a href="qh-io.htm">Io</a>
278&#149; <a href="qh-mem.htm">Mem</a> &#149; <a href="qh-merge.htm">Merge</a>
279&#149; <a href="qh-poly.htm">Poly</a> &#149; <a href="qh-qhull.htm#TOC">Qhull</a>
280&#149; <a href="qh-set.htm">Set</a> &#149; <a href="qh-stat.htm">Stat</a>
281&#149; <a href="qh-user.htm">User</a><br>
282
283
284<p><!-- GC common information --> </p>
285<hr>
286<p><a href="http://www.geom.uiuc.edu/"><img
287src="../../html/qh--geom.gif" align="middle" width="40" height="40"></a><i>The
288Geometry Center Home Page </i></p>
289<p>Comments to: <a href=mailto:qhull@qhull.org>qhull@qhull.org</a>
290</a><br>
291Created: May 2, 1997 --- <!-- hhmts start --> Last modified: see top <!-- hhmts end --> </p>
292</body>
293</html>
Note: See TracBrowser for help on using the repository browser.