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

Question

Цель

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

Входы

Углы четырехугольника: (x1, y1) (x2, y2) (x3, y3) (x4, y4)

Контрольная точка: (xt, yt)

выход

1 - Если в четырехугольнике

0 - В противном случае

Update

Было отмечено, что идентификации вершин четырехугольника недостаточно для однозначной идентификации. Можно предположить, что порядок точек определяет стороны четырехугольника (точка 1 соединяет 2, 2 соединяется с 3, 3 соединяется с 4, 4 соединяется с 1)

Answer 1

Вы можете проверить точку с этим условием.Также вы можете рассматривать четырехугольник как 2 треугольника для расчета его площади.

Answer 2

Использование inpolygon. Использование будет inpolygon(xt,yt,[x1 x2 x3 x4],[y1 y2 y3 y4])

Answer 3

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

РЕДАКТИРОВАТЬ Вот некоторый псевдокод для точки в треугольнике:

function SameSide(p1,p2, a,b)
    cp1 = CrossProduct(b-a, p1-a)
    cp2 = CrossProduct(b-a, p2-a)
    if DotProduct(cp1, cp2) >= 0 then return true
    else return false

function PointInTriangle(p, a,b,c)
    if SameSide(p,a, b,c) and SameSide(p,b, a,c)
        and SameSide(p,c, a,b) then return true
    else return false

Или используя барицентрическую технику:

A, B и C - конечные точки треугольника, P - тестируемая точка

// Compute vectors        
v0 = C - A
v1 = B - A
v2 = P - A

// Compute dot products
dot00 = dot(v0, v0)
dot01 = dot(v0, v1)
dot02 = dot(v0, v2)
dot11 = dot(v1, v1)
dot12 = dot(v1, v2)

// Compute barycentric coordinates
invDenom = 1 / (dot00 * dot11 - dot01 * dot01)
u = (dot11 * dot02 - dot01 * dot12) * invDenom
v = (dot00 * dot12 - dot01 * dot02) * invDenom

// Check if point is in triangle
return (u > 0) && (v > 0) && (u + v < 1)

Answer 4

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

Answer 5

в предположении, что данные координаты расположены st (x1, y1) = крайняя правая координата (x2, y2) = верхняя координата (x3, y3) = крайняя левая координата (x4, y4) = самая нижняя координата

Вы можете сделать следующее:

1. calculate the 4 lines of the quadrilateral (we'll call these quad lines)
2. calculate 4 lines, from the (xt, yt) to every other coordinate (we'll call these new lines)
3. if any new line intersects any of the quad lines, then the coordinate is outside of the quadrilateral, otherwise it is inside.

Answer 6

Решение, которое я использовал для решения этой проблемы, состояло в том, чтобы получить угол P (на диаграммах, размещенных ОП) для каждого из 4 треугольников, которые он образует с каждой стороны четырехугольника. Добавьте углы вместе. Если они равны (или почти равны, в зависимости от погрешности кода) 360, точка находится внутри четырехугольника. Если сумма меньше 360, точка находится за пределами. Однако это может работать только с выпуклыми четырехугольниками.

Answer 7

Предположим, A,B,C,D - вершины четырехугольника, а P - точка.Если P находится внутри четырехугольника, то все точечные произведения dot(BP,BA), dot(BP,BC), dot(AP,AB), dot(AP,AD), dot(DP,DC), dot(DP,DA), dot(CP,CB) и dot(CP,CD) будут положительными.Если P находится вне четырехугольника, то хотя бы один из этих продуктов будет отрицательным.