Delaunay Triangulation is a fundamental concept in computational geometry, which is used to create a triangulation of a set of points in a 2D or 3D space. This process is important in various fields such as computer graphics, image processing, and numerical simulation. In this article, we will explore how to perform Delaunay Triangulation of points from a 2D surface in 3D using Python.
In this article, we will use the Python library scipy for performing Delaunay Triangulation. We will first generate a set of random points on a 2D surface and then use the scipy library to create a triangulation of these points. Finally, we will use the library matplotlib to visualize the triangulation in 3D.
Key Concepts
Delaunay Triangulation
Delaunay Triangulation is a method for creating a triangulation of a set of points in a 2D or 3D space. The key idea behind this method is that the triangles in the triangulation should not have any points inside the circumcircle of the triangle. This ensures that the triangles have a relatively uniform shape and size, which is important in many applications. Some examples of these applications are computer graphics, image processing, and numerical simulation.
In computational geometry, there are many different types of triangulations for a set of points, Delaunay triangulation is one of them, and is known for its “best” quality triangulation comparing to other triangulation methods.
Scipy
Scipy is a Python library for scientific and technical computing. It provides a wide range of functionality, including optimization, interpolation, integration, and signal and image processing. It also provides the ability to perform Delaunay triangulation of a set of points.
Matplotlib
Matplotlib is a plotting library for creating static, animated, and interactive visualizations in Python. It can be used to create a wide range of visualizations, including 2D and 3D plots, bar charts, scatter plots, and more. Matplotlib is a powerful library, it’s widely used and makes it easy to create beautiful visualizations. We use it here to plot the triangulation in 3D, using the plot_trisurf function, and to display it, using the show function.
Methods Used
- matplotlib.tri.Triangulation(): A class for creating a triangulation in matplotlib.
- matplotlib.pyplot.triplot(): A function for creating a 2D plot of a triangulation.
- matplotlib.pyplot.show(): A function for displaying the plots in a window.
- scipy.spatial.Delaunay(): A function that takes a set of points and returns the Delaunay triangulation of those points.
Procedure
1. Import the necessary libraries
The first step is to import the necessary libraries. We will need the NumPy, Matplotlib, and SciPy libraries for this task.
Python3
import numpy as np import matplotlib.pyplot as plt from scipy.spatial import Delaunay |
2. Obtain the 2D points dataset
Obtain the dataset of 2D points, here, we shall generate a random dataset, using numpy’s random method.
Python3
# Generate some random points points = np.random.rand(177, 2) |
3. Perform Delaunay triangulation
Now, we can use the Delaunay class from the SciPy library to perform the triangulation.
Python3
# Perform Delaunay triangulation tri = Delaunay(points) |
4. Visualize the triangulation
Finally, we can use Matplotlib’s triplot function to visualize the triangulation.
Python3
# Visualize the triangulation plt.triplot(points[:,0], points[:,1], tri.simplices.copy()) plt.plot(points[:,0], points[:,1], 'o') plt.show() |
The provided program generates the following output:
Output
This procedure may be applied as per the following examples:
Example 1:
This code uses the Python libraries numpy, matplotlib, and scipy to perform a Delaunay triangulation on a set of 2D points and visualize the resulting triangulation. The code starts by importing the necessary libraries, numpy, matplotlib, and scipy. Then it defines a 2D array of points, which represents a closed trapezoid shape in this example, that is used as the input for the Delaunay triangulation. The scipy library’s Delaunay() function is then used to perform the triangulation of the points, it takes the 2D array of points as input and returns a Delaunay triangulation object. The matplotlib library is then used to visualize the triangulation, the triplot() function creates a 2D plot of the triangulation, where the first two arguments are the x and y coordinates of the points, respectively, and the third argument is the set of triangles represented as indices of the input points. Additionally, a scatter plot of the points is created using the plt.plot(points[:,0], points[:,1], ‘o’) and it is displayed using the plt.show() function.
Python3
import numpy as np import matplotlib.pyplot as plt from scipy.spatial import Delaunay # A 2D array of points points = np.array([[3.0, 0.0], [2.0, 0.0], [2.0, 0.75], [2.5, 0.75], [2.5, 0.6], [2.25, 0.6], [2.25, 0.2], [3.0, 0.2], [3.0, 0.0]]) # Perform Delaunay triangulation tri = Delaunay(points) # Visualize the triangulation plt.triplot(points[:,0], points[:,1], tri.simplices.copy()) plt.plot(points[:,0], points[:,1], 'o') plt.show() |
Output:
Example 2:
This code uses the Python libraries numpy, matplotlib, and scipy to perform a Delaunay triangulation on a set of 2D points and visualize the resulting triangulation. It starts by importing the necessary libraries, then it creates a 2D array of points (15 points in this case) with x and y coordinates, it uses this array as input to perform the Delaunay triangulation using scipy’s Delaunay function, which returns a triangulation object. Next, it visualizes the triangulation using matplotlib’s triplot function, which creates a 2D plot of the triangulation, It also creates a scatter plot of the points using plt.plot and finally, it shows the plot using plt.show().
Python3
import numpy as np import matplotlib.pyplot as plt from scipy.spatial import Delaunay # A 2D array of points points = np.array([[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2], [3, 0], [3, 1], [3, 2], [4, 0], [4, 1], [4, 2]]) # Perform Delaunay triangulation tri = Delaunay(points) # Visualize the triangulation plt.triplot(points[:,0], points[:,1], tri.simplices.copy()) plt.plot(points[:,0], points[:,1], 'o') plt.show() |
Output:
Example 3:
This code uses the Python libraries numpy, matplotlib, and scipy to perform a Delaunay triangulation on a set of 2D points and visualize the resulting triangulation. It starts by importing the necessary libraries, then it creates a 2D array of points (9 points in this case) with x and y coordinates, it uses this array as input to perform the Delaunay triangulation using scipy’s Delaunay function, which returns a triangulation object. Next, it visualizes the triangulation using matplotlib’s triplot function, which creates a 2D plot of the triangulation, It also creates a scatter plot of the points using plt.plot and finally, it shows the plot using plt.show().
Python3
import numpy as np import matplotlib.pyplot as plt from scipy.spatial import Delaunay # A 2D array of points points = np.array([[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]) # Perform Delaunay triangulation tri = Delaunay(points) # Visualize the triangulation plt.triplot(points[:,0], points[:,1], tri.simplices.copy()) plt.plot(points[:,0], points[:,1], 'o') plt.show() |
Output:
In conclusion, Delaunay triangulation is a powerful mathematical concept that can be used to triangulate a set of points in a plane. In this article, we discussed how to perform Delaunay triangulation of points from a 2D surface in 3D using Python. We covered the steps required to generate some random points, perform the triangulation, and visualize the resulting triangulation. We also provided a few examples of Delaunay triangulation using different sets of points, and demonstrated how to generate a set of points on a sphere that can be triangulated to yield a 3D sphere.
