Shear transformation which doesn't change the order in x-direction

Given a set of points with unequal x-coordinates, I want to calculate the value v > 0 such that 开发者_运维技巧the shear transformation (x, y) -> (x + v*y, y) doesn't change the order in the x-direction.

This isn't difficult. Order the points by their x-axis. Because of the continuity of the shear transformation, it's enough for you to find a maximum v that two consecutive points (in x-order) do not change order. Let (x,y) and (x',y') be two consecutive points in your ordering. with v>0, the x coordinates change as x -> x + vy and x' -> x' + vy'. Now as x'>x, you want to find maximum v such that x' + vy' >= x + vy. By linearity, it's enough to solve

x' + vy' = x + vy

i.e.

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

thus

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

If the result is negative, then any value of v goes (the points are moving farther away); if the result is positive, that's the maximum value that the pair (x,y), (x',y') can tolerate. Now calculate this maximum for all consecutive pairs and take their minimum.

Note that if y = y', v becomes undefined. In this case the points lie at the same point on y-axis and the shear transformation doesn't change their distance.

Convert each point (x, y) into a ray {(x + yv, v) | v ≥ 0} in the xv-halfplane with v ≥ 0. Use a segment intersection algorithm to find the one with minimum v.