Как я могу проверить, находится ли точка ниже линии или нет?

Question

Как я могу проверить, находится ли точка ниже линии или нет?

У меня есть следующие данные:

Line [ {x1,y1}, {x2,y2} ]
Points {xA,yA}, {xB,yB} ...

Мне нужно написать небольшой алгоритм на python для обнаружения точек на одной стороне и другой стороне линии.

спасибо

Answer 1

Вы можете попробовать использовать перекрестный продукт - http://en.wikipedia.org/wiki/Cross_product.

v1 = {x2-x1, y2-y1}   # Vector 1
v2 = {x2-xA, y2-yA}   # Vector 1
xp = v1.x*v2.y - v1.y*v2.x  # Cross product
if xp > 0:
    print 'on one side'
elif xp < 0:
    print 'on the other'
else:
    print 'on the same line!'

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

Я не проверял это.

Редактировать Я изначально ввел формулу точечного произведения. : О

К счастью, я нашел Расчет перекрестного произведения двухмерного вектора .

Answer 2

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

v1 = {x2-x1, y2-y1}   # Vector 1
v2 = {xA-x1, yA-y1}   # Vector 2
cross_product = v1.x*v2.y - v1.y*v2.x
if cross_product > 0:
    print 'pointA is on the counter-clockwise side of line'
elif xp < 0:
    print 'pointA is on the clockwise side of line'
else:
    print 'pointA is exactly on the line'

Answer 3

Допустим, вы дали 2 балла A, B и хотите знать, в какой полуплоскости находится третья точка C.Термины «ниже» и «выше» в качестве критериев очень расплывчаты, поэтому вам нужен ориентир, например, источник.Просто убедитесь, что эта контрольная точка не коллинеарна с A и B.

Теперь у вас есть треугольник (A, B, C).Используя определитель, вы можете вычислить область со знаком ( см. Здесь или здесь ).Единственное, что здесь интересно, это запомнить знак.

Следующий шаг: для заданной точки D вычислите область треугольника со знаком (A, B, D).Если результат имеет тот же знак, что и область вашего контрольного треугольника -> C и D находятся на одной стороне от (A, B).Если знак отличается -> C и D лежат на противоположных сторонах линии.Если площадь (A, B, D) равна 0, то A, B и D коллинеарны.Примечание: используйте встроенный Python cmp для сравнения областей треугольника.