Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1""" 

2============================================================= 

3Spatial algorithms and data structures (:mod:`scipy.spatial`) 

4============================================================= 

5 

6.. currentmodule:: scipy.spatial 

7 

8Spatial transformations 

9======================= 

10 

11These are contained in the `scipy.spatial.transform` submodule. 

12 

13Nearest-neighbor queries 

14======================== 

15.. autosummary:: 

16 :toctree: generated/ 

17 

18 KDTree -- class for efficient nearest-neighbor queries 

19 cKDTree -- class for efficient nearest-neighbor queries (faster implementation) 

20 Rectangle 

21 

22Distance metrics are contained in the :mod:`scipy.spatial.distance` submodule. 

23 

24Delaunay triangulation, convex hulls, and Voronoi diagrams 

25========================================================== 

26 

27.. autosummary:: 

28 :toctree: generated/ 

29 

30 Delaunay -- compute Delaunay triangulation of input points 

31 ConvexHull -- compute a convex hull for input points 

32 Voronoi -- compute a Voronoi diagram hull from input points 

33 SphericalVoronoi -- compute a Voronoi diagram from input points on the surface of a sphere 

34 HalfspaceIntersection -- compute the intersection points of input halfspaces 

35 

36Plotting helpers 

37================ 

38 

39.. autosummary:: 

40 :toctree: generated/ 

41 

42 delaunay_plot_2d -- plot 2-D triangulation 

43 convex_hull_plot_2d -- plot 2-D convex hull 

44 voronoi_plot_2d -- plot 2-D Voronoi diagram 

45 

46.. seealso:: :ref:`Tutorial <qhulltutorial>` 

47 

48 

49Simplex representation 

50====================== 

51The simplices (triangles, tetrahedra, etc.) appearing in the Delaunay 

52tessellation (N-D simplices), convex hull facets, and Voronoi ridges 

53(N-1-D simplices) are represented in the following scheme:: 

54 

55 tess = Delaunay(points) 

56 hull = ConvexHull(points) 

57 voro = Voronoi(points) 

58 

59 # coordinates of the jth vertex of the ith simplex 

60 tess.points[tess.simplices[i, j], :] # tessellation element 

61 hull.points[hull.simplices[i, j], :] # convex hull facet 

62 voro.vertices[voro.ridge_vertices[i, j], :] # ridge between Voronoi cells 

63 

64For Delaunay triangulations and convex hulls, the neighborhood 

65structure of the simplices satisfies the condition: 

66``tess.neighbors[i,j]`` is the neighboring simplex of the ith 

67simplex, opposite to the ``j``-vertex. It is -1 in case of no neighbor. 

68 

69Convex hull facets also define a hyperplane equation:: 

70 

71 (hull.equations[i,:-1] * coord).sum() + hull.equations[i,-1] == 0 

72 

73Similar hyperplane equations for the Delaunay triangulation correspond 

74to the convex hull facets on the corresponding N+1-D 

75paraboloid. 

76 

77The Delaunay triangulation objects offer a method for locating the 

78simplex containing a given point, and barycentric coordinate 

79computations. 

80 

81Functions 

82--------- 

83 

84.. autosummary:: 

85 :toctree: generated/ 

86 

87 tsearch 

88 distance_matrix 

89 minkowski_distance 

90 minkowski_distance_p 

91 procrustes 

92 geometric_slerp 

93 

94""" 

95 

96from .kdtree import * 

97from .ckdtree import * 

98from .qhull import * 

99from ._spherical_voronoi import SphericalVoronoi 

100from ._plotutils import * 

101from ._procrustes import procrustes 

102from ._geometric_slerp import geometric_slerp 

103 

104__all__ = [s for s in dir() if not s.startswith('_')] 

105__all__ += ['distance', 'transform'] 

106 

107from . import distance, transform 

108 

109from scipy._lib._testutils import PytestTester 

110test = PytestTester(__name__) 

111del PytestTester