Параллелограмм содержит точку

Question

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

Answer 1

Привет еще раз и спасибо за все ваши ответы. Тем временем я сам придумал что-то, что, я думаю, было бы довольно быстрым:

Представьте, что у нас есть параллелограмм, который охватывает PQ и PR, где PQ и PR - векторы (P, Q и R - углы). Кроме того, у нас есть пункт, который мы хотим проверить, который называется A.

Мы знаем, что Vector PA можно разбить на два вектора, параллельных PQ и PR:

PA=n*PQ+m*PR

Теперь мы знаем, что n и m ДОЛЖНЫ быть в интервале [0; 1], мы решаем n и m:

n = -det(PA, PQ)/det(PQ, PR)
m = det(PA, PR)/det(PQ, PR)

Где det (PA, PQ) - определитель векторов PA и PQ:

det(PA, PQ) = PA.x*PQ.y-PQ.x*PA.y

Если точка A находится внутри параллелограмма, то 0 <= n <= 1 и 0 <= m <= 1, это дает нам псевдокод: </p>

var d:Number = det(PQ, PR);
if (0 <= -det(PA, PQ)/d <= 1 && 0 <= det(PA, PR)/d <= 1)
{
    //inside
}
else
{
    //outside
}

Answer 2

Представьте себе луч, исходящий из вашей точки в одном направлении. Если этот луч пересекает линии вашей фигуры нечетное количество раз, он находится внутри фигуры. Если оно проходит четное количество раз, оно выходит за пределы формы.

Итак, в вашей программе вы просто создаете невидимую линию и видите, как часто она пересекается. Я думаю, что Actionscript, вероятно, имеет встроенную функцию для этого.

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

Answer 3

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

РЕДАКТИРОВАТЬ: Поскольку владелец вопроса знаком с векторами, я в основном перепишу свой ответ на этом языке. Предположим, что параллелограмм охватывает векторы PQ и PR, где P, Q и R - углы. Символ * будет обозначать скалярное произведение. Выберите точку q так, чтобы PQ был перпендикулярен Pq (то есть Pq*PQ=0) и PR*Pq>0 (например, вы можете получить q, повернув Q вокруг P на 90 градусов) , Также выберите точку r, такую, что PR*Pr=0 и PQ*Pr>0. Тогда точка A находится внутри, если и только если (0 < Pr*PA < Pr*PQ) && (0 < Pq*PA < Pq*PR).

Answer 4

Эта статья описывает метод определения, где пересекаются луч и четырехугольник. Это может быть упрощено в дальнейшем, если четырехугольник является параллелограммом.

Если у вас есть параллелограмм со смежными сторонами, описанными векторами AB и AC . Любая точка на плоскости параллелограмма может быть описана следующим вектором

T(a, b) = A + a * AB + b * AC

Любой луч можно описать как начало координат O и направление D

R(t) = O + t * D

Пересечение 2 - это когда T(a, b) == R(t)

O + t * D = A + a * AB + b * AC

Решите это для a и b и убедитесь, что они оба находятся между 0 и 1. См. Псевдокод в конце статьи, чтобы узнать, как это реализовать.

Answer 5

1. Получите контур вашего многоугольника
2. Проверьте, лежит ли точка в округе

dist1 = cv2.pointPolygonTest(contours[0], (50, 70), True)

dist возвращает одно из следующих трех:

• Положительное значение, если точка находится внутри контура
• Отрицательное значение, если точка находится вне контура
• Ноль, если точка находится на контуре

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

Answer 6

Если параллелограмм является выпуклым (и с учетом определения параллелограмма он должен быть xD), то любой алгоритм для проверки, находится ли он в его границах, должен работать, вы можете повысить эффективность, развернув цикл, поскольку вы знаете, что есть только 4 вершины Например.

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

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

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

Answer 7

Стандартное уравнение линии задается как ax + bx + c = 0 .. но интересно, если вы возьмете это выражение ax + bx + c и оцените точки x, y, учитывая a, b, c для вашего В конкретной строке вы обнаружите, что выражение разбивает плоскость на две половины: одна половина, где выражение больше нуля, а другая половина, где она меньше.

Теперь, если вы берете четыре точки вашей параллелограммы и вычисляете коэффициенты a, b, c для каждой линии, составляющей сторону параллелограмма, вы можете оценить каждое выражение для рассматриваемой x, y и найти из какой стороны каждой линии эта точка находится. внутри параллелограмма будет логическим И отдельных сторон.

Т.е., когда у вас есть a, b, c для каждой из четырех строк, вы можете сделать тест что-то как

if ( ((a1*x+b1*y+c1)>0) && ((a2*x+b2*y+c2)<0) && 
        ((a3*x+b3*y+c3)<0) && ((a4*x+b4*y+c4)>0) {
    // it's in!
}

... единственная оставшаяся хитрость заключается в том, что вы должны определить «полярность» каждого теста знака, то есть больше или меньше нуля. Самый простой способ сделать это - оценить 0,0 и посмотреть, находится ли он на той стороне, которую вы хотите, что равносильно тому, что знак «с» говорит вам, какой способ проверки.

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

Answer 8

Мое первое наблюдение по поводу этой проблемы состоит в том, что прямоугольник (выровненный по осям) - это простой вырожденный случай. Если два угла этого прямоугольника: (x1, y1) и (x2, y2), то вы просто проверяете, учитывая точку (x3, y3), что min (x1, x2)

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

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

У меня нет времени на написание примера, но вычисление этих уклонов и пересечений - это алгебра первого года.

[Addenda]

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

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

Это может быть два решения: явно проверить наличие пересечений на границах отрезка (угол / вершина) или обработать каждый отрезок как ограниченный на одном конце с помощью (точка + эпсилон) (так что наши вычисления не найдут никакой точки) общего между любыми двумя сторонами).

Моя идея найти ограничивающий прямоугольник все еще является полезным быстрым тестом и распространяется в основном на все многоугольники. Мы находим min () и max () x, чтобы найти левую и правую граничные стороны, и min () и и max () y, чтобы найти нижнюю и верхнюю границы. Это также может быть расширено до трех измерений ... и мой друг говорит, что стандартные графические библиотеки широко используют это для обнаружения столкновений в большинстве виртуальных реальностей, MMORPG и т. Д. Когда находят столкновения в ограничивающих прямоугольниках, они выполняют более детальные вычисления. на многоугольниках, которые там содержатся.

Answer 9

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

Edit:

Учитывая четыре координаты верхнего левого, верхнего правого, нижнего правого и нижнего левого углов:

if (y >= y1 && y <= y3) {
   var k = (x4 - x1) / (y4 - y1);
   var m = x1 - k * y1;
   if (x >= k * y + m) {
     k = (x3 - x2) / (y3 - y2);
     m = x2 - k * y2;
     if (x <= k * y + m) {
       // inside
     }
   }
}