File: Core\CSharp\MS\Internal\Ink\CuspData.cs
Project: wpf\src\PresentationCore.csproj (PresentationCore)
//-----------------------------------------------------------------------
// <copyright file="CuspData.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// </copyright>
//-----------------------------------------------------------------------
 
using System;
using System.Diagnostics;
using System.Windows;
using System.Windows.Media;
using System.Windows.Ink;
using System.Windows.Input;
using System.Collections.Generic;
using MS.Internal.Ink.InkSerializedFormat;
 
namespace MS.Internal.Ink
{
    internal class CuspData
    {
        /// <summary>
        /// Default constructor
        /// </summary>
        internal CuspData()
        {
        }
 
        /// <summary>
        /// Constructs internal data structure from points for doing operations like
        /// cusp detection or tangent computation
        /// </summary>
        /// <param name="stylusPoints">Points to be analyzed</param>
        /// <param name="rSpan">Distance between two consecutive distinct points</param>
        internal void Analyze(StylusPointCollection stylusPoints, double rSpan)
        {
            // If the count is less than 1, return
            if ((null == stylusPoints) || (stylusPoints.Count == 0))
                return;
 
            _points = new List<CDataPoint>(stylusPoints.Count);
            _nodes = new List<double>(stylusPoints.Count);
 
            // Construct the lists of data points and nodes
            _nodes.Add(0);
            CDataPoint cdp0 = new CDataPoint();
            cdp0.Index = 0;
            //convert from Avalon to Himetric
            Point point = (Point)stylusPoints[0];
            point.X *= StrokeCollectionSerializer.AvalonToHimetricMultiplier;
            point.Y *= StrokeCollectionSerializer.AvalonToHimetricMultiplier;
            cdp0.Point = point;
            _points.Add(cdp0);
 
            //drop duplicates
            int index = 0;
            for (int i = 1; i < stylusPoints.Count; i++)
            {
                if (!DoubleUtil.AreClose(stylusPoints[i].X, stylusPoints[i - 1].X) ||
                    !DoubleUtil.AreClose(stylusPoints[i].Y, stylusPoints[i - 1].Y))
                {
                    //this is a unique point, add it
                    index++;
 
                    CDataPoint cdp = new CDataPoint();
                    cdp.Index = index;
 
                    //convert from Avalon to Himetric
                    Point point2 = (Point)stylusPoints[i];
                    point2.X *= StrokeCollectionSerializer.AvalonToHimetricMultiplier;
                    point2.Y *= StrokeCollectionSerializer.AvalonToHimetricMultiplier;
                    cdp.Point = point2;
 
                    _points.Insert(index, cdp);
                    _nodes.Insert(index, _nodes[index - 1] + (XY(index) - XY(index - 1)).Length);
                }
            }
 
            SetLinks(rSpan);
        }
 
        /// <summary>
        /// Set links amongst the points for tangent computation
        /// </summary>
        /// <param name="rError">Shortest distance between two distinct points</param>
        internal void SetTanLinks(double rError)
        {
            int count = Count;
 
            if (rError < 1.0)
                rError = 1.0f;
 
            for (int i = 0; i < count; ++i)
            {
                // Find a StylusPoint at distance-_span forward
                for (int j = i + 1; j < count; j++)
                {
                    if (_nodes[j] - _nodes[i] >= rError)
                    {
                        CDataPoint cdp = _points[i];
                        cdp.TanNext = j;
                        _points[i] = cdp;
 
                        CDataPoint cdp2 = _points[j];
                        cdp2.TanPrev = i;
                        _points[j] = cdp2;
                        break;
                    }
                }
 
                if (0 > _points[i].TanPrev)
                {
                    for (int j = i - 1; 0 <= j; --j)
                    {
                        if (_nodes[i] - _nodes[j] >= rError)
                        {
                            CDataPoint cdp = _points[i];
                            cdp.TanPrev = j;
                            _points[i] = cdp;
                            break;
                        }
                    }
                }
 
                if (0 > _points[i].TanNext)
                {
                    CDataPoint cdp = _points[i];
                    cdp.TanNext = count - 1;
                    _points[i] = cdp;
                }
 
                if (0 > _points[i].TanPrev)
                {
                    CDataPoint cdp = _points[i];
                    cdp.TanPrev = 0;
                    _points[i] = cdp;
                }
            }
        }
 
        
 
 
        /// <summary>
        /// Return the Index of the next cusp or the 
        /// Index of the last StylusPoint if no cusp was found
        /// </summary>
        /// <param name="iCurrent">Current StylusPoint Index</param>
        /// <returns>Index into CuspData object for the next cusp </returns>
        internal int GetNextCusp(int iCurrent)
        {
            int last = Count - 1;
 
            if (iCurrent < 0)
                return 0;
 
            if (iCurrent >= last)
                return last;
 
            // Perform a binary search
            int s = 0, e = _cusps.Count;
            int m = (s + e) / 2;
 
            while (s < m)
            {
                if (_cusps[m] <= iCurrent)
                    s = m;
                else
                    e = m;
 
                m = (s + e) / 2;
            }
 
            return _cusps[m + 1];
        }
 
        /// <summary>
        /// Point at Index i into the cusp data structure
        /// </summary>
        /// <param name="i">Index</param>
        /// <returns>StylusPoint</returns>
        /// <remarks>The Index is within the bounds</remarks>
        internal Vector XY(int i)
        {
            return new Vector(_points[i].Point.X, _points[i].Point.Y);
        }
 
 
        /// <summary>
        /// Number of points in the internal data structure
        /// </summary>
        internal int Count
        {
            get { return _points.Count; }
        }
 
 
        /// <summary>
        /// Returns the chord length of the i-th StylusPoint from start of the stroke
        /// </summary>
        /// <param name="i">StylusPoint Index</param>
        /// <returns>distance</returns>
        /// <remarks>The Index is within the bounds</remarks>
        internal double Node(int i)
        {
            return _nodes[i];
        }
 
 
        /// <summary>
        /// Returns the Index into original points given an Index into cusp data
        /// </summary>
        /// <param name="nodeIndex">Cusp data Index</param>
        /// <returns>Original StylusPoint Index</returns>
        internal int GetPointIndex(int nodeIndex)
        {
            return _points[nodeIndex].Index;
        }
 
 
        /// <summary>
        /// Distance
        /// </summary>
        /// <returns>distance</returns>
        internal double Distance()
        {
            return _dist;
        }
 
 
        /// <summary>
        /// Finds the approximante tangent at a given StylusPoint
        /// </summary>
        /// <param name="ptT">Tangent vector</param>
        /// <param name="nAt">Index at which the tangent is calculated</param>
        /// <param name="nPrevCusp">Index of the previous cusp</param>
        /// <param name="nNextCusp">Index of the next cusp</param>
        /// <param name="bReverse">Forward or reverse tangent</param>
        /// <param name="bIsCusp">Whether the current idex is a cusp StylusPoint</param>
        /// <returns>Return whether the tangent computation succeeded</returns>
        internal bool Tangent(ref Vector ptT, int nAt, int nPrevCusp, int nNextCusp, bool bReverse, bool bIsCusp)
        {
            // Tangent is computed as the unit vector along 
            // PT = (P1 - P0) + (P2 - P0) + (P3 - P0)
            // => PT = P1 + P2 + P3 - 3 * P0
            int i_1, i_2, i_3;
 
            if (bIsCusp)
            {
                if (bReverse)
                {
                    i_1 = _points[nAt].TanPrev;
                    if (i_1 < nPrevCusp || (0 > i_1))
                    {
                        i_2 = nPrevCusp;
                        i_1 = (i_2 + nAt) / 2;
                    }
                    else
                    {
                        i_2 = _points[i_1].TanPrev;
                        if (i_2 < nPrevCusp)
                            i_2 = nPrevCusp;
                    }
                }
                else
                {
                    i_1 = _points[nAt].TanNext;
                    if (i_1 > nNextCusp || (0 > i_1))
                    {
                        i_2 = nNextCusp;
                        i_1 = (i_2 + nAt) / 2;
                    }
                    else
                    {
                        i_2 = _points[i_1].TanNext;
                        if (i_2 > nNextCusp)
                            i_2 = nNextCusp;
                    }
                }
                ptT = XY(i_1) + 0.5 * XY(i_2) - 1.5 * XY(nAt);
            }
            else
            {
                Debug.Assert(bReverse);
                i_1 = nAt;
                i_2 = _points[nAt].TanPrev;
                if (i_2 < nPrevCusp)
                {
                    i_3 = nPrevCusp;
                    i_2 = (i_3 + i_1) / 2;
                }
                else
                {
                    i_3 = _points[i_2].TanPrev;
                    if (i_3 < nPrevCusp)
                        i_3 = nPrevCusp;
                }
 
                nAt = _points[nAt].TanNext;
                if (nAt > nNextCusp)
                    nAt = nNextCusp;
 
                ptT = XY(i_1) + XY(i_2) + 0.5 * XY(i_3) - 2.5 * XY(nAt);
            }
 
            if (DoubleUtil.IsZero(ptT.LengthSquared))
            {
                return false;
            }
 
            ptT.Normalize();
            return true;
        }
 
        /// <summary>
        /// This "curvature" is not the theoretical curvature.  it is a number between
        /// 0 and 2 that is defined as 1 - cos(angle between segments) at this StylusPoint.
        /// </summary>
        /// <param name="iPrev">Previous data StylusPoint Index</param>
        /// <param name="iCurrent">Current data StylusPoint Index </param>
        /// <param name="iNext">Next data StylusPoint Index</param>
        /// <returns>"Curvature"</returns>
        private double GetCurvature(int iPrev, int iCurrent, int iNext)
        {
            Vector V = XY(iCurrent) - XY(iPrev);
            Vector W = XY(iNext) - XY(iCurrent);
            double r = V.Length * W.Length;
 
            if (DoubleUtil.IsZero(r))
                return 0;
 
            return 1 - (V * W) / r;
        }
 
 
        /// <summary>
        /// Find all cusps for the stroke
        /// </summary>
        private void FindAllCusps()
        {
            // Clear the existing cusp indices
            _cusps.Clear();
 
            // There is nothing to find out from
            if (1 > this.Count)
                return;
 
            // First StylusPoint is always a cusp
            _cusps.Add(0);
 
            int iPrev = 0, iNext = 0, iCuspPrev = 0;
 
            // Find the next StylusPoint for Index 0
            // The following check will cover coincident points, stroke with 
            // less than 3 points
            if (!FindNextAndPrev(0, iCuspPrev, ref iPrev, ref iNext))
            {
                // Point count is zero, thus, there can't be any cusps
                if (0 == this.Count)
                    _cusps.Clear();
                else if (1 < this.Count) // Last StylusPoint is always a cusp
                    _cusps.Add(iNext);
 
                return;
            }
 
            // Start the algorithm with the next StylusPoint
            int iPoint = iNext;
            double rCurv = 0;
 
            // Check all the points on the chord of the stroke
            while (FindNextAndPrev(iPoint, iCuspPrev, ref iPrev, ref iNext))
            {
                // Find the curvature at iPoint
                rCurv = GetCurvature(iPrev, iPoint, iNext);
 
                /*
                    We'll look at every StylusPoint where rPrevCurv is a local maximum, and the 
                    curvature is more than the noise threashold.  If we're near the beginning
                    of the stroke then we'll ignore it and carry on.  If we're near the end 
                    then we'll skip to the end.  Otherwise, we'll flag it as a cusp if it 
                    deviates is significantly from the curvature at nearby points, forward
                    and backward
                */
                if (0.80 < rCurv)
                {
                    double rMaxCurv = rCurv;
                    int iMaxCurv = iPoint;
                    int m = 0, k = 0;
 
                    if (!FindNextAndPrev(iNext, iCuspPrev, ref k, ref m))
                    {
                        // End of the stroke has been reached
                        break;
                    }
 
                    for (int i = iPrev + 1; (i <= m) && FindNextAndPrev(i, iCuspPrev, ref iPrev, ref iNext); ++i)
                    {
                        rCurv = GetCurvature(iPrev, i, iNext);
                        if (rCurv > rMaxCurv)
                        {
                            rMaxCurv = rCurv;
                            iMaxCurv = i;
                        }
                    }
 
                    // Save the Index with max curvature
                    _cusps.Add(iMaxCurv);
 
                    // Continue the search with next StylusPoint
                    iPoint = m + 1;
                    iCuspPrev = iMaxCurv;
                }
                else if (0.035 > rCurv)
                {
                    // If the angle is less than 15 degree, skip the segment
                    iPoint = iNext;
                }
                else
                    ++iPoint;
            }
 
            // If everything went right, add the last StylusPoint to the list of cusps
            _cusps.Add(this.Count - 1);
        }
 
 
        /// <summary>
        /// Finds the next and previous data StylusPoint Index for the given data Index
        /// </summary>
        /// <param name="iPoint">Index at which the computation is performed</param>
        /// <param name="iPrevCusp">Previous cusp</param>
        /// <param name="iPrev">Previous data Index</param>
        /// <param name="iNext">Next data Index</param>
        /// <returns>Returns true if the end has NOT been reached.</returns>
        private bool FindNextAndPrev(int iPoint, int iPrevCusp, ref int iPrev, ref int iNext)
        {
            bool bHasMore = true;
 
            if (iPoint >= Count)
            {
                bHasMore = false;
                iPoint = Count - 1;
            }
 
			// Find a StylusPoint at distance-_span forward
            for (iNext = checked(iPoint + 1); iNext < Count; ++iNext)
                if (_nodes[iNext] - _nodes[iPoint] >= _span)
					break;
 
			if (iNext >= Count)
			{
				bHasMore = false;
				iNext = Count - 1;
			}
 
            for (iPrev = checked(iPoint - 1); iPrevCusp <= iPrev; --iPrev)
                if (_nodes[iPoint] - _nodes[iPrev] >= _span)
					break;
 
			if (iPrev < 0)
                iPrev = 0;
 
            return bHasMore;
        }
 
 
        /// <summary>
        /// 
        /// </summary>
        /// <param name="a"></param>
        /// <param name="rMin"></param>
        /// <param name="rMax"></param>
        private static void UpdateMinMax(double a, ref double rMin, ref double rMax)
        {
            rMin = Math.Min(rMin, a);
            rMax = Math.Max(a, rMax);
        }
        /// <summary>
        /// Sets up the internal data structure to construct chain of points
        /// </summary>
        /// <param name="rSpan">Shortest distance between two distinct points</param>
        private void SetLinks(double rSpan)
        {
            // NOP, if there is only one StylusPoint
            int count = Count;
 
            if (2 > count)
                return;
 
            // Set up the links to next and previous probe
            double rL = XY(0).X;
            double rT = XY(0).Y;
            double rR = rL;
            double rB = rT;
 
            for (int i = 0; i < count; ++i)
            {
                UpdateMinMax(XY(i).X, ref rL, ref rR);
                UpdateMinMax(XY(i).Y, ref rT, ref rB);
            }
 
            rR -= rL;
            rB -= rT;
            _dist = Math.Abs(rR) + Math.Abs(rB);
            if (false == DoubleUtil.IsZero(rSpan))
                _span = rSpan;
            else if (0 < _dist)
            {
                /***
                _nodes[count - 1] at this StylusPoint contains the length of the stroke.
                _dist is the half peripheri of the bounding box of the stroke.
                The idea here is that the Length/_dist is somewhat analogous to the 
                "fractal dimension" of the stroke (or in other words, how much the stroke
                winds.)
                Length/count is the average distance between two consequitive points
                on the stroke. Thus, this average distance is multiplied by the winding
                factor.
                If the stroke were a PURE straight line across the diagone of a square, 
                Lenght/Dist will be approximately 1.41. And if there were one pixel per
                co-ordinate, the span would have been 1.41, which works fairly well in
                cusp detection
                ***/
                _span = 0.75f * (_nodes[count - 1] * _nodes[count - 1]) / (count * _dist);
            }
 
            if (_span < 1.0)
                _span = 1.0f;
 
            FindAllCusps();
        }
 
 
        private List<CDataPoint>        _points;
        private List<double>            _nodes;
        private double                  _dist = 0;
        private List<int>               _cusps = new List<int>();
 
        // Parameters governing the cusp detection algorithm
        // Distance between probes for curvature checking
        private double _span = 3; // Default span
    
        struct CDataPoint
        {
            public Point        Point;       // Point (coordinates are double)
            public int          Index;       // Index into the original array
            public int          TanPrev;    // Previous StylusPoint Index for tangent computation
            public int          TanNext;    // Next StylusPoint Index for tangent computation
        };
    }
}