37
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ Do you know in advance what are your two end points? Or is determined at the moment the user stops touching the screen? \$\endgroup\$ – Alexandre Vaillancourt Apr 8 '15 at 14:17
  • \$\begingroup\$ Sorry if my description is not clear to you. Well, the starting point A(x,y) is the first touch and the ending point B(x,y) is when we released from touch screen as you said. \$\endgroup\$ – user3637362 Apr 8 '15 at 14:25
  • \$\begingroup\$ We have a related question on matching player-drawn letters. \$\endgroup\$ – Anko Apr 8 '15 at 21:31
  • 3
    \$\begingroup\$ Please don't post images for source code in the future. \$\endgroup\$ – Josh Apr 9 '15 at 16:24
  • 1
    \$\begingroup\$ @user3637362 I understand that you are starting j=1 so that you can compare touchList[j] with touchList[j-1], but when touch.phase == TouchPhase.Began or touch.phase == TouchPhase.Ended the positions are not added to touchList and subsequently not included in sumLength. This bug would be present in all cases but would be more apparent when the line has few segments. \$\endgroup\$ – Kelly Thomas Apr 9 '15 at 16:48
52
\$\begingroup\$

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:

enter image description here

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.

\$\endgroup\$
  • 34
    \$\begingroup\$ There is a small problem with this approach in that polylines of equal length are not equally 'straight'. A line that wobbles with low deviation (but many times) about the straight line is 'straighter' than a line of equal length that deviates out to a single point and then back. \$\endgroup\$ – Dancrumb Apr 8 '15 at 19:34
  • \$\begingroup\$ I can't +1 @Dancrumbs comment enough - that is a pretty key limitation with this method as if the user is drawing a straight line they will wobble a little bit so this feels like a common use case. \$\endgroup\$ – T. Kiley Apr 8 '15 at 20:53
  • \$\begingroup\$ @Dancrumb just factor in the average distance from the line, or factor in the "max distance" any point is from the line. Then you can weight the algorithm toward more wobbly lines with smaller deviation amplitudes, and away from lines that stray far from the expected path. \$\endgroup\$ – Superdoggy Apr 8 '15 at 22:16
  • 2
    \$\begingroup\$ @Dancrumb it sounds to me like this might end up a benefit for the OP's use-case. Hand-drawn lines will, of course, have small deviations. This approach might actually work to dampen the effect of these expected differences. \$\endgroup\$ – Thebluefish Apr 8 '15 at 22:59
  • 2
    \$\begingroup\$ @user3637362 you have a bug in your code. A possible explanation is that you forgot to account for the distance between the start-point and the first point or the end-point and the last point, but without looking at your code it is impossible to tell what your mistake could be. \$\endgroup\$ – Philipp Apr 9 '15 at 15:24
32
\$\begingroup\$

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.

drawing

(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.
\$\endgroup\$
  • \$\begingroup\$ Joel Bosveld's answer indicates an interesting case: an almost perfectly straight line with corners at the start and end. If the line shall be drawn freely by the user, this is indeed a problem. Nevertheless I think this method could cover that scenario. One could actually perform a fit with with RMSD or absolute Integral as an top-be-minimized value. Start values could be the start and end points. As the lenght does not matter it is also irelevant if the optimization moves the points so that the ideal line reaches out further or is shorter (the height has to be calculated to that niveau). \$\endgroup\$ – gr4nt3d Apr 9 '15 at 12:35
23
\$\begingroup\$

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 kincked. 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 (Dx(t),Dy(t)), where Dx(t) is the derivative of x at time t (this site appears to be missing TeX support). If the curve is not parameterized by arc-length, we normalize by dividing by ||(Dx(t),Dy(t))||. So we have a unit vector (or angle) of the tangent to the curve at time t. So, the angle is a(t)=(Dx(t),Dy(t))/||(Dx(t),Dy(t))||

We are then interested in ||Da(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, Da(t) becomes (a(t+h)-a(t))/h. And, a(t) becomes ((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||Da(t)||^2 for all datapoints 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 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.

\$\endgroup\$
  • 2
    \$\begingroup\$ This is the most sensible definition of straightness. \$\endgroup\$ – Marcks Thomas Apr 9 '15 at 11:39
  • 1
    \$\begingroup\$ This is by far the most sensible answer and I'm sure that the others would soom become very frustrating. Unfortunately, the form that the solution is presented in is a bit more obscure than the others, but I'd recommend the OP persists. \$\endgroup\$ – Dan Sheppard Apr 11 '15 at 11:38
  • \$\begingroup\$ Generally I also think this answer is indeed the best. Though a problem bothers me: What happens if the line is not "smooth enough"? E.g. if you have two perfectly straight line segments with an angle of, lets say, 90°. Am I mistaken or would this result in a pretty low result compared with a really smooth linear line? (I think Dancrumb's user case with a wobbly line was a similar problem) ... Locally this is sure the best way though. \$\endgroup\$ – gr4nt3d Apr 11 '15 at 12:40
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 5
    \$\begingroup\$ When you add up the distance between the ideal line and the point for every measured point, you need to account for the number of measures you took, otherwise when the user draws slower or use a device with a faster scan-rate they will register more points which means they will get a worse score. \$\endgroup\$ – Philipp Apr 8 '15 at 15:02
  • \$\begingroup\$ @Philipp Yes you do! I must admit your way of doing it seems better than mine :P \$\endgroup\$ – Alexandre Vaillancourt Apr 8 '15 at 15:03
  • \$\begingroup\$ I think this approach is improved by taking the average distance, rather than the cumulativeDistance. \$\endgroup\$ – Dancrumb Apr 8 '15 at 19:28
  • \$\begingroup\$ @Dancrumb Really, it depends on the needs, but yeah, that would be a way to do it. \$\endgroup\$ – Alexandre Vaillancourt Apr 8 '15 at 19:33
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

protected by MichaelHouse Apr 10 '15 at 16:00

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.