在某些点之间搜索并找到重要点的方法

Question

我有一些点，它们是有序的，由用户绘制。

我想在这些观点之间找到重要的观点。重要的一点，正如我所定义的，是我们在点的方向上突然改变的一点。例如，手工绘制的"Z"必须有2个重要点。

我试着计算相邻点之间的角度，但这并没有给我想要的结果。计算斜率的变化是一样的。

也许我需要以某种方式优化角度查找，但我不知道。知道吗？

编辑：这里是比较角度的Java代码：

int nBreakPoints = 0;
double nextangle = 0;
double nextr;
double r = Math.sqrt(Math.pow(points[1].x-points[0].x, 2) 
    + Math.pow(points[1].y-points[0].y, 2));
double angle = Math.asin((points[1].y-points[0].y) / r)*180/Math.PI; 
double cumR = r;
int firstI = 0;
for(int i=1; i<points.length-2 ;i++)
{
    nextr = (int) Math.sqrt(Math.pow(points[i].x-points[i+1].x, 2) 
        + Math.pow(points[i+1].y-points[i].y, 2));
    cumR += nextr;
    if(cumR < 20 || cumR==0) continue;
    nextangle = Math.asin((points[i].y-points[firstI].y) / cumR)*180/Math.PI;
    if(Math.abs(angle-nextangle) >= 20) nBreakPoints++;
    r = nextr;
    angle = nextangle;
    cumR = 0;
    firstI = i;
}

好的，它只是计算两点之间的角度，如果它们不同于20度，我们就有了一个新的重要点。

需要注意的是，添加cumR和firstI是为了防止将"太近"的点带入计算。

Answer 1

如果角度翻转360°，您的角度计算可能会失败。例如，一个角度是179°，下一个角度为-179°。绝对差异很大，但角度非常接近。

这里有一个更稳健的方法：

pp = points[i - 1] //the preceding point; if it exists
p = points[i]
pn = points[i + 1] //the next point; if it exists
dp = [p.x - pp.x, p.y - pp.y] //direction of incoming line
dn = [pn.x - p.x, pn.y - p.y] //direction of outgoing line
r = Math.sqrt((dp.x * dp.x + dp.y * dp.y) * (dn.x * dn.x + dn.y * dn.y)) //product of vector lengths
cos = (dp.x * dn.x + dp.y * dn.y) / r //cosine of angle
angle = Math.acos(cos) * 180 / Math.PI;
if(angle > 20)
    ...

如果这些点彼此非常接近并且受到噪声的影响，那么考虑更宽的范围而不是相邻点可能是合理的：

pp = points[i - n]
p = points[i]
pn = points[i + n]

n可以是一个常数，您可以根据应用程序进行选择。你也可以寻找与当前点有一定距离的下一个点：

for(int j = i - 1; j >= 0; --j)
{
    dp = [p.x - points[j].x, p.y - points[j].y]
    rp = dp.x * dp.x + dp.y * dp.y;
    if(rp > square_threshold)
        break;
}

下一点也是如此。