计算几何设定点算法的

我有以下问题运行时间为O（nlogn）来设计的算法：计算几何设定点算法的

鉴于n个点的集合P，确定的值A> 0，使得剪切变换（x，y）→（x + Ay，y）不会改变x坐标不等的点的顺序（在x方向上）。

即使搞清楚从哪里开始，我也有很多困难。

任何帮助，将不胜感激！

谢谢！

来源

2011-11-15 Shabu

另请参阅http：// stackoverflow。com/questions/5615964/shear-transformation-which-doesnt-change-the-order-in-x-direction –

我认为Y = 0

When x = 0, A > 0 
(x,y) -> (x+Ay,y) 
     -> (0+(A*0),0) = (0,0) 
When x = 1, A > 0 
(x,y) -> (x+Ay,y) 
     -> (1+(A*0),0) = (1,0)

不等的x坐标，（2,0），（3,0），（4,0）... 所以，我认为，开始点可能是（0,0），x = 0。

来源

2011-11-15 02:51:54 SuSanda

我认为你错误地解释了这个问题 - 这个想法是你给了（x，y）点并且需要选择A.你并不是从x和A开始，然后需要选择y。 – templatetypedef

假设所有的x，y坐标都是正数。（不失一般性，可以添加偏移量。）在时间O（n log n）中，对列表L中的点进行排序，主要按x坐标升序排列，其次按y坐标升序排列。在时间O（n）中，处理点对（按L顺序）如下。设p，q是L中的任意两个连续点，并设px，qx，py，qy表示它们的x和y坐标值。从那里你只需要考虑几个案例，它应该是显而易见的：如果px = qx，则什么也不做。否则，如果py < = qy，则什么也不做。否则（PX> QX，PY> QY）要求PX + A * PY < QX + A * QY，即（PX-QX）/（PY-QY）> A.

所以：通过L到达按顺序排列，并找到所有点对中满足的最大A'，其中px> qx和py> qy。然后选择A的值小于A'的值，例如A'/ 2。（或者，如果问题的目的是找到最大的这样的A，则只需报告A'值。）

来源

2011-11-15 02:57:26

好的，这里粗略地介绍了一种方法。

按x顺序对点列表进行排序。（这给出了O（nlogn） - 以下所有步骤都是O（n）。）

生成一个新的列表dx_i = x_（i + 1） - x_i，这是x坐标之间的差异。当x_i被排序时，所有这些dx_i> = 0。

现在对于一些A，变换的dx_i（A）将是x_（i + 1）-x_i + A *（y_（i + 1） - 义）。如果这是一个负值或零（x_（i + 1）（A）< x_i（A）

因此，对于每个dx_i，找到使得dx_i（A）为零，即 A_i = - （x_（i + 1） - x_i）/（y_（i + 1） - y_i）。您现在有一个系数列表，它会导致在一个连续的这个点不会改变顺序，一些A_i将是负的，如果你想要A> 0，则丢弃这些点（负数）。 A_I也会诱发顺序互换，所以A> 0的要求是有点任意的。）

找到最小A_I> 0在列表中。因此，任何一个有0 <一个< A_i（min）将是一个不会改变点的顺序的剪切。选择A_i（分钟），因为这将带来两个点到同一个X，但不会彼此经过。

来源

2011-11-15 03:11:32

计算几何设定点算法的

回答

相关问题