Пространственные данные SciPy

Пространственные данные, также известные как геометрические данные, используются для представления информации о различных аспектах объектов, таких как положение, форма, распределение размеров и т. д., например, точек на координатах.

SciPy обрабатывает пространственные данные через модуль scipy.spatial, например, определяет, находится ли точка внутри границы, вычисляет ближайшую точку вокруг заданной точки и все точки в пределах заданного расстояния.

Триангуляция

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

Триангуляция многоугольника — это разбиение многоугольника на несколько треугольников, и мы можем использовать эти треугольники для вычисления площади многоугольника.

Известный факт в топологии говорит нам, что любая поверхность имеет триангуляцию.

Предположим, что на поверхности имеется триангуляция. Пусть общее число вершин всех треугольников обозначено как p (общие вершины считаются только один раз), число рёбер — как a, а число треугольников — как n. Тогда e = p - a + n — топологический инвариант поверхности. То есть, какую бы триангуляцию ни использовать, e всегда даёт одно и то же значение. e называется эйлеровой характеристикой.

Метод триангуляции множества точек — это триангуляция Delaunay().

Пример

Создайте треугольники из заданных точек:

import numpy as np
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() для создания выпуклой оболочки.

Пример

Создайте выпуклую оболочку из заданных точек:

import numpy as np
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):

from scipy.spatial import KDTree

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-мерном пространстве или естественную длину вектора (т. е. расстояние от точки до начала координат). В двумерном и трёхмерном пространстве евклидово расстояние — это фактическое расстояние между двумя точками.

В следующем примере рассматривается евклидово расстояние между заданными точками:

Пример

from scipy.spatial.distance import euclidean

p1 = (1, 0)
p2 = (10, 2)

res = euclidean(p1, p2)

print(res)

Результат вывода показан на рисунке ниже:

9.21954445729

Манхэттенское расстояние

Геометрия такси, или манхэттенское расстояние, — термин, придуманный Германом Минковским в девятнадцатом веке. Это геометрический термин, используемый в метрических пространствах для обозначения суммы абсолютных осевых расстояний между двумя точками в стандартной системе координат.

Манхэттенское расстояние допускает движение только в четырёх направлениях: вверх, вниз, влево и вправо, а манхэттенское расстояние между двумя точками — это кратчайшее расстояние между ними.

Манхэттенское расстояние против евклидова: красная, синяя и жёлтая линии соответственно показывают, что все манхэттенские расстояния имеют одинаковую длину (12), тогда как зелёная линия показывает, что евклидово расстояние имеет длину 6×√2 ≈ 8.48.

В следующем примере вычисляется манхэттенское расстояние между заданными точками:

Пример

from scipy.spatial.distance import cityblock

p1 = (1, 0)
p2 = (10, 2)

res = cityblock(p1, p2)

print(res)

Результат вывода:

11

Косинусное расстояние

Косинусное расстояние, также известное как косинусное сходство, измеряет сходство между двумя векторами путём измерения косинуса угла между ними.

Косинус угла 0 градусов равен 1, тогда как косинус любого другого угла не больше 1, а его минимальное значение равно -1.

Следующий пример вычисляет косинусное расстояние между точками A и B:

Пример

from scipy.spatial.distance import cosine

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."

В следующем примере вычисляется расстояние Хэмминга между двумя точками:

Пример

from scipy.spatial.distance import hamming

p1 = (True, False, True)
p2 = (False, True, True)

res = hamming(p1, p2)

print(res)

Результат вывода:

0.666666666667
Другие расширения