Точка в прямоугольнике

Question

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

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

Может быть, картина поможет объяснить:
A, B, C, а также длина стороны A / B. В основном я думал, что если CD меньше, чем половина стороны A, а D находится на AB, точка находится в прямоугольнике. Но как мне это сделать?
Другая мысль: Вместо того, чтобы найти D, чтобы увидеть, находится ли он на AB, проверьте, острые ли углы ABC и BAC, но я все еще не знаю, как это сделать.

Answer 1

Следующий метод довольно прост, но требует найти 1 векторную длину (вы можете кэшировать ее для нескольких проверок)

1. Вектор вычисления AB = B - A

2. Calc Длина AB - это будет ширина прямоугольника

3. Если AB_length (допустимое отклонение - небольшое значение, например, TOLERANCE = 0.00000001), тогда прямоугольник имеет нулевую ширину, поэтому точка не может лежать в прямоугольнике

4. Нормализовать AB: AB_normalized= AB / AB_length

5. Вычисление проекций оси

   Вычисление AB проекции:

   AB_proj = точка продукта (AB_normalized, C -A)

   Calc AB ортогональная проекция (обозначается на вашей картинке "CD"):

   AB_orthogonal = (-AB.y, AB.x)

   AB_orthogonal_proj = точечное произведение (AB_orthogonal, C - A)

6. Если (0 <= AB_proj <= AB_length) и (ABS(AB_orthogonal_proj) <= AB_height / 2) </strong>, тогда точка лежит в прямоугольнике, иначе не лежит

Answer 2

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

1. Является ли проекция AC на AB внутри AB?
2. Есть | DC | <высота / 2? </li>

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

Answer 3

Идея с острым треугольником ABC не работает.Например, точка C находится непосредственно рядом с линией AB, угол в C станет почти 180 °.С другой стороны, угол в B может быть очень маленьким, если высота прямоугольника довольно мала, но C тогда лежит за пределами прямоугольника.

Тем не менее, ваш другой подход является одним из основных способов реализации этого.

Точка D находится где-то на линии через A и B, таким образом,

D = A + t * (B-A)

(заглавные буквы обозначают векторы в пространстве, строчные буквы - цифры).В то же время соединение от D до C перпендикулярно соединению A к B и, таким образом,

(C-D) . (B-A) == 0

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

(C-A-t*(B-A)) . (B-A) = (C-A) . (B-A) - t * (B-A) . (B-A) == 0

или при решении для t:

t = (C-A).(B-A) / (B-A).(B-A)

(или, другими словами, относительная длина проекции вектора AC на линиюAB).

Точка D находится внутри прямоугольника, если 0 <= t <= 1, и, таким образом, это ваше первое условие.

После этого вы можете вычислить расстояние от C доD (просто вставьте t в самое первое выражение, чтобы получить D) и сравните это с h/2, то есть последнее условие будет

(C-D).(C-D) <= (h/2)^2

Answer 4

Не совсем уверен, что это самый быстрый, но это, вероятно, сработает:

Вместо того, чтобы помещать половину D между двумя центрами, спроецируйте C как D вдоль оси AB.Затем убедитесь, что a) D находится между A и B и b) CD меньше или равен половине высоты прямоугольника.

---

По вашей идее об использовании углов ... с использованием Pythagorus и / или AlТеорема Каши может на самом деле иметь смысл:

http://en.wikipedia.org/wiki/Law_of_cosines

ABC острый и BAC острый оба будут предварительным условием, и, учитывая их, вы помещаете C2 в прямоугольник с той же альфа / бета (см. вики-страницу).Оттуда вы также знаете гамму (pi / 2, так как на прямоугольнике) и бета / альфа (pi / 2 - бета), что вызывает вопрос о том, меньше ли расстояние [A,C] или [B,C] или равно расстоянию [A,C2] или [B,C2] соответственно.

Answer 5

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

Это быстрее, чем проекция? Я думаю, это зависит от вероятности того, что вы будете тривиально отклонены после вашего первого шага!