106 3D: Deterministic convex hulls

9.3

Racket

106 3D: Deterministic convex hulls🔗ℹ

struct
(struct convex-hull3d-coplanar-group3d ( face-id
triangle-indices
boundary-vertex-indices
source-point-indices)
    #:transparent)
  face-id : any/c
  triangle-indices : vector?
  boundary-vertex-indices : (or/c #f vector?)
  source-point-indices : vector?

One merged coplanar supporting face of a three-dimensional hull. The source-point vector includes every retained input point on that plane, including a point in the face interior.

struct
(struct convex-hull3d-result ( dimension
mesh
source-point-indices
coplanar-groups
interior-indices
diagnostics)
    #:transparent)
  dimension : (integer-in 0 3)
  mesh : mesh3d?
  source-point-indices : vector?
  coplanar-groups : vector?
  interior-indices : vector?
  diagnostics : hash?

A truthful hull result. source-point-indices maps returned mesh vertices to original input indexes. interior-indices includes non-extreme and merged-duplicate inputs. For dimension 0, 1, and 2, mesh is, respectively, a point mesh, segment mesh, or planar triangle fan—never a fabricated three-dimensional solid.

procedure
(convex-hull3d points
[ #:id id
#:tolerance tolerance
#:merge-tolerance merge-tolerance
#:orientation-tolerance orientation-tolerance
#:coplanar-tolerance coplanar-tolerance
#:coplanar coplanar
#:on-degenerate on-degenerate])
→ convex-hull3d-result?
  points : (or/c vector? list?)
  id : symbol? = 'hull
  tolerance : (or/c 'automatic nonnegative-real?) = 'automatic
  merge-tolerance : (or/c #f nonnegative-real?) = #f
  orientation-tolerance : (or/c #f nonnegative-real?) = #f
  coplanar-tolerance : (or/c #f nonnegative-real?) = #f
  coplanar : (or/c 'merge 'triangulate) = 'merge
  on-degenerate : (or/c 'report 'error) = 'report

Builds a deterministic convex hull. It retains original source indexes. #:merge-tolerance, #:orientation-tolerance, and #:coplanar-tolerance control point clustering, degeneracy/orientation classification, and supporting-face grouping independently. A numeric legacy #:tolerance supplies all three unless an explicit policy keyword overrides that stage. The automatic merge policy accepts only exact duplicates; automatic orientation uses a scale-aware threshold for inexact classification. Exact coordinates use exact determinant signs.

The next outside point is chosen by greatest positive face distance, then stable coordinate/source order. 'merge returns polygonal supporting-face records; 'triangulate leaves that vector empty. If a point set is lower-dimensional, 'report returns its actual dimension and 'error raises instead. Diagnostics state the effective tolerances, the exact/inexact orientation policy, duplicate count, and near-zero decision count.

Limitations. The convex-hull implementation is deterministic but is not a general computational-geometry repair system: it does not resolve self-intersecting input, and inexact near-degenerate cases use the recorded scale-aware policy instead of a bigfloat/exact-predicate fallback. Near-duplicate clustering with an explicit tolerance is deterministic and transitive: a chain of close points forms one cluster even when its endpoints are not directly close. Concave hulls, Delaunay triangulation, and arbitrary polygon-with-hole operations are not supported.

I	Concepts
II	Cookbook
III	Guide
IV	Complete Example Programs
V	Reference

52	Find a task or a name
53	Modules to require
54	Scenes and sampling
55	Scene states
56	Animation requests
57	Native model details
58	Visuals
59	Geometry
60	Number Lines and Coordinate Decorations
61	Point Markers, Scatter Plots, and Filled Areas
62	Probability and Statistical Diagrams
63	Calculus lessons
64	Colors
65	Slides
66	Slide command-line tools
67	Source Programs and Authored Timelines
68	Interactive Preview and Inspection
69	Preview controls and diagnostics
70	Projects and Final Rendering
71	Project execution and cache details
72	Pict Renderer Protocol
73	3D reference map
74	3D: Objects, groups, and paths
75	3D: Cameras and projection
76	3D: Views inside a Scene
77	3D: Animating 3D objects
78	3D: Animating the 3D camera
79	3D: Cuts, caps, and section measurements
80	3D: Supplementary surface, section, and annotation bindings
81	3D: Cuts, sections, and numerical volume
82	3D: Vectors
83	3D: Linear maps and rotations
84	3D: Affine transforms
85	3D: Bounds, rays, and planes
86	3D: Spatial maps and homotopies
87	3D: Materials and lights
88	3D: Lighting inspection
89	3D: Shadow descriptors and stable bounds
90	3D: Finite-light animation
91	3D: Software finite-light evaluation
92	3D: Colour space and final output
93	3D: Relations and geometric annotations
94	3D: Projected labels
95	3D: Textured billboards
96	3D: Spatial curves and vector diagrams
97	3D: Spatial anchors and label layout
98	3D: Anchors and projected labels
99	3D: Parametric surfaces and calculus
100	3D: Adaptive, trimmed, and implicit surfaces
101	3D: Constructive solids
102	3D: Surface constructors and queries
103	3D: Meshes
104	3D: Triangle topology
105	3D: Polygonal faces
106	3D: Deterministic convex hulls
107	3D: Polyhedral duals
108	3D: Schlegel diagrams and polyhedral nets
109	3D: Conservative mesh correspondence
110	3D: Topology-safe mesh matching
111	3D: Checking and repairing mesh orientation
112	3D: Clipping, sections, and transparency
113	3D: Prepared spatial ODE trajectories and vector fields
114	3D: Seeds and streamline sets
115	3D: Poincare sections and return maps
116	3D: Equilibria and local linearization
117	3D: Flow maps and volume change
118	3D: Drawing and inspecting trajectories
119	3D: Reading prepared trajectories
120	3D: Drawing vector fields and particles
121	3D: Trajectory display
122	3D: Spatial inspection and exact picking
123	3D: Retained renderer backends
124	3D: Compiled geometry and instances
125	3D: Frame requests and results
126	3D: Software rendering and statistics
127	3D: Optional Racket/ Open GL backend
128	Experimental Derived Visuals
129	Source Package Hygiene