qhull

README

qhull-go

A pure-Go 2-D Delaunay triangulator that aims to reproduce the exact connectivity produced by Qhull 8.0.2 with matplotlib's options (qhull d Qt Qbb Qc Qz).

Most Go Delaunay libraries return a valid triangulation. For points in general position that is enough — the triangulation is unique. But on cocircular inputs (≥4 points on a common empty circle) the triangulation is non-unique, and the specific diagonal Qhull picks is fixed by its internal construction order, not by geometry. This package reproduces that choice, which is what makes it suitable as a drop-in for matplotlib-parity work (it was extracted from matplotlib-go).

No cgo. No external dependencies — standard library only.

API

import qhull "github.com/cwbudde/qhull-go"

// Default: matplotlib/Qhull-matched connectivity, with the cocircular diagonal
// resolved from the computed vertex creation order. This is what you want for
// parity. Falls back to the exact baseline if the order computation ever bails.
tris, neighbors, err := qhull.Delaunay(x, y)

// Robust exact-predicate baseline. Identical to Delaunay for general position;
// on cocircular cells it returns a valid but arbitrary diagonal (no Qhull
// matching) and is cheaper on cocircular-heavy inputs.
tris, neighbors, err := qhull.DelaunayFast(x, y)

Both return triangles [][3]int (anticlockwise vertex indices) and neighbors [][3]int, where neighbors[i][j] is the triangle across the edge from vertex j to (j+1)%3, or -1 on the convex-hull boundary.

Status

• General position: 27/27 corpus cases match Qhull's connectivity exactly.
• Cocircular: 34/34 corpus cases match Qhull's exact build order / diagonal (61/61 across the combined order lock).

Ground-truth oracle

Parity is validated against Qhull's actual output, captured as fixtures in testdata/ (creation_order.json, corpus.json). The fixtures are committed, so building and testing this package needs nothing beyond the Go toolchain.

Regenerating the fixtures requires the Qhull 8.0.2 source plus the small instrumentation tools (oracle/introspect.c, oracle/dump_state.c, oracle/stepdump.c) and our trace patch (oracle/instrumentation.patch). The Qhull source itself is not redistributed here — it is a local, gitignored dev dependency under third_party/qhull-8.0.2/. The pinned tarball, one-time setup, and build/regeneration recipe are in oracle/README.md.

License

All code published here is MIT-licensed (see LICENSE). Qhull is used only as a local dev/test oracle and is not redistributed in this repository; see THIRD_PARTY.md.

Documentation

Overview

Package qhull computes 2-D Delaunay triangulations whose connectivity matches matplotlib's Qhull backend (Qhull 8.0.2, options "d Qt Qbb Qc Qz").

Why this exists

Most Delaunay libraries return *a* valid triangulation. For points in general position that is enough: the Delaunay triangulation is unique, so every correct construction agrees. But on cocircular inputs — four or more points on a common empty circle — the triangulation is non-unique, and the particular diagonal Qhull picks is fixed by its internal construction order, not by geometry. This package reproduces that choice, which makes it a drop-in for matplotlib-parity work (it was extracted from matplotlib-go).

API

Two entry points, both taking parallel x and y slices and returning the triangles and per-triangle neighbours:

• Delaunay is the default, parity-matching path. It reproduces Qhull's cocircular diagonal by resolving it from the computed vertex creation order, and falls back to the exact baseline if that computation cannot complete. Use it whenever you want matplotlib/Qhull connectivity.
• DelaunayFast is the robust exact-predicate baseline. It returns a valid Delaunay triangulation but makes an arbitrary cocircular diagonal choice. It is identical to Delaunay in general position and cheaper on cocircular-heavy inputs.

Both return triangles and neighbors as [][3]int. triangles[i] holds the three input-point indices of triangle i in anticlockwise winding; neighbors[i][j] is the triangle across the edge from vertex j to vertex (j+1)%3, or -1 on the convex-hull boundary. Inputs must have equal-length x and y and at least three points.

The implementation is pure Go: no external dependencies and no cgo.

Index

• func Delaunay(x, y []float64) (triangles, neighbors [][3]int, err error)
• func DelaunayFast(x, y []float64) (triangles, neighbors [][3]int, err error)

Examples

• Delaunay

Functions

func Delaunay

func Delaunay(x, y []float64) (triangles, neighbors [][3]int, err error)

Delaunay returns the Delaunay triangulation of the points (x, y) with matplotlib/Qhull's cocircular diagonal choice resolved from the computed vertex creation order (buildHullOrderRidge + the per-cell fan). This is the default, parity-matching entry point. It is layered on the robust exact-predicate baseline (DelaunayFast) and degrades gracefully:

• General-position inputs have no cocircular cells, so the exact triangulation is already canonical and is returned directly (the order computation, which would be wasted, is skipped — this is also the fast path for large inputs).
• When cocircular cells exist, the build order is computed and each cell is fanned from its last-created vertex, reproducing Qhull's diagonal.
• If the order computation bails (an unported hull degeneracy), the exact triangulation — itself a valid Delaunay triangulation — is returned.

Triangles (anticlockwise vertex indices) are returned in deterministic order; neighbors[i][j] is the triangle across the edge from vertex j to (j+1)%3, or -1 on the convex-hull boundary. For a faster construction that does not match Qhull's cocircular diagonal, use DelaunayFast.

Example

ExampleDelaunay triangulates the four corners of a unit square. The corners are cocircular, so the diagonal is not determined by geometry — Delaunay reproduces the specific diagonal that matplotlib's Qhull backend chooses.

package main

import (
	"fmt"
	"log"

	qhull "github.com/cwbudde/qhull-go"
)

func main() {
	// 3---2
	// |   |
	// 0---1
	x := []float64{0, 1, 1, 0}
	y := []float64{0, 0, 1, 1}

	triangles, neighbors, err := qhull.Delaunay(x, y)
	if err != nil {
		log.Fatal(err)
	}

	fmt.Println("triangles:", triangles)
	fmt.Println("neighbors:", neighbors)
}

Output:
triangles: [[3 0 1] [3 1 2]]
neighbors: [[-1 -1 1] [0 -1 -1]]

func DelaunayFast

func DelaunayFast(x, y []float64) (triangles, neighbors [][3]int, err error)

DelaunayFast returns the Delaunay triangulation of the points (x, y) as a list of triangles (anticlockwise vertex indices) and, for each triangle, its three neighbours. neighbors[i][j] is the triangle adjacent across the edge from vertex j to vertex (j+1)%3, or -1 on the convex hull boundary.

This is the robust exact-predicate baseline construction. It does NOT reproduce Qhull's cocircular diagonal choice: on inputs with ≥4 points on a common empty circle it returns a valid — but arbitrary — diagonal, skipping the creation-order computation that Delaunay performs. For general-position inputs (no cocircular cells) it is identical to Delaunay; on cocircular-heavy inputs it is cheaper. Use it when you need a Delaunay triangulation but do not care about matplotlib/Qhull connectivity parity.