# Calculating and detecting curves

How can I detect the 'steepness' of a curve? For example, if the user swipes their finger across the screen in a curve, what's the best way of detecting whether the curve is almost a semi-circle, or whether it's straight?

Is it also possible to extend this to possibly recognise multiple curves (e.g. a sigmoidal shape)?

-

I suggest using an orientation histogram. First, collect sample points on your curve, ensuring they're far enough apart to be meaningful. Choose a minimum distance of 10 pixels, for instance.

Then iterate on point triplets [A,B,C] and compute the orientation change:

``````v1 = (B - A).normalize();
v2 = C - B;
f = atan2(-v2.x * v1.x -v2.y * v1.y,
v2.x * v1.y - v2.y * v1.x);
``````

Now `f` contains the orientation difference between `BC` and `AB`. The `atan2()` here is important to avoid any division by zero.

Now you can compare successive orientation changes like [Jesse Emond] suggested. However, computing a histogram will be more robust:

``````float histo[32];
memset(histo, 0, sizeof(histo));

/* ... */

histo[31 - (int)((M_PI - f) * (32.0 / 2.0 / M_PI))] += weight(A, B, C);
``````

(I use `M_PI - f` instead of `f + M_PI` because the `M_PI` value is inclusive and could lead to an integer overflow).

`float weight(A, B, C)` is a method that computes the weight of the stroke. A simple weight function would return the length of `AC`, but you could decide to give long strokes a smaller weight.

Finally, analyse the histogram. If you get most of the values around `histo[15]` and `histo[16]` it means the user did a straight line. If they are around `histo[13]` it means a large counterclockwise circle arc, `histo[18]` means a clockwise circle, `histo[11]` means a smaller circle, anything below `histo[8]` or above `histo[24]` means there was a brutal change in direction...

-
Is the value of `M_PI` just `Pi` (but truncated for efficiency)? – XSL Mar 9 '11 at 14:36
Yes, `M_PI` is how `<math.h>` or `<cmath>` define Pi. For some reason on Windows you need to `#define _USE_MATH_DEFINES` in order to make it available. Note that there is also `M_1_PI` that conveniently defines `1/Pi`. – sam hocevar Mar 9 '11 at 14:44
Cool, thanks a lot for your answer! – XSL Mar 9 '11 at 14:51

For the curve or straight line problem, I think I'd keep a list of the positions of old input. Then, I'd check the slope between every point (delta Y / delta X). If the slope does not change a lot, then it's probably a line. If it varies a lot, it's probably a curve. You could use a limit representing the slope difference that determines if the input is a line or a curve.

So, if I had to implement such a functionality, I think I'd go like this:

``````List<Vector2> inputPositions = new List<Vector2>();//the old input positions
``````

then I'd find the slopes between every position:

``````float deltaY = 0f;
float deltaX = 0f;
List<float> slopes = new List<float>();
for (int i = 0; i < inputPositions.Count - 1; ++i)//check all the positions except the last one
{
deltaY = inputPositions[i + 1].Y - inputPositions[i].Y;//next pos.Y - current.Y
deltaX = inputPositions[i + 1].X - inputPositions[i].X;//next pos.X - current.X

if (deltaX != 0.0f)//prevent division by 0
{
}
else
{
//I'm not really sure about using these values, but basically it
//means that the movement was vertical
slopes.Add(deltaY > 0.0f ? float.MaxValue : float.MinValue);
}
}
``````

then you can analyse the results to see if the slope difference was too huge.

``````bool IsLine(List<float> slopes)
{
const float IS_NOT_LINE_SLOPE_DIFF = 0.05f;//find an appropriate constant for your program

float slopeVariation = 0f;
for (int i = 0; i < slopes.Count - 1; ++i)//check all but the last element
{
slopeVariation = slopes[i] - slopes[i + 1];
if (Math.Abs(slopeVariation) >= IS_NOT_LINE_SLOPE_DIFF)
return false;
}

return true;
}
``````

You could even get the median of the slope variations to get a more general result.

Sure, this isn't the cleanest and certainly not the best way to solve your problem, but that's the way I would go to do it.

-
Be careful: slopes depend too much on the orientation. This will behave inconsistently with similar horizontal and vertical gestures. – sam hocevar Mar 9 '11 at 10:08