Возникла небольшая задачка: на плоскости заданы точка и прямоугольник. Требуется определить, попадает ли точка в прямоугольник.
Ни для кого не секрет, что задача эта решена на сто рядов самыми различными способами, поэтому вряд ли я предложу что-то новое. Но сам подход мне показался любопытным.
Итак. Когда говорят, что заданы точка и прямоугольник, обычно имеют в виду, что на плоскости есть система координат, в которой известны координаты точки и координаты вершин прямоугольника:
Точка A имеет координаты: (x, y)
Вершины прямоугольника P имеют координаты:
(x1, y1)
(x2, y2)
(x3, y3)
(x4, y4)
А дальше начинается небольшая хитрость. Если присмотреться, то две смежные стороны прямоугольника P можно выбрать в качестве новой системы координат O'X'Y'. В ней прямоугольник превратится в единичный квадрат, а принадлежность точки единичному квадрату проверить легко.
Осталось только выписать формулы перехода от системы координат OXY к системе координат O'X'Y'. Для этого возьмём формулы перехода O'X'Y' →OXY и обратим их.
Это сделать легко. Действительно, если некая точка имеет в системе координат O'X'Y' координаты (x', y'), то в системе координат OXY она будет иметь координаты:
x = (x3 − x2) ∙ x' + (x1 − x2) ∙ y' + x2
y = (y3 − y2) ∙ x' + (y1 − y2) ∙ y' + y2
Выражая координаты (x', y') через координаты (x, y) получим:
x' = [ (y1 − y2) ∙ (x − x2) − (x1 − x2) ∙ (y − y2) ] / d
y' = [ −(y3 − y2) ∙ (x − x2) + (x3 − x2) ∙ (y − y2) ] / d
где
d = (x3 − x2) ∙ (y1 − y2) − (x1 − x2) ∙ (y3 − y2)
Тут надо отметить небольшую особенность. Мы специально выбрали перечисление вершин прямоугольника против часовой стрелки - чтобы величина d была неотрицательной.
Получили следующий простой критерий. Точка A попадает в прямоугольник P, если выполнены неравенства:
0 ≤ x' ≤ 1
0 ≤ y' ≤ 1
Или, после несложных преобразований:
0 ≤ (y1 − y2) ∙ (x − x2) − (x1 − x2) ∙ (y − y2) ≤ d
0 ≤ (x3 − x2) ∙ (y − y2) − (y3 − y2) ∙ (x − x2) ≤ d
Больше того, этот подход позволяет обобщить эту формулу не только на прямоугольники, но и на параллелограммы. А также выписать критерий для треугольника, если заметить, что треугольник (x1, y1)-(x2, y2)-(x3, y3) в системе координат O'X'Y' имеет вид (0,1)-(0,0)-(1,0):
0 ≤ x'
0 ≤ y'
x' + y' ≤ 1
Или, после несложных преобразований:
0 ≤ (y1 − y2) ∙ (x − x2) − (x1 − x2) ∙ (y − y2)
0 ≤ (x3 − x2) ∙ (y − y2) − (y3 − y2) ∙ (x − x2)
(y1 − y3) ∙ (x − x2) − (x1 − x3) ∙ (y − y2) ≤ d
Таким образом, аффинное преобразование координат позволило решить сразу целый класс однотипных задач.
