записывать только видимые точки на диск перегруженной диаграммы рассеяния

Question

Я создаю диаграммы рассеяния matplotlib из 10000 пунктов. При размере точек, который я использую, это приводит к избыточному построению, то есть некоторые из точек будут скрыты точками, нанесенными на них.

Хотя я не против того, что я не вижу скрытых точек, они избыточно записываются, когда я записываю фигуру на диск в формате pdf (или в другом векторном формате), в результате получается большой файл.

Есть ли способ создать векторное изображение, в котором в файл будут записаны только видимые точки? Это было бы похоже на концепцию «выравнивания» / слияния слоев в программном обеспечении для редактирования фотографий. (Я все еще хотел бы сохранить изображение как вектор, поскольку я хотел бы иметь возможность увеличения).

Пример графика:

import numpy as np
import pandas as pd
import random
import matplotlib.pyplot as plt
random.seed(15)

df = pd.DataFrame({'x': np.random.normal(10, 1.2, 10000), 
                   'y': np.random.normal(10, 1.2, 10000), 
                   'color' : np.random.normal(10, 1.2, 10000)})
df.plot(kind = "scatter", x = "x", y = "y", c = "color", s = 80, cmap = "RdBu_r")
plt.show()

Answer 1

tl; dr

Я не знаю ни одного простого решения, такого как

RemoveOccludedCircles(C)

Приведенный ниже алгоритм требует некоторой реализации, но он не должен быть слишком плохим.

Переформулировка проблемы

Хотя мы можем попытаться удалить существующие круги при добавлении новых, я считаю, что проще думать о проблеме наоборот, обрабатывая все круги в обратном порядке и делая вид, что рисуем каждую из них. Новый круг позади существующих.

Тогда возникает следующая основная проблема: Как я могу эффективно определить, будет ли один круг полностью скрыт другим набором кругов?

Условия

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

Структуры данных

C: набор видимых кругов

P: набор контрольных точек

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

Визуализация задачи

Чтобы лучше понять роль контрольных точек, их обслуживание и алгоритм, взгляните на следующий рисунок: Обработка 6 кругов

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

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

Обслуживание контрольной точки

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

После размещения одного круга справедливо следующее предположение: новый круг полностью скрыт существующими кругами, если

1. Его центр падает в видимый круг.
2. Нет Контрольная точка находится строго внутри нового круга.

Чтобы сохранить это предположение при добавлении новых кругов, набор контрольных точек необходимо обновлять после каждого добавления видимого круг:

1. Добавьте 4 новые контрольные точки для нового круга, как описано выше.

2. Добавьте новые контрольные точки на каждом пересечении нового круг с существующими видимыми кругами.

3. Удалите все контрольные точки, которые l ie строго внутри любого видимого круга.

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

Псевдокод

AllCircles <- All circles, sorted from front to back
C <- {} // the set of visible circles
P <- {} // the set of control points
for X in AllCircles {
  if (Inside(center(X), C) AND Outside(P, X)) {
    // ignore circle, it is occluded!
  } else {
    C <- C + X
    P <- P + CreateFourControlPoints(X)
    P <- P + AllCuttingPoints(X, C)
    RemoveHiddenControlPoints(P, C)
  }
}
DrawCirclesInReverseOrder(C)

Функции «Внутри» и «Снаружи» здесь немного абстрактны, поскольку «Внутри» возвращает истину, если точка содержится в одном или нескольких окружностях из окружностей с сеткой и ' Снаружи 'возвращает true, если все точки из набора точек l ie за пределами круга. Но ни одна из используемых функций не должна быть трудной для записи.

Незначительные проблемы, которые необходимо решить

1. Как определить численно устойчивым образом, находится ли точка строго внутри круг? -> Это не должно быть слишком плохо для решения, так как все точки никогда не являются более сложными, чем решение квадратного уравнения c. Тем не менее, важно , не полагаться только на представления с плавающей запятой, поскольку они будут численно недостаточны, и некоторые контрольные точки могут быть полностью потеряны, фактически оставляя дыры в конечном графике. Поэтому сохраните символ c и точное представление координат контрольной точки. Я бы попытался SymPy решить эту проблему, поскольку она, кажется, охватывает всю необходимую математику. Формула для пересекающихся кругов легко найти в Интернете, например, здесь .

2. Как эффективно определить, содержит ли круг какую-либо контрольную точку или любой видимый круг содержит центр нового круга? -> Чтобы решить эту проблему, я бы предложил сохранить все элементы P и C в решетчатых структурах, где ширина и высота каждого элемента сетки равна радиусу окружностей. В среднем, число активных точек и видимых окружностей на ячейку сетки должно быть в O (1), хотя можно создать искусственные установки с произвольным количеством элементов на ячейку сетки, что могло бы превратить общий алгоритм из O (N) к O (N * N).

Мысли о времени выполнения

Как упоминалось выше, я ожидаю, что время выполнения будет линейно масштабироваться с количеством кругов в среднем, потому что количество видимых кругов в каждой ячейке сетки будет в O (N), если не построено злым путем.

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

Answer 2

Мое лучшее предположение было бы использовать hexbin. Обратите внимание, что на точечной диаграмме отображаются только те точки, которые отображаются последними. При hexbin все совпадающие точки будут усреднены.

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

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

np.random.seed(15)
df = pd.DataFrame({'x': np.random.normal(10, 1.2, 10000),
                   'y': np.random.normal(10, 1.2, 10000),
                   'color': np.random.normal(10, 1.2, 10000)})

fig, ax = plt.subplots(ncols=4, gridspec_kw={'width_ratios': [10,10,10,1]})

norm = plt.Normalize(df.color.min(), df.color.max())
df.plot(kind="scatter", x="x", y="y", c="color", s=10, cmap="RdBu_r", norm=norm, colorbar=False, ax=ax[0])

hexb = ax[1].hexbin(df.x, df.y, df.color, cmap="RdBu_r", norm=norm, gridsize=80)

centers = hexb.get_offsets()
values = hexb.get_array()
ax[2].scatter(centers[:,0], centers[:,1], c=values, s=10, cmap="RdBu_r", norm=norm)

plt.colorbar(hexb, cax=ax[3])
plt.show()

Вот еще одно сравнение. Количество точек уменьшается с коэффициентом 10, и график становится более «честным», так как перекрывающиеся точки усредняются.