Données spatiales SciPy
Les données spatiales, également appelées données géométriques, sont utilisées pour représenter des informations sur divers aspects des objets tels que la position, la forme, la distribution de taille, etc., par exemple, des points sur des coordonnées.
SciPy gère les données spatiales via le module scipy.spatial, comme déterminer si un point se trouve à l'intérieur d'une limite, calculer le point le plus proche autour d'un point donné, et tous les points dans une distance donnée.
Triangulation
La triangulation, en trigonométrie et en géométrie, est une méthode de mesure de la distance à une cible en mesurant les angles entre le point cible et les extrémités connues d'une ligne de base fixe.
La triangulation d'un polygone est la division du polygone en plusieurs triangles, et nous pouvons utiliser ces triangles pour calculer l'aire du polygone.
Un fait connu en topologie nous dit que toute surface admet une triangulation.
Supposons qu'il existe une triangulation sur une surface. Soit p le nombre total de sommets de tous les triangles (les sommets communs ne sont comptés qu'une seule fois), a le nombre d'arêtes et n le nombre de triangles. Alors e = p - a + n est un invariant topologique de la surface. Autrement dit, quelle que soit la triangulation utilisée, e donne toujours la même valeur. On appelle e la caractéristique d'Euler.
La méthode de triangulation d'un ensemble de points est la triangulation Delaunay().
Exemple
Créer des triangles à partir des points donnés :
from scipy.spatial import Delaunay
import matplotlib.pyplot as plt
points = np.array([
[2, 4],
[3, 4],
[3, 0],
[2, 2],
[4, 1]
])
simplices = Delaunay(points).simplices # indices des sommets dans le triangle
plt.triplot(points[:, 0], points[:, 1], simplices)
plt.scatter(points[:, 0], points[:, 1], color='r')
plt.show()
Le résultat de sortie est présenté dans la figure ci-dessous :
Remarque :Les identifiants des sommets du triangle sont stockés dans l'attribut simplices de l'objet de triangulation.
Enveloppe convexe
L'enveloppe convexe est un concept de géométrie algorithmique (infographie).
Dans un espace vectoriel réel V, pour un ensemble X donné, l'intersection S de tous les ensembles convexes contenant X est appelée l'enveloppe convexe de X. L'enveloppe convexe de X peut être construite en utilisant des combinaisons convexes de tous les points (X1, ...Xn) de X.
Nous pouvons utiliser la méthode ConvexHull() pour créer une enveloppe convexe.
Exemple
Créer une enveloppe convexe à partir de points donnés :
from scipy.spatial import ConvexHull
import matplotlib.pyplot as plt
points = np.array([
[2, 4],
[3, 4],
[3, 0],
[2, 2],
[4, 1],
[1, 2],
[5, 0],
[3, 1],
[1, 2],
[0, 2]
])
hull = ConvexHull(points)
hull_points = hull.simplices
plt.scatter(points[:,0], points[:,1])
for simplex in hull_points:
plt.plot(points[simplex,0], points[simplex,1], 'k-')
plt.show()
Le résultat de sortie est présenté dans la figure ci-dessous :
Arbre K-D
kd-tree (abréviation de k-dimensional tree) est une structure de données arborescente qui stocke des points d'instance dans un espace à k dimensions pour une récupération rapide. Elle est principalement utilisée pour rechercher des données clés dans un espace multidimensionnel (par exemple, recherche par intervalle et recherche des plus proches voisins).
Les arbres K-D peuvent être utilisés dans diverses applications, telles que la recherche de clés multidimensionnelle (recherche par intervalle et recherche des plus proches voisins).
La recherche du plus proche voisin est utilisée pour trouver le point de l'arbre le plus proche du point d'entrée.
KDTree()La méthode renvoie un objet KDTree.
query()La méthode renvoie la distance au plus proche voisin et la position du plus proche voisin.
Exemple
Trouver la distance au plus proche voisin de (1,1) :
points = [(1, -1), (2, 3), (-2, 3), (2, -3)]
kdtree = KDTree(points)
res = kdtree.query((1, 1))
print(res)
Le résultat de sortie est présenté dans la figure ci-dessous :
(2.0, 0)
Matrice de distances
En mathématiques, une matrice de distances est une matrice (tableau bidimensionnel) dont les éléments sont les distances entre les points. Par conséquent, étant donné N points dans l'espace euclidien, sa matrice de distances est une matrice dont les éléments sont des nombres réels non négatifs.N×NLa matrice symétrique. La matrice de distances et la matrice d'adjacence sont similaires en concept, la différence étant que cette dernière ne contient que la présence ou l'absence d'une arête entre les éléments (points), et ne contient pas d'information sur la distance de la connexion entre les éléments (points). Par conséquent, une matrice de distances peut être considérée comme une forme pondérée d'une matrice d'adjacence.
Par exemple, nous analysons les points bidimensionnels suivants de a à f. Ici, nous prenons la métrique euclidienne entre les pixels où se trouvent les points comme métrique de distance.
Sa matrice de distances est :
Ces données de la matrice de distances peuvent en outre être visualisées sous forme de carte thermique dans une représentation graphique (comme le montre la figure ci-dessous), où le noir représente une distance nulle et le blanc représente la distance maximale.
En bio-informatique, les matrices de distances sont utilisées pour représenter les structures protéiques indépendamment des systèmes de coordonnées, ainsi que les distances entre deux séquences dans l’espace des séquences. Ces représentations sont utilisées dans l’alignement de structures, l’alignement de séquences et pour déterminer les structures protéiques en RMN, en rayons X et en cristallographie.
Distance euclidienne
En mathématiques, la distance euclidienne ou métrique euclidienne est la distance « ordinaire » (c’est-à-dire en ligne droite) entre deux points de l’espace euclidien. Avec cette distance, l’espace euclidien devient un espace métrique. La norme associée est appelée norme euclidienne. La littérature antérieure la désigne sous le nom de métrique pythagoricienne.
La métrique euclidienne (également appelée distance euclidienne) est une définition couramment utilisée de la distance, désignant la distance réelle entre deux points dans un espace à m dimensions, ou la longueur naturelle d’un vecteur (c’est-à-dire la distance du point à l’origine). Dans l’espace bidimensionnel et tridimensionnel, la distance euclidienne est la distance réelle entre deux points.
L’exemple suivant examine la distance euclidienne entre les points donnés :
Exemple
p1 = (1, 0)
p2 = (10, 2)
res = euclidean(p1, p2)
print(res)
Le résultat de sortie est présenté dans la figure ci-dessous :
9.21954445729
Distance de Manhattan
La géométrie des taxis ou distance de Manhattan est un terme inventé par Hermann Minkowski au dix-neuvième siècle. C’est un terme géométrique utilisé dans les espaces métriques pour indiquer la somme des distances axiales absolues entre deux points dans un système de coordonnées standard.
La distance de Manhattan n’autorise que les déplacements dans les quatre directions haut, bas, gauche et droite, et la distance de Manhattan entre deux points est la plus courte distance entre eux.
Distance de Manhattan vs distance euclidienne : les lignes rouge, bleue et jaune indiquent respectivement que toutes les distances de Manhattan ont la même longueur (12), tandis que la ligne verte indique que la distance euclidienne a une longueur de 6×√2 ≈ 8.48.
L’exemple suivant calcule la distance de Manhattan entre les points donnés :
Exemple
p1 = (1, 0)
p2 = (10, 2)
res = cityblock(p1, p2)
print(res)
Le résultat de sortie est:
11
Distance cosinus
La distance cosinus, également appelée similarité cosinus, mesure la similarité entre deux vecteurs en mesurant le cosinus de l'angle entre eux.
Le cosinus d'un angle de 0 degré est 1, tandis que le cosinus de tout autre angle n'est pas supérieur à 1, et sa valeur minimale est -1.
L'exemple suivant calcule la distance cosinus entre les points A et B :
Exemple
p1 = (1, 0)
p2 = (10, 2)
res = cosine(p1, p2)
print(res)
Le résultat de sortie est:
0.019419324309079777
Distance de Hamming
En théorie de l'information, la distance de Hamming entre deux chaînes de même longueur est le nombre de positions auxquelles les caractères correspondants diffèrent. En d'autres termes, c'est le nombre de caractères qui doivent être remplacés pour transformer une chaîne en l'autre.
Le poids de Hamming est la distance de Hamming entre une chaîne et une chaîne de zéros de même longueur. En d'autres termes, c'est le nombre d'éléments non nuls dans la chaîne : pour une chaîne binaire, c'est le nombre de 1, donc le poids de Hamming de 11101 est 4.
- 1011101et1001001La distance de Hamming entre elles est 2.
- 2143896et2233796La distance de Hamming entre elles est 3.
- "toned"et"roses"La distance de Hamming entre eux est de 3.
L'exemple suivant calcule la distance de Hamming entre deux points :
Exemple
p1 = (True, False, True)
p2 = (False, True, True)
res = hamming(p1, p2)
print(res)
Le résultat de sortie est:
0.666666666667Autres extensions