Срязваща трансформация, която не променя реда в посока x - алгоритъм, изчислителна геометрия

Като се има предвид набор от точки с неравномерни координати x, искам да изчисля стойността v> 0 така, че трансформацията на срязване (x, y) -> (x + v * y, y) да не променя реда в x -посока.

Отговори:

Това не е трудно. Поръчайте точките по тяхната ос. Поради непрекъснатостта на срязващата трансформация е достатъчно да откриете максимален V, че две последователни точки (в x-ред) не променят реда. Нека (x, y) и (x ", y") две последователни точки в поръчката ви с v> 0, координатите x се променят като x -> x + vy и x "-> x" + vy ". Сега като x "> x, вие искате да намерите максимално v, така че x" + vy "> = x + из.Чрез линейност, това е достатъчно, за да реши

x" + vy" = x + vy

т.е.

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

по този начин

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

Ако резултатът е отрицателен, тогава всяка стойност на vотива (точките се движат по-далеч); ако резултатът е положителен, това е максималната стойност, която двойката (x, y), (x ", y") може да понесе. Сега изчислете този максимум за всички последователни двойки и вземете минимума от тях.

Забележете, че ако y = y ", v става недефинирана. В този случай точките се намират в една и съща точка на y-ос, а трансформацията на срязване не променя тяхното разстояние.

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