算法问题的一个基本方法 |
送交者: 高玉宝 2012年07月03日06:25:57 于 [灵机一动] 发送悄悄话 |
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为0,m为-10 如接点两线的另一端全在后面,则x加2,全在前面则x减2。然后比较m和x,如x大于m,则使m=x,记下这个角度d(即方向)。这样每个点都检查下来后,d就是所要的结果。 |
|
|
|
实用资讯 | |