quickhull

README

quickhull-go

A 3D Quickhull implementation in Go.

Big thanks to @akuukka for their public domain C++ implementation which was used as a reference.

This is different from Google's S2 Geometry implementation because it works in ℝ³ instead of S².

Go Get

go get -u github.com/markus-wa/quickhull-go

Example

TODO

License

This project is licensed under the MIT license.

Documentation

Index

• func ConvexHull(pointCloud []r3.Vector) []r3.Vector
• type Face
• type HalfEdge
• type HalfEdgeMesh
  • func ConvexHullAsMesh(pointCloud []r3.Vector) HalfEdgeMesh

Functions

func ConvexHull

func ConvexHull(pointCloud []r3.Vector) []r3.Vector

ConvexHull calculates the convex hull of the given point cloud using the Quickhull algorithm. See: https://en.wikipedia.org/wiki/Quickhull

Types

type Face

type Face struct {
	HalfEdge int // Index of a bounding HalfEdge
}

Face of a half edge. See: https://www.openmesh.org/media/Documentations/OpenMesh-6.3-Documentation/a00010.html

type HalfEdge

type HalfEdge struct {
	EndVertex int // Index of end vertex
	Opp       int // Index of opposite HalfEdge
	Face      int // Index of Face it belongs to
	Next      int // Index of next HalfEdge
}

HalfEdge is a half edge. See: https://www.openmesh.org/media/Documentations/OpenMesh-6.3-Documentation/a00010.html

type HalfEdgeMesh

type HalfEdgeMesh struct {
	Vertices  []r3.Vector
	Faces     []Face
	HalfEdges []HalfEdge
}

HalfEdgeMesh is a mesh consisting of half edges. See: https://www.openmesh.org/media/Documentations/OpenMesh-6.3-Documentation/a00010.html

func ConvexHullAsMesh

func ConvexHullAsMesh(pointCloud []r3.Vector) HalfEdgeMesh

ConvexHullAsMesh calculates the convex hull and returns it as a half-edge-mesh. See also: ConvexHull()