Найти все точки под линией на карте

Чтобы нарисовать путь между двумя точками на карте с большим количеством точек (почти две тысячи), я использую следующую функцию:

def path_between_cities(self, cities_with_coordinates, from_to):

        from matplotlib.lines import Line2D     

        # coordinates from chosen path
        x = [int(from_to[0][2]), int(from_to[1][2])]
        y = [int(from_to[0][1]), int(from_to[1][1])]

        #create line
        line = Line2D(x,y,linestyle='-',color='k')

        # create axis
        x_ = np.array((0,2000))
        y_ = np.array((0,6000))

        plt.plot(x_,y_, 'o')

        for item in cities_with_coordinates:
            name = item[0]
            y_coord = int(item[1])
            x_coord = int(item[2])
            plt.plot([x_coord], [y_coord], marker='o', markersize=1, color='blue')
            plt.axes().add_line(line)

        plt.axis('scaled')
        plt.show()

Моя цель - извлечь все точки (координаты), которые находятся ниже нарисованной линии.

Я знаю, что вы можете сделать это, используя перекрестное произведение векторов

Учитывая большое количество векторов, каким будет наиболее эффективный способ добиться этого в контексте выше?


python matplotlib computational-geometry cross-product
person 8-Bit Borges    schedule 11.07.2018    source источник
comment
Ваш вопрос действительно не имеет ничего общего с matplotlib или построением графика. У вас есть массив точек и линия, определяемая двумя точками. Это типичная задача вычислительной геометрии. Это можно решить, используя только NumPy (поскольку вы все равно его используете).   -  person DYZ    schedule 11.07.2018
comment
Я сказал, что вопрос зависит от matplotlib или plotting?   -  person 8-Bit Borges    schedule 11.07.2018
comment
Вы сделали это, пометив его matplotlib.   -  person DYZ    schedule 11.07.2018
comment
это относится к matplotib, отсюда и тег. В самом вопросе я использую слово «контекст», и это относится к matplotlib. в любом случае, извините, что ввел вас в заблуждение, сэр.   -  person 8-Bit Borges    schedule 11.07.2018
comment
Посмотрите, поможет ли это. Может действительно дубликат...   -  person Thomas Kühn    schedule 11.07.2018

Ответы (1)


arrow_upward
1
arrow_downward

Каждая операция перекрестного произведения по-прежнему O(1). Вы можете запустить приведенную ниже функцию для всех точек и посмотреть, какие из них находятся ниже, доведя ее до линейной проверки времени.

def ccw(a,b,c):
    """ Returns 1 if c is above directed line ab else returns -1"""
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y)
    #a and b are the vertices and c is the test point.

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

person gaganso    schedule 11.07.2018