确定一组点是否形成一条近似直线

Question

我正在做一个line/arc检测算法。我发现了这组讨厌的点：

[(215, 69), (217, 70), (220, 67), (223, 65), (226, 64), (229, 62), (232, 60), (236 , 57), (239, 56), (242, 54), (245, 52), (248, 50), (251, 48), (254, 47), (257, 45), (260, 43 ), (264, 40), (267, 39), (270, 37), (273, 35), (276, 33), (279, 31), (282, 29), (285, 28), (288, 26), (291, 24)]

我需要确定这些是直线还是曲线。我绘制了 set ，它看起来像这样： Set of green points on a line

他们清楚地代表了一条线。

但是，我尝试了各种测试来确定它们是直线还是曲线。

我测试了每个点之间的角度是否近似相等。但是，由于线条有点曲折，所以有一些异常点不等于

我测试了直线的任意 3 个连续点的叉积以检查它们是否共线

for k in range(0,len(pts-3),1):
cp1=pts[k]
cp2=pts[k+1]
cp3=pts[k+2]
c1,c2,c3= (cp1.x,cp1.y),(cp2.x,cp2.y),(cp3.x,cp3.y)
cros= (p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y)
print(abs(cros))

其中一些具有非常重要的交叉产品。再次因为这条线是我认为的锯齿形线。

这种锯齿状的结构使我的算法失效！那么如何判断锯齿状的锯齿线是直线还是曲线呢？

Answer 1

假设点是根据与线末端的接近程度排序的，我们可以将每条线的梯度与其相邻点进行比较，以确定它们是否位于一条线上。渐变的好处是我们可以指定一个公差级别来定义一条线是否太偏离而不能被视为线的一部分。

JS 中给定点的示例是一个多维数组：

function calculateIsLine() {
let startingGradient=getGradientFromPoint(0);//we get a baseline and compare to every other point. If it is for example, inverted or completely off,
//we can confirm it doesn't line up.

console.log("Starting Gradient: "+startingGradient);

for (let i = 0; i < points.length-1; i++) {//ignoring last point as no point after it.
    if(Math.abs(startingGradient-getGradientFromPoint(i))>0.5){//0.5 is our tolerance level
        console.log("Conflicting Point: "+points[i]+" "+getGradientFromPoint(i));

        return false;
    }

}
return true;

}
function getGradientFromPoint(offset){
    return (points[offset+1][1]-points[offset][1])/(points[offset+1][0]-points[offset][0]);//gradient formula

}

工作代码段

let points = [];
let pointsString = "[(215, 69), (217, 70), (220, 67), (223, 65), (226, 64), (229, 62), (300, 60), (236, 57), (239, 56), (242, 54), (245, 52), (248, 50), (251, 48), (254, 47), (257, 45), (260, 43), (264, 40), (267, 39), (270, 37), (273, 35), (276, 33), (279, 31), (282, 29), (285, 28), (288, 26), (291, 24)]";

let conflictingPointIndex;

function setup() {
  let canvas = createCanvas(500, 100);
  let arrayPoints = pointsString.split("(");

  arrayPoints.splice(0, 1);

  for (let i = 0; i < arrayPoints.length; i++) {
    arrayPoints[i] = arrayPoints[i].substr(0, arrayPoints[i].indexOf(")")).replace(" ", "");
    let stringPoint = arrayPoints[i].split(",");
    for (let j = 0; j < 2; j++) {
      if (!points[i])
        points[i] = [];
      points[i][j] = parseInt(stringPoint[j]);

    }
  }
  points.sort((p1, p2) => {
    return p1[0] - p2[0];

  });
 // console.log(points);


}
function draw() {
  background(0);
  console.log(calculateIsLine());
  for (let i = 0; i < points.length; i++) {
    if (i === conflictingPointIndex + 1)
      stroke(255, 0, 0);
    else stroke(255);
    point(points[i][0], points[i][1]);
  }
  noLoop();

}

function calculateIsLine() {
  let startingGradient = getGradientFromPoint(0); //we get a baseline and compare to every other point. If it is for example, inverted or completely off,
  //we can confirm it doesn't line up.
  console.log("Starting Gradient: " + startingGradient);
  for (let i = 0; i < points.length - 1; i++) { //ignoring last point as no point after it.
    if (Math.abs(startingGradient - getGradientFromPoint(i)) > 1.6) { //0.5 is our tolerance level
      console.log("Conflicting Point: " + points[i] + " " + getGradientFromPoint(i) + " " + Math.abs(startingGradient - getGradientFromPoint(i)));
      conflictingPointIndex = i;
      return false;
    }

  }
  return true;

}

function getGradientFromPoint(offset) {
  return (points[offset + 1][1] - points[offset][1]) / (points[offset + 1][0] - points[offset][0]); //gradient formula

}

<script src="https://github.com/processing/p5.js/releases/download/0.6.1/p5.js"></script>

我想不出用于曲线的方法。但希望您能够想到与此类似的方法。其他人也可能有关于曲线的解决方案。

确定一组点是否形成一条近似直线

determine if a set of points form an approximate line

curve

line

zigzag