linecurvezigzag

determine if a set of points form an approximate line

I am making a line/arc detection algorithm. I found this pesky set of points :

[(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)]

I need to determine if these form a line or a curve. I plotted the set , it looks like this: Set of green points on a line

They clearly represent a line.

However, I tried all sorts of tests to determine if they are line or curve.

  1. I tested whether the angles between each of the points are approximately equal. However, because the line a bit zig zagged, there are some outlier points that are not equal

  2. I tested the cross product of any 3 sequential point of the line to check if they are collinear

    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))

Some of them have really significant cross products. Again because the line is a zig zagged line me thinks.

This zig zagged ness is throwing my algorithm off! So how do I determine if a zigged zagged line is a line or a curve?

Solution

  • Assuming points are sorted based on proximity to the end of the line, we could compare gradients of each line with their neighbor in order to determine whether they sit on a line. The good thing about the gradient is how we can specify a tolerance level to define whether a line is too off to be considered part of the line.

    An Example in JS given points is a multi dimensional array:

    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

}

    Working Snippet

    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>

    I wasn't able to think of an approach to use for curves. But hopefully, you may be able to think of an approach similar to this. Someone else may also have a solution regarding curves.