добавление точек на пиксель вдоль некоторой оси для 2D многоугольника

Question

Предполагая, что у меня есть открытый многоугольник, представленный списком 2D точек.Например, представление некоторого вида треугольника-многоугольника без основы было бы:

import numpy as np
polygon_arr = np.array([[0,0], [15,10], [2,4]])

Я ищу элегантный способ обогатить представление, то есть добавить точки к polygon_arr такой, что сам многоугольник не изменится, но для каждого значения y (в диапазоне многоугольника) в polygon_arr .

будет соответствующая точка. Пример:

simple_line_polygon = np.array([[0,0], [10,5]])
enriched_representation = foo(simple_line_polygon)
# foo() should return: np.array([[0,0], [2,1], [4,2], [6,3], [8,4], [10,5]])

Я думал о рассмотрении каждой из двух смежных точек в многоугольнике, построил линейное уравнение (y = mx + n) и отобрал его для каждого y в пределах диапазона;затем рассмотрим особые случаи, такие как две точки, расположенные вертикально (поэтому уравнение линии не определено), и случай, когда точки уже ближе друг к другу, чем изменение y на один пиксель в значении y.Тем не менее, это не так элегантно, и было бы полезно получить лучшие идеи.

Answer 1

Здесь нет необходимости в линейном уравнении.Вы можете просто масштабировать x и y расстояния между точками отдельно.Если между точками должно быть минимальное расстояние, вы можете проверить это, вычислив евклидово расстояние между углами.Вот небольшая функция, которая, мы надеемся, делает то, что вам нужно:

import numpy as np

def enrich_polygon(polygon, maxpoints = 5, mindist=1):

    result = []

    ##looping over all lines of the polygon:
    for start, end in zip(polygon, np.vstack([polygon[1:],polygon[:1]])):
        dist = np.sqrt(np.sum((start-end)**2)) ##distance between points
        N = int(min(maxpoints+1,dist/mindist)) ##amount of sub-sections
        if N < 2:                              ##mindist already reached
            result += [start]

        ##generating the new points:
        ##put all points (including original start) on the line into results 
        else:
            result += [
                start+i*(end-start)/(N-1) for i in range(N-1)
            ]
    return np.array(result)

polygon_arr = np.array([[0,0], [15,10], [2,4]])
res = enrich_polygon(polygon_arr)

print(res)

Функция берет исходный многоугольник и выполняет итерацию по парам соседних угловых точек.Если расстояние между двумя углами больше mindist, новые точки будут добавлены вплоть до максимальных точек (максимальное количество точек, добавляемых на линию).Для данного примера результат выглядит так:

[[ 0.          0.        ]
 [ 3.          2.        ]
 [ 6.          4.        ]
 [ 9.          6.        ]
 [12.          8.        ]
 [15.         10.        ]
 [12.4         8.8       ]
 [ 9.8         7.6       ]
 [ 7.2         6.4       ]
 [ 4.6         5.2       ]
 [ 2.          4.        ]
 [ 1.33333333  2.66666667]
 [ 0.66666667  1.33333333]]