0
# Hulls
1

2
The hulls module provides convex hull operations for geometries, enabling the creation of outer bounds, smooth transitions between shapes, and protective casings. It supports both 2D and 3D geometries with efficient algorithms for point-based and geometry-based hulls.
3

4
## Capabilities
5

6
### Convex Hull Operations
7

8
Create convex hulls from multiple geometries to find their outer boundary.
9

10
```javascript { .api }
11
/**
12
 * Create convex hull of given geometries
13
 * @param {...Object} geometries - Variable number of geometry objects (geom2, geom3, or path2)
14
 * @returns {Object} New geometry representing the convex hull
15
 */
16
function hull(...geometries: RecursiveArray<Geom2>): Geom2;
17
function hull(...geometries: RecursiveArray<Geom3>): Geom3;
18
function hull(...geometries: RecursiveArray<Path2>): Path2;
19

20
/**
21
 * Create chain of hulled geometries with smooth transitions
22
 * @param {...Object} geometries - Variable number of geometry objects (minimum 2)
23
 * @returns {Object} Union of all consecutive hull pairs
24
 */
25
function hullChain(...geometries: RecursiveArray<Geom2>): Geom2;
26
function hullChain(...geometries: RecursiveArray<Geom3>): Geom3;
27
function hullChain(...geometries: RecursiveArray<Path2>): Path2;
28
```
29

30
**Usage Examples:**
31

32
```javascript
33
const { hull, hullChain } = require('@jscad/modeling').hulls;
34
const { rectangle, circle, triangle } = require('@jscad/modeling').primitives;
35

36
// Basic convex hull of multiple shapes
37
const envelope = hull(
38
  rectangle({ center: [-5, -5], size: [4, 4] }),
39
  circle({ center: [5, 5], radius: 3 }),
40
  triangle()
41
);
42

43
// Smooth transition between shapes
44
const smoothTransition = hullChain(
45
  rectangle({ center: [-10, 0] }),
46
  circle({ center: [0, 0] }),
47
  rectangle({ center: [10, 0] })
48
);
49

50
// Multiple geometry hull for protective casing
51
const casing = hull(component1, component2, component3);
52
```
53

54
### Point-Based Hull Operations
55

56
Create convex hulls directly from arrays of points using efficient algorithms.
57

58
```javascript { .api }
59
/**
60
 * Create 2D convex hull from array of points using Graham scan algorithm
61
 * @param {Array} uniquePoints - Array of unique 2D points [[x,y], [x,y], ...]
62
 * @returns {Array} Array of points forming convex hull boundary (counter-clockwise)
63
 */
64
function hullPoints2(uniquePoints: Array<[number, number]>): Array<[number, number]>;
65

66
/**
67
 * Create 3D convex hull from array of points using QuickHull algorithm
68
 * @param {Array} uniquePoints - Array of unique 3D points [[x,y,z], [x,y,z], ...]
69
 * @returns {Array} Array of polygons (triangular faces) forming convex hull surface
70
 */
71
function hullPoints3(uniquePoints: Array<[number, number, number]>): Array<Poly3>;
72
```
73

74
**Usage Examples:**
75

76
```javascript
77
const { hullPoints2, hullPoints3 } = require('@jscad/modeling').hulls;
78

79
// 2D convex hull from scattered points
80
const points2D = [
81
  [0, 0], [3, 1], [1, 3], [5, 2], 
82
  [2, 4], [4, 0], [1, 1] // interior point
83
];
84
const hull2D = hullPoints2(points2D); // Returns boundary points only
85

86
// 3D convex hull from point cloud
87
const points3D = [
88
  [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 1],
89
  [1, 1, 0], [1, 0, 1], [0, 1, 1], [1, 1, 1],
90
  [0.5, 0.5, 0.5] // interior point
91
];
92
const hull3D = hullPoints3(points3D); // Returns triangular faces
93

94
// Create geometry from hull points
95
const { geom2, geom3 } = require('@jscad/modeling').geometries;
96
const hullGeometry2D = geom2.fromPoints(hull2D);
97
const hullGeometry3D = geom3.create(hull3D);
98
```
99

100
## Advanced Usage Patterns
101

102
### Protective Casings and Enclosures
103

104
```javascript
105
const { hull } = require('@jscad/modeling').hulls;
106
const { expand } = require('@jscad/modeling').expansions;
107

108
// Create protective casing around components
109
const components = [motor, battery, circuitBoard, connector];
110
const looseFit = hull(...components);
111
const tightFit = hull(...components.map(c => expand({ delta: 0.5 }, c)));
112

113
// Enclosure with mounting tabs
114
const enclosure = hull(
115
  mainBody,
116
  ...mountingTabs.map(tab => translate(tab.position, tab.geometry))
117
);
118
```
119

120
### Smooth Morphing and Transitions
121

122
```javascript
123
const { hullChain } = require('@jscad/modeling').hulls;
124
const { union } = require('@jscad/modeling').booleans;
125

126
// Morphing animation frames
127
const morphFrames = [];
128
const startShape = circle({ radius: 5 });
129
const endShape = rectangle({ size: [10, 8] });
130

131
// Create intermediate hull shapes for animation
132
for (let i = 0; i <= 10; i++) {
133
  const t = i / 10;
134
  const frame = hullChain(
135
    scale([1 - t + 0.1, 1 - t + 0.1], startShape),
136
    scale([t + 0.1, t + 0.1], endShape)
137
  );
138
  morphFrames.push(frame);
139
}
140

141
// Continuous transition structure
142
const bridge = hullChain(pillar1, arch, pillar2);
143
```
144

145
### Point Cloud Processing
146

147
```javascript
148
const { hullPoints3 } = require('@jscad/modeling').hulls;
149

150
// Process 3D scan data
151
function processPointCloud(scanPoints) {
152
  // Remove duplicate points
153
  const uniquePoints = [...new Set(scanPoints.map(p => p.join(',')))].map(s => s.split(',').map(Number));
154
  
155
  // Create convex hull
156
  const hullFaces = hullPoints3(uniquePoints);
157
  
158
  // Convert to solid geometry
159
  const { geom3 } = require('@jscad/modeling').geometries;
160
  return geom3.create(hullFaces);
161
}
162

163
// Simplify complex geometry to convex approximation
164
function simplifyToHull(complexGeometry) {
165
  const { measureBoundingBox } = require('@jscad/modeling').measurements;
166
  const bounds = measureBoundingBox(complexGeometry);
167
  
168
  // Extract boundary points and create hull
169
  const points = extractSurfacePoints(complexGeometry, 100); // Custom function
170
  return hullPoints3(points);
171
}
172
```
173

174
## Type Definitions
175

176
```javascript { .api }
177
// Recursive array type for nested geometry arrays
178
type RecursiveArray<T> = Array<T | RecursiveArray<T>>;
179

180
// 2D point type
181
type Vec2 = [number, number];
182

183
// 3D point type  
184
type Vec3 = [number, number, number];
185

186
// 3D polygon face
187
type Poly3 = {
188
  vertices: Array<Vec3>;
189
};
190

191
// Supported geometry types
192
type Geom2 = {
193
  sides: Array<Array<Vec2>>;
194
  color?: [number, number, number, number];
195
};
196

197
type Geom3 = {
198
  polygons: Array<Poly3>;
199
  color?: [number, number, number, number];
200
};
201

202
type Path2 = {
203
  points: Array<Vec2>;
204
  isClosed: boolean;
205
};
206
```
207

208
## Algorithm Details
209

210
### 2D Convex Hull (Graham Scan)
211
- **Time Complexity**: O(n log n) due to sorting
212
- **Algorithm**: Finds lowest point, sorts by polar angle, uses stack to eliminate concave points
213
- **Optimization**: Uses `fakeAtan2` function for better performance than `Math.atan2`
214
- **Output**: Points ordered counter-clockwise
215

216
### 3D Convex Hull (QuickHull)
217
- **Time Complexity**: O(n log n) average, O(n²) worst case
218
- **Algorithm**: Incremental construction using extreme points and visible face removal
219
- **Implementation**: Based on mauriciopoppe/quickhull3d library
220
- **Output**: Triangular faces forming complete hull surface
221

222
### Error Handling
223
- **Mixed Types**: Throws "only hulls of the same type are supported"
224
- **Empty Input**: Throws "wrong number of arguments" 
225
- **Insufficient Points**: Returns empty geometry for degenerate cases
226
- **Duplicate Points**: Automatically filtered using string-based Set deduplication