Delaunay triangulation in SciPy

Introduction

Delaunay triangulation helps connect points to form triangles without overlapping edges. It is useful to understand shapes and spaces between points.

Mapping locations on a map to find nearest neighbors

Creating mesh grids for 3D surface modeling

Analyzing spatial relationships in sensor networks

Generating terrain models from scattered elevation points

Syntax

SciPy

from scipy.spatial import Delaunay
tri = Delaunay(points)
tri.simplices

points is a list or array of coordinates, like [[x1, y1], [x2, y2], ...]

tri.simplices gives the indices of points forming each triangle

Examples

Simple triangle from three points forming one triangle.

SciPy

import numpy as np
from scipy.spatial import Delaunay
points = np.array([[0, 0], [1, 0], [0, 1]])
tri = Delaunay(points)
print(tri.simplices)

Four points forming two triangles covering a square area.

SciPy

import numpy as np
from scipy.spatial import Delaunay
points = np.array([[0, 0], [1, 0], [0, 1], [1, 1]])
tri = Delaunay(points)
print(tri.simplices)

Sample Program

This code creates a Delaunay triangulation for five points forming a square with a center point. It prints the triangles as groups of point indices.

SciPy

import numpy as np
from scipy.spatial import Delaunay

# Define points in 2D space
points = np.array([
    [0, 0],
    [1, 0],
    [0, 1],
    [1, 1],
    [0.5, 0.5]
])

# Create Delaunay triangulation
tri = Delaunay(points)

# Print triangles by point indices
print(tri.simplices)

Important Notes

Delaunay triangulation maximizes the minimum angle of triangles, avoiding skinny triangles.

Works in 2D and higher dimensions but is most common in 2D.

Input points should not be all on a single line or identical points.

Summary

Delaunay triangulation connects points to form triangles without overlapping edges.

It helps analyze spatial relationships and create meshes.

Use scipy.spatial.Delaunay to compute it easily in Python.