Computer vision, Machine Learning

Построение диаграммы Вороного в Python для задач визуализации

Время прочтения: 5 мин.

Диаграмма Вороного представляет собой множество точек и регионов на плоскости.

Рисунок 1 – Диаграмма Вороного

Для точек (seed points) и регионов (Voronoi cells) диаграммы Вороного на плоскости действуют следующие правила:

  1. В каждом из регионов находится только одна точка pi.
  2. Расстояние от любой точки одного региона ближе к seed точке pi этого региона, чем к любой другой seed точке.

Диаграмма Вороного может быть использована для решения широкого спектра задач — геометрических, картографических, задач построения логики искусственного интеллекта, а также применяется в машинном обучении и computer vision.

Построение диаграммы на простом примере

Существует множество различных способов построения диаграммы Вороного. В статье приведён способ построения диаграммы упрощённым методом, по своему исполнению более всего напоминающим 3-d Convex Hull.

Суть алгоритма:

  1. Каждая точка pi с 2д плоскости последовательно проецируется на 3д параболоид с центром в этой точке.
  2. Для первой точки p1 массив с исходной матрицей fields заполненной значениями, заведомо превышающими значения массива paraboloid, таким образом матрица colors заполняется одним кодом, соответствующим одному цвету (рис. 1).
  3. Следующим шагом матрица значений paraboloid перетирается новыми данными для следующей точки pi, для дальнейшего сравнения с матрицей fields, обновляя, таким образом, массив colors в точках, соответствующих новой цветовой зоне (рис. 2).
  4. Массив field обновляется с учетом вершины нового параболоида, а алгоритм снова переходит к пункту 3 (дальнейшее построение представлено на рис. 3 и рис. 4).

Для упрощения восприятия можно привести пример построения диаграммы для 4 точек и код программы ниже:

Рисунок 2
Рисунок 3
Рисунок 4
Рисунок 5
shape = 10,10
dot_x = [2,5,7,2]                               
dot_y = [2,5,2,7]
points = ([2,2], [5,5],
          [7,2], [2,7])  
def Z(X,Y):                     #матрица значений Z параболоида
    return (X-x)**2 + (Y-y)**2
for i,(x,y) in enumerate(points):    #кол-во циклов определяется числом точек
    paraboloid = numpy.fromfunction(Z,(shape))  #создается массив Z для отдельной точки
    colors = numpy.where(paraboloid < field,i+1,colors) #заполняется цветовая матрица
    field = numpy.where(paraboloid < field,paraboloid,field) №

    fig = plt.figure(figsize=plt.figaspect(0.5))   
    ax = fig.add_subplot(1, 2, 1, projection='3d')
    X = np.arange(0, 10, 1)
    Y = np.arange(0, 10, 1)
    X, Y = np.meshgrid(X, Y)
    surf = ax.plot_surface(X, Y, paraboloid,rstride=1, cstride=1, cmap=cm.magma,
                       linewidth=0, antialiased=False)
    ax.set_zlim(0, 100)
    fig.colorbar(surf, shrink=0.5, aspect=10)
    ax = fig.add_subplot(1, 2, 2)
    C = numpy.transpose(colors)
    ax.imshow(C, cmap=cm.magma, alpha = 1)
    ax.scatter(dot_x, dot_y , c = 'Red')
    ax.scatter(dot_x[i], dot_y[i] , c = 'Blue')
    plt.show()

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

Решение прикладной задачи при помощи диаграммы Вороного

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

Входными данными в данной ситуации служат карта местности (г. Новосибирск) и нанесенные на неё координаты остановок (рис. 5).

Рисунок 6 – Карта Новосибирска с отмеченными на ней остановками общественного транспорта

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

 А именно:

shape = 1244,767 #размер карты
dot_x = [390,440,423,403,377,355,337,331,541,572,611,605,499,531,567,592,458,439,422,460,471,479,497,435]
dot_y = [533,557,573,607,592,542,550,597,416,437,511,429,289,271,283,259,284,302,329,343,351,327,379,365]
points = ([390, 533], [440,557], [423, 573], [403, 607], [377, 592], [355, 542],
        [337, 550], [331, 597], [541, 416],[572,437],[611,511],[605,429],[499,289],[531,271],
        [567,283],[592,259],[458,284],[439,302],[422,329],[460,343],[471,351],[479,327],[497,379],[435,365])
#--------------------------- визуализция ---------------------------
C = numpy.transpose(colormap)
plt.figure(figsize=(40,20))
imgplot = plt.imshow(img, alpha=1)
plt.imshow(C, alpha = 0.2, cmap = cm.prism)   #, cmap = cm.prism
plt.scatter(dot_x, dot_y , c = 'Red')
plt.savefig('voronoi_map.png')
plt.show()

Результатом работы программы в данном случае является карта, поделённая на сегменты.

Рисунок 7 – Карта «зон покрытия» остановок общественного транспорта в г. Новосибирск

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

Советуем почитать