| 算法问题的一个基本方法（修改版） |
| 送交者: 高玉宝 2012年07月04日11:02:26 于 [灵机一动] 发送悄悄话 |
|
A polygon, either convex or concave. A point, in the same plane of the polygon, either inside or outside the polygon. From this point, find a direction which cuts most sides of the polygon. 先算出点与多边形各接点连线的角度，然后把多边形各接点根据其角度从小到大 排列，然后从最小的那接点开始，依次检查各接点。为了方便叙述，就称角度小 的一方位左方，角度大的一方为右方。 设x为点与所检查那接点的射线所经过的边线数，m为点的射线能经过的最多射线 数，d为点的射线能经过的最多射线数的那方向，即角度（也就是要找的答案）。 d的初始值为角度最小的接点角度。x和m的初始值根据左边第一接点的情况而定。 1。左边第一接点的两连线（每个接点有两连线）的另一端全在射线的右边，则设 x和m为2。 2。如全在射线的左边，则设x和m为0。 3。一端在左一端在右，则设x和m为1。 然后检查下面的各点（从第二接点开始），如 1。接点两线的另一端全在右边，则x加2。 2。全在左边，则x减2。x减2后，如x小于0，则使x为0。 3。一端在左一端在右，如x是0，则使x为1，否则x不变。 然后比较m和x。如x大于m，则使m=x，使d为这接点的角度。 这样每个点都检查下来后，d（稍偏右一点）就是所要的结果。 |
|
|
|
|
 |
 |
| 实用资讯 | |
