1 |
/* RCSid $Id$ */ |
2 |
/* C header file for Hilbert curve functions */ |
3 |
#if !defined(_hilbert_h_) |
4 |
#define _hilbert_h_ |
5 |
|
6 |
#ifdef __cplusplus |
7 |
extern "C" { |
8 |
#endif |
9 |
|
10 |
/* define the bitmask_t type as an integer of sufficient size */ |
11 |
typedef unsigned long long bitmask_t; |
12 |
/* define the halfmask_t type as an integer of 1/2 the size of bitmask_t */ |
13 |
typedef unsigned long halfmask_t; |
14 |
|
15 |
/***************************************************************** |
16 |
* hilbert_i2c |
17 |
* |
18 |
* Convert an index into a Hilbert curve to a set of coordinates. |
19 |
* Inputs: |
20 |
* nDims: Number of coordinate axes. |
21 |
* nBits: Number of bits per axis. |
22 |
* index: The index, contains nDims*nBits bits (so nDims*nBits must be <= 8*sizeof(bitmask_t)). |
23 |
* Outputs: |
24 |
* coord: The list of nDims coordinates, each with nBits bits. |
25 |
* Assumptions: |
26 |
* nDims*nBits <= (sizeof index) * (bits_per_byte) |
27 |
*/ |
28 |
|
29 |
void hilbert_i2c(unsigned nDims, unsigned nBits, bitmask_t index, bitmask_t coord[]); |
30 |
|
31 |
/***************************************************************** |
32 |
* hilbert_c2i |
33 |
* |
34 |
* Convert coordinates of a point on a Hilbert curve to its index. |
35 |
* Inputs: |
36 |
* nDims: Number of coordinates. |
37 |
* nBits: Number of bits/coordinate. |
38 |
* coord: Array of n nBits-bit coordinates. |
39 |
* Outputs: |
40 |
* index: Output index value. nDims*nBits bits. |
41 |
* Assumptions: |
42 |
* nDims*nBits <= (sizeof bitmask_t) * (bits_per_byte) |
43 |
*/ |
44 |
|
45 |
bitmask_t hilbert_c2i(unsigned nDims, unsigned nBits, bitmask_t const coord[]); |
46 |
|
47 |
/***************************************************************** |
48 |
* hilbert_cmp, hilbert_ieee_cmp |
49 |
* |
50 |
* Determine which of two points lies further along the Hilbert curve |
51 |
* Inputs: |
52 |
* nDims: Number of coordinates. |
53 |
* nBytes: Number of bytes of storage/coordinate (hilbert_cmp only) |
54 |
* nBits: Number of bits/coordinate. (hilbert_cmp only) |
55 |
* coord1: Array of nDims nBytes-byte coordinates (or doubles for ieee_cmp). |
56 |
* coord2: Array of nDims nBytes-byte coordinates (or doubles for ieee_cmp). |
57 |
* Return value: |
58 |
* -1, 0, or 1 according to whether |
59 |
coord1<coord2, coord1==coord2, coord1>coord2 |
60 |
* Assumptions: |
61 |
* nBits <= (sizeof bitmask_t) * (bits_per_byte) |
62 |
*/ |
63 |
|
64 |
int hilbert_cmp(unsigned nDims, unsigned nBytes, unsigned nBits, void const* coord1, void const* coord2); |
65 |
int hilbert_ieee_cmp(unsigned nDims, double const* coord1, double const* coord2); |
66 |
|
67 |
/***************************************************************** |
68 |
* hilbert_box_vtx |
69 |
* |
70 |
* Determine the first or last vertex of a box to lie on a Hilbert curve |
71 |
* Inputs: |
72 |
* nDims: Number of coordinates. |
73 |
* nBytes: Number of bytes/coordinate. |
74 |
* nBits: Number of bits/coordinate. (hilbert_box_vtx only) |
75 |
* findMin: Is it the least vertex sought? |
76 |
* coord1: Array of nDims nBytes-byte coordinates - one corner of box |
77 |
* coord2: Array of nDims nBytes-byte coordinates - opposite corner |
78 |
* Output: |
79 |
* c1 and c2 modified to refer to selected corner |
80 |
* value returned is log2 of size of largest power-of-two-aligned box that |
81 |
* contains the selected corner and no other corners |
82 |
* Assumptions: |
83 |
* nBits <= (sizeof bitmask_t) * (bits_per_byte) |
84 |
*/ |
85 |
unsigned |
86 |
hilbert_box_vtx(unsigned nDims, unsigned nBytes, unsigned nBits, |
87 |
int findMin, void* c1, void* c2); |
88 |
unsigned |
89 |
hilbert_ieee_box_vtx(unsigned nDims, |
90 |
int findMin, double* c1, double* c2); |
91 |
|
92 |
/***************************************************************** |
93 |
* hilbert_box_pt |
94 |
* |
95 |
* Determine the first or last point of a box to lie on a Hilbert curve |
96 |
* Inputs: |
97 |
* nDims: Number of coordinates. |
98 |
* nBytes: Number of bytes/coordinate. |
99 |
* nBits: Number of bits/coordinate. |
100 |
* findMin: Is it the least vertex sought? |
101 |
* coord1: Array of nDims nBytes-byte coordinates - one corner of box |
102 |
* coord2: Array of nDims nBytes-byte coordinates - opposite corner |
103 |
* Output: |
104 |
* c1 and c2 modified to refer to least point |
105 |
* Assumptions: |
106 |
* nBits <= (sizeof bitmask_t) * (bits_per_byte) |
107 |
*/ |
108 |
unsigned |
109 |
hilbert_box_pt(unsigned nDims, unsigned nBytes, unsigned nBits, |
110 |
int findMin, void* coord1, void* coord2); |
111 |
unsigned |
112 |
hilbert_ieee_box_pt(unsigned nDims, |
113 |
int findMin, double* c1, double* c2); |
114 |
|
115 |
/***************************************************************** |
116 |
* hilbert_nextinbox |
117 |
* |
118 |
* Determine the first point of a box after a given point to lie on a Hilbert curve |
119 |
* Inputs: |
120 |
* nDims: Number of coordinates. |
121 |
* nBytes: Number of bytes/coordinate. |
122 |
* nBits: Number of bits/coordinate. |
123 |
* findPrev: Is the previous point sought? |
124 |
* coord1: Array of nDims nBytes-byte coordinates - one corner of box |
125 |
* coord2: Array of nDims nBytes-byte coordinates - opposite corner |
126 |
* point: Array of nDims nBytes-byte coordinates - lower bound on point returned |
127 |
* |
128 |
* Output: |
129 |
if returns 1: |
130 |
* c1 and c2 modified to refer to least point after "point" in box |
131 |
else returns 0: |
132 |
arguments unchanged; "point" is beyond the last point of the box |
133 |
* Assumptions: |
134 |
* nBits <= (sizeof bitmask_t) * (bits_per_byte) |
135 |
*/ |
136 |
int |
137 |
hilbert_nextinbox(unsigned nDims, unsigned nBytes, unsigned nBits, |
138 |
int findPrev, void* coord1, void* coord2, |
139 |
void const* point); |
140 |
|
141 |
/***************************************************************** |
142 |
* hilbert_incr |
143 |
* |
144 |
* Advance from one point to its successor on a Hilbert curve |
145 |
* Inputs: |
146 |
* nDims: Number of coordinates. |
147 |
* nBits: Number of bits/coordinate. |
148 |
* coord: Array of nDims nBits-bit coordinates. |
149 |
* Output: |
150 |
* coord: Next point on Hilbert curve |
151 |
* Assumptions: |
152 |
* nBits <= (sizeof bitmask_t) * (bits_per_byte) |
153 |
*/ |
154 |
|
155 |
void |
156 |
hilbert_incr(unsigned nDims, unsigned nBits, bitmask_t coord[]); |
157 |
|
158 |
#ifdef __cplusplus |
159 |
} |
160 |
#endif |
161 |
|
162 |
#endif /* _hilbert_h_ */ |