当前位置: 代码迷 >> 数据结构与算法 >> 化除斜率相同的点
  详细解决方案

化除斜率相同的点

热度:9624   发布时间:2013-02-26 00:00:00.0
消除斜率相同的点
一个由100个点组成的数租,存了多变型上的每一个点,这个多边形是一个矩形,怎么简化成5个点保存这个矩形?
不知道我描述清楚了没有。

------解决方案--------------------------------------------------------
一般情况下做一下凸包就出来了。
------解决方案--------------------------------------------------------
令多边形各点是 p1,p2,...,pn,每个 pi=(xi,yi);
STEP1: 在 p1,p2,...pn 中寻找这样的 pi,它与 pi-1 和 pi+1到 pi 的斜率一样;
STEP2: 如果没有这样的点,算法结束;
STEP3: 如果有,删除它,然后转 STEP1.
------解决方案--------------------------------------------------------
角点的斜率远远大于其他点的斜率
你设置一个阈值(试几下,确定一个大概的),超出阈值就认为拐了一个直角弯,记录拐弯处的x,y以及拐的次数即可。
  相关解决方案