Пространственные данные SciPy
Пространственные данные, также известные как геометрические данные, используются для представления информации о различных аспектах объектов, таких как положение, форма, распределение размеров и т. д., например, точек на координатах.
SciPy обрабатывает пространственные данные через модуль scipy.spatial, например, определяет, находится ли точка внутри границы, вычисляет ближайшую точку вокруг заданной точки и все точки в пределах заданного расстояния.
Триангуляция
Триангуляция, в тригонометрии и геометрии, — это метод измерения расстояния до цели путём измерения углов между целевой точкой и известными конечными точками фиксированной базовой линии.
Триангуляция многоугольника — это разбиение многоугольника на несколько треугольников, и мы можем использовать эти треугольники для вычисления площади многоугольника.
Известный факт в топологии говорит нам, что любая поверхность имеет триангуляцию.
Предположим, что на поверхности имеется триангуляция. Пусть общее число вершин всех треугольников обозначено как p (общие вершины считаются только один раз), число рёбер — как a, а число треугольников — как n. Тогда e = p - a + n — топологический инвариант поверхности. То есть, какую бы триангуляцию ни использовать, e всегда даёт одно и то же значение. e называется эйлеровой характеристикой.
Метод триангуляции множества точек — это триангуляция Delaunay().
Пример
Создайте треугольники из заданных точек:
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 # индексы вершин в треугольнике
plt.triplot(points[:, 0], points[:, 1], simplices)
plt.scatter(points[:, 0], points[:, 1], color='r')
plt.show()
Результат вывода показан на рисунке ниже:

Примечание:Идентификаторы вершин треугольников хранятся в атрибуте simplices объекта триангуляции.
Выпуклая оболочка
Выпуклая оболочка — это понятие в вычислительной геометрии (графике).
В вещественном векторном пространстве V для заданного множества X пересечение S всех выпуклых множеств, содержащих X, называется выпуклой оболочкой X. Выпуклую оболочку X можно построить с помощью выпуклых комбинаций всех точек (X1, ...Xn) из X.
Мы можем использовать метод ConvexHull() для создания выпуклой оболочки.
Пример
Создайте выпуклую оболочку из заданных точек:
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()
Результат вывода показан на рисунке ниже:

K-D-дерево
kd-tree (сокращение от k-мерного дерева) — это древовидная структура данных, которая хранит точки экземпляров в k-мерном пространстве для быстрого поиска. Она в основном используется для поиска ключевых данных в многомерном пространстве (например, поиск по диапазону и поиск ближайшего соседа).
K-D-деревья могут использоваться в различных приложениях, таких как многомерный поиск ключей (поиск по диапазону и поиск ближайшего соседа).
Поиск ближайшего соседа используется для нахождения точки в дереве, ближайшей к входной точке.
KDTree()Метод возвращает объект KDTree.
query()Метод возвращает расстояние до ближайшего соседа и позицию ближайшего соседа.
Пример
Найдите расстояние до ближайшего соседа для (1,1):
points = [(1, -1), (2, 3), (-2, 3), (2, -3)]
kdtree = KDTree(points)
res = kdtree.query((1, 1))
print(res)
Результат вывода показан на рисунке ниже:
(2.0, 0)
Матрица расстояний
В математике матрица расстояний — это матрица (двумерный массив), элементами которой являются расстояния между точками. Следовательно, для N точек в евклидовом пространстве её матрица расстояний — это матрица, элементами которой являются неотрицательные действительные числа.N×NСимметричная матрица. Матрица расстояний и матрица смежности схожи по концепции, разница в том, что последняя содержит только информацию о наличии ребра между элементами (точками) и не содержит информацию о расстоянии связи между элементами (точками). Поэтому матрицу расстояний можно рассматривать как взвешенную форму матрицы смежности.
Например, мы анализируем следующие двумерные точки от a до f. Здесь в качестве метрики расстояния мы берём евклидову метрику между пикселями, в которых расположены точки.

Её матрица расстояний такова:

Эти данные матрицы расстояний можно далее рассматривать как тепловую карту в графическом представлении (как показано на рисунке ниже), где чёрный цвет обозначает нулевое расстояние, а белый — максимальное расстояние.

В биоинформатике матрицы расстояний используются для представления структур белков независимо от систем координат, а также расстояний между двумя последовательностями в пространстве последовательностей. Эти представления используются при выравнивании структур, выравнивании последовательностей и при определении структур белков методами ЯМР, рентгеновской кристаллографии и кристаллографии.
Евклидово расстояние
В математике евклидово расстояние или евклидова метрика — это «обычное» (т. е. прямолинейное) расстояние между двумя точками в евклидовом пространстве. С этим расстоянием евклидово пространство становится метрическим пространством. Соответствующая норма называется евклидовой нормой. В более ранней литературе её называют пифагорейской метрикой.
Евклидова метрика (также называемая евклидовым расстоянием) — это широко используемое определение расстояния, означающее фактическое расстояние между двумя точками в m-мерном пространстве или естественную длину вектора (т. е. расстояние от точки до начала координат). В двумерном и трёхмерном пространстве евклидово расстояние — это фактическое расстояние между двумя точками.
В следующем примере рассматривается евклидово расстояние между заданными точками:
Пример
p1 = (1, 0)
p2 = (10, 2)
res = euclidean(p1, p2)
print(res)
Результат вывода показан на рисунке ниже:
9.21954445729
Манхэттенское расстояние
Геометрия такси, или манхэттенское расстояние, — термин, придуманный Германом Минковским в девятнадцатом веке. Это геометрический термин, используемый в метрических пространствах для обозначения суммы абсолютных осевых расстояний между двумя точками в стандартной системе координат.
Манхэттенское расстояние допускает движение только в четырёх направлениях: вверх, вниз, влево и вправо, а манхэттенское расстояние между двумя точками — это кратчайшее расстояние между ними.
Манхэттенское расстояние против евклидова: красная, синяя и жёлтая линии соответственно показывают, что все манхэттенские расстояния имеют одинаковую длину (12), тогда как зелёная линия показывает, что евклидово расстояние имеет длину 6×√2 ≈ 8.48.

В следующем примере вычисляется манхэттенское расстояние между заданными точками:
Пример
p1 = (1, 0)
p2 = (10, 2)
res = cityblock(p1, p2)
print(res)
Результат вывода:
11
Косинусное расстояние
Косинусное расстояние, также известное как косинусное сходство, измеряет сходство между двумя векторами путём измерения косинуса угла между ними.
Косинус угла 0 градусов равен 1, тогда как косинус любого другого угла не больше 1, а его минимальное значение равно -1.
Следующий пример вычисляет косинусное расстояние между точками A и B:
Пример
p1 = (1, 0)
p2 = (10, 2)
res = cosine(p1, p2)
print(res)
Результат вывода:
0.019419324309079777
Расстояние Хэмминга
В теории информации расстояние Хэмминга между двумя строками одинаковой длины — это количество позиций, в которых соответствующие символы различаются. Иными словами, это количество символов, которые нужно заменить, чтобы преобразовать одну строку в другую.
Вес Хэмминга — это расстояние Хэмминга между строкой и нулевой строкой той же длины. Иными словами, это количество ненулевых элементов в строке: для двоичной строки это количество единиц, поэтому вес Хэмминга для 11101 равен 4.
- 1011101и1001001Расстояние Хэмминга между ними равно 2.
- 2143896и2233796Расстояние Хэмминга между ними равно 3.
- "toned"and"roses"Расстояние Хэмминга между ними равно 3."
В следующем примере вычисляется расстояние Хэмминга между двумя точками:
Пример
p1 = (True, False, True)
p2 = (False, True, True)
res = hamming(p1, p2)
print(res)
Результат вывода:
0.666666666667Другие расширения