Преобразование сдвига, которое не меняет порядок в x-направлении

Question

Учитывая набор точек с неравными x-координатами, я хочу вычислить значение v> 0 так, чтобы преобразование сдвига (x, y) -> (x + v * y, y) не меняло порядок в направлении х.

Answer 1

Это не сложно. Упорядочить точки по их оси X. Из-за непрерывности преобразования сдвига вам достаточно найти максимум v, чтобы две последовательные точки (в x-порядке) не меняли порядок. Пусть (x, y) и (x ', y') будут двумя последовательными точками в вашем порядке. при v> 0 координаты x изменяются как x -> x + vy и x '-> x' + vy '. Теперь, когда x '> x, вы хотите найти максимум v такой, что x' + vy '> = x + vy. По линейности достаточно решить

x' + vy' = x + vy

т.е.

x' - x = vy - vy' = v(y - y')

* Таким образом, 1007 *

v = (x' - x)/(y - y')

Если результат отрицательный, то любое значение v исчезает (точки удаляются дальше); если результат положительный, это максимальное значение, которое может выдержать пара (x, y), (x ', y'). Теперь вычислите этот максимум для всех последовательных пар и возьмите их минимум.

Обратите внимание, что если y = y ', v становится неопределенным. В этом случае точки лежат в одной и той же точке на оси Y, и преобразование сдвига не меняет своего расстояния.

Answer 2

Конвертировать каждую точку (x, y) в луч {(x + yv, v) | v ≥ 0} в полуплоскости xv с v ≥ 0. Используйте алгоритм пересечения сегментов, чтобы найти алгоритм с минимальным v.