Skip to content

Instantly share code, notes, and snippets.

@DanielWJudge

DanielWJudge/LargestTriangleThreeBuckets.cs

Last active March 16, 2024 15:23
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save DanielWJudge/63300889f27c7f50eeb7 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save DanielWJudge/63300889f27c7f50eeb7 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. DanielWJudge renamed this gist Aug 25, 2014. 1 changed file with 0 additions and 0 deletions.
    0 LargestTriangleThreeBuckets → LargestTriangleThreeBuckets.cs
    View file
    File renamed without changes.
  2. DanielWJudge created this gist Aug 25, 2014.
    69 changes: 69 additions & 0 deletions LargestTriangleThreeBuckets
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,69 @@
    public static IEnumerable<Tuple<double, double>> LargestTriangleThreeBuckets(List<Tuple<double, double>> data, int threshold)
    {
    int dataLength = data.Count;
    if (threshold >= dataLength || threshold == 0)
    return data; // Nothing to do

    List<Tuple<double, double>> sampled = new List<Tuple<double, double>>(threshold);

    // Bucket size. Leave room for start and end data points
    double every = (double)(dataLength - 2) / (threshold - 2);

    int a = 0;
    Tuple<double, double> maxAreaPoint = new Tuple<double, double>(0,0);
    int nextA = 0;

    sampled.Add(data[a]); // Always add the first point

    for (int i = 0; i < threshold - 2; i++)
    {
    // Calculate point average for next bucket (containing c)
    double avgX = 0;
    double avgY = 0;
    int avgRangeStart = (int)(Math.Floor((i + 1) * every) + 1);
    int avgRangeEnd = (int)(Math.Floor((i + 2) * every) + 1);
    avgRangeEnd = avgRangeEnd < dataLength ? avgRangeEnd : dataLength;

    int avgRangeLength = avgRangeEnd - avgRangeStart;

    for (; avgRangeStart < avgRangeEnd; avgRangeStart++)
    {
    avgX += data[avgRangeStart].Item1; // * 1 enforces Number (value may be Date)
    avgY += data[avgRangeStart].Item2;
    }
    avgX /= avgRangeLength;

    avgY /= avgRangeLength;

    // Get the range for this bucket
    int rangeOffs = (int)(Math.Floor((i + 0) * every) + 1);
    int rangeTo = (int)(Math.Floor((i + 1) * every) + 1);

    // Point a
    double pointAx = data[a].Item1; // enforce Number (value may be Date)
    double pointAy = data[a].Item2;

    double maxArea = -1;

    for (; rangeOffs < rangeTo; rangeOffs++)
    {
    // Calculate triangle area over three buckets
    double area = Math.Abs((pointAx - avgX) * (data[rangeOffs].Item2 - pointAy) -
    (pointAx - data[rangeOffs].Item1) * (avgY - pointAy)
    ) * 0.5;
    if (area > maxArea)
    {
    maxArea = area;
    maxAreaPoint = data[rangeOffs];
    nextA = rangeOffs; // Next a is this b
    }
    }

    sampled.Add(maxAreaPoint); // Pick this point from the bucket
    a = nextA; // This a is the next a (chosen b)
    }

    sampled.Add(data[dataLength - 1]); // Always add last

    return sampled;
    }