How can I quantify a drawn line's straightness?

Question

I'm working on a game which requires players to draw a line from a point A(x1,y1) to the other point B(x2,y2) on the screen of an Android device.

I want to find how well that drawing fits to a straight line. For instance, a result of 90% would mean the drawing almost perfectly fits the line. If players draw a curved line from A to B, it should get a low score.

The end points are not known in advance. How can I do this?

Answer 1

A perfectly straight line would also be the shortest possible line with a total length of sqrt((x1-x2)² + (y1-y2)²). A more scribbly line will be a less ideal connection and thus be inevitably longer.

When you take all individual points of the path the user drew and sum up the distances between them, you can compare the total length with the ideal length. The smaller the total length divided by the ideal length, the better the line.

Here is a visualization. When the black dots are the end-points of the gesture and the blue points are the points you measured during the gesture, you would calculate and add up the lengths of the green lines and divide it by the length of the red line:

A score or sinuosity index of 1 would be perfect, anything higher would be less perfect, anything below 1 would be a bug. When you prefer to have the score in percent, divide 100% by that number.

Answer 2

This might not be the best way to implement this either, but I suggest a RMSD (root mean square deviation) could be better, than merely the distance method, in cases mentioned by Dancrumb (see first two lines below).

RMSD = sqrt(mean(deviation^2))

Note:

• The sum of the absolute deviations (integral-like) might be better, as it does not average out positive errors with negative ones. ( =sum(abs(deviation)))
• You probably would have to search the shortest distance to the linear line if there is a way that creates shorter distances than dropping the perpendicular.

(Please excuse the low quality of my drawing)

As you see, you have to

1. find an orthogonal vector to your line (dot-product equals 0).
   If your line points towards (1, 3) you'd want (3, -1) (trough the origin each)
2. Measure the distances h from the ideal line to the user one, parallel to that vector.
3. Calculate the RMSD or sum of absolute differences.

Answer 3

Existing answers do not take into account that the end points are arbitrary (rather than given). Thus, when measuring the straightness of the curve, it does not make sense to use the end points (for example, to calculate expected length, angle, position). A simple example would be a straight line with both ends kinked. If we measure using the distance from the curve and the straight line between the end points this will be quite large, as the straight line we have drawn is offset from the straight line between the end points.

How do we tell how straight the curve is? Assuming that the curve is smooth enough, we want to know how much, on average, the tangent to the curve is changing. For a line, this would be zero (as the tangent is constant).

If we let the position at time t be \$(x(t),y(t))\$, then the tangent is \$(D_x(t),D_y(t))\$, where \$D_x(t)\$ is the derivative of x at time t.

If the curve is not parameterized by arc-length, we normalize by dividing by \$||(D_x(t),D_y(t))||\$.

So we have a unit vector (or angle) of the tangent to the curve at time t. So, the angle is \$a(t)=(D_x(t),D_y(t))/||(D_x(t),D_y(t))||\$

We are then interested in \$||D_a(t)||^2\$ integrated along the curve.

Given that we most likely have discrete data points rather than a curve, we must use finite differences to approximate the derivatives. So, \$D_a(t)\$ becomes \$\frac{a(t+h)-a(t)}{h}\$. And, \$a(t)\$ becomes $$\frac{(x(t+h)-x(t))/h,(y(t+h)-y(t))/h}{||((x(t+h)-x(t))/h,(y(t+h)-y(t))/h)||}$$

Then we then get S by summing up \$h||D_a(t)||^2\$ for all data points and possibly normalizing by the length of the curve. Most likely, we use \$h=1\$, but it really is just an arbitrary scale factor.

To reiterate, S will be zero for a line and larger the more it deviates from a line. To convert to the required format, use \$\frac{1}{1+S}\$. Given that the scale is somewhat arbitrary, it is possible to multiply S by some positive number (or transform it in some other way, e.g. use \$bS^c\$ instead of S) to adjust how straight certain curves are.

Answer 4

This is a grid based system, right? Find your own points for the line and calculate the slope of the line. Now, using that calculation, determine valid points that the line would pass through, given some margin of error off the exact value.

Through a short amount of trial-and-error testing, determine what good and bad amount of matching points would exist and set your game up using a scale for the same results from your testing.

i.e. A short line with almost horizontal slope may have 7 points that you could draw through. If you can consistently match 6 or more of the 7 that were determined to be part of the straight line, then that would be the highest score. Grading for length and accuracy should be part of the scoring.

Answer 5

A very easy and intuitive measure is the area between the best fitting straight line and the actual curve. Determining this is fairly straightforward:

1. Use a least-squares fit on all points (this prevents the end-kink problem mentioned by Joel Bosveld).
2. For all points on the curve, determine the distance to the line. This is also a standard problem. (linear algebra, base transform.)
3. Sum all distances.

Answer 6

The idea is to keep all the points the user touched, then evaluate and sum the distance between each of those points to the line formed when the user releases the screen.

Here is something to get you started in pseudo-code:

bool mIsRecording = false;
point[] mTouchedPoints = new point[];

function onTouch
  mIsRecording = true

functon update
  if mIsRecording
    mTouchedPoints.append(currentlyTouchedLocation)

function onRelease
  mIsRecording = false

  cumulativeDistance = 0

  line = makeLine( mTouchedPoints.first, mTouchedPoints.last )

  for each point in mTouchedPoints:
    cumulativeDistance = distanceOfPointToLine(point, line)

  mTouchedPoints = new point[]

What is cumulativeDistance could give you an idea on the fitting. A distance of 0 would mean the user was straight on the line all the time. Now you'd have to do some tests to see how it behaves in your context. And you might want to amplify the value returned by distanceOfPointToLine by squaring it to penalize more the large distances away from the line.

I'm not familiar with unity, but the code in update here may go in a onDrag function.

And you might want to add somewhere in there some code to prevent registering a point if it's the same as the last one registered. You don't want to register stuff when the user does not move.

Answer 7

One method you could use is to subdivide the line into segments and do a vector dot product between each vector that represents the segment and a vector representing a straight line between the first and last point. This has the benefit of letting you find extremely "spiky" segments easily.

Edit:

Also, I would consider using the length of the segment in addition to the dot product. A very short but orthogonal vector should count less than a long one that has less of a deviation.

Answer 8

The easiest and quickest might be simply to find out how thick the line would have to be to cover all the points of the user drawn line.

The thicker the line has to be, the worse the user did in drawing their line.

Answer 9

Somehow referring to MSalters Answer, here is some more specific information.

Use the least squares method to fit a line for your points. You are basically looking for a function y=f(x) which fits best. Once you have it you can use the actual y values to sum the square of differences:

s = sum over ( (y-f(x))^2 )

The smaller the sum, the straighter the line.

How to get the best approximation, is explained here: https://web.archive.org/web/20210506231850/http://math.mit.edu/~gs/linearalgebra/ila0403.pdf

Just read from "Fitting a straight line". Note that t is used instead of x and b instead of y. C and D is to be determined as approximation, then you have f(x) = C + Dx

Additional Note: Obviously, you also have to take the length of the line into account. Every line consisting of 2 Points will be perfect. I do not know the exact context, but I guess I would use the sum of squares divided by the number of points as rating. Also I would add the requirement of a minimal length, minimal number of points. (Maybe about 75% of the maximun length)