simple implementation of the scan-line polygon fill algorithm for arduino (allows concave sections, but not intersecting edges)

polygon.cpp

#include "polygon.h"

class Point {
public:
    double x;
    double y;

    Point(void) : x(0.0), y(0.0) {}
    Point(double x, double y) : x(x), y(y) {}
};

// a segment is 2 points, with the smallest y-point first, and a computed
// (inverted) slope x/y.
class Segment {
public:
    // 5 doubles: 40 bytes
    Point p1, p2;
    double inv_slope;

    Segment(void) : inv_slope(0.0) {}

    Segment(const Point& p1, const Point& p2) {
        if (p1.y <= p2.y) {
            this->p1 = p1;
            this->p2 = p2;
        } else {
            this->p1 = p2;
            this->p2 = p1;
        }

        if (p1.y == p2.y) {
            // not used anyway.
            this->inv_slope = 0;
        } else {
            this->inv_slope = (float)(this->p2.x - this->p1.x) / (float)(this->p2.y - this->p1.y);
        }
    }

    double x_intercept(double y) const {
        return this->p1.x + (y - this->p1.y) * this->inv_slope;
    }
};

class SortedSegments {
public:
    // 16 * 40 = 640 bytes :/
    Segment segments[MAX_POLYGON_POINTS];
    uint16_t segment_count;
    double y_min, y_max;

    SortedSegments(void) : segment_count(0), y_min(0.0), y_max(0.0) {}

    void clear(void) {
        this->segment_count = 0;
        this->y_min = this->y_max = 0.0;
    }

    // sort by smallest y in the segment
    int insert_sorted(const Segment& s) {
        // keep running min/max y
        if (this->segment_count == 0) {
            y_min = s.p1.y;
            y_max = s.p2.y;
        } else {
            if (s.p1.y < y_min) y_min = s.p1.y;
            if (s.p2.y > y_max) y_max = s.p2.y;
        }

        int i = 0;
        while (i < this->segment_count && this->segments[i].p1.y < s.p1.y) i++;
        if (i < this->segment_count) {
            memmove(&this->segments[i + 1], &this->segments[i], sizeof(Segment) * (this->segment_count - i));
        }
        this->segments[i] = s;
        this->segment_count++;
        return i;
    }

    const Segment& operator[](size_t i) const {
        return this->segments[i];
    }
};

class SortedDoubles {
public:
    double values[MAX_POLYGON_POINTS];
    uint16_t count;

    SortedDoubles(void) : count(0) {}

    // sort by smallest y in the segment
    int insert_sorted(double v) {
        int i = 0;
        while (i < this->count && this->values[i] < v) i++;
        if (i < this->count) {
            memmove(&this->values[i + 1], &this->values[i], sizeof(double) * (this->count - i));
        }
        this->values[i] = v;
        this->count++;
        return i;
    }

    const double operator[](size_t i) const {
        return this->values[i];
    }
};


static SortedSegments segments;

bool fill_polygon(GxEPD2_GFX_BASE_CLASS& display, Point points[], size_t point_count, uint16_t color) {
    if (point_count > MAX_POLYGON_POINTS) return false;

    int16_t y_min, y_max = -1;

    // 1. build list of line segments (with first point as the smallest y),
    // and sort them from smallest starting y to largest.
    segments.clear();
    for (size_t i = 0; i < point_count; i++) {
        Point& p1 = points[i];
        Point& p2 = points[(i + 1) % point_count];
        // draw the line too, since that's cheap, and saves us doing
        // fixups later.
        display.drawLine(p1.x, p1.y, p2.x, p2.y, color);
        // horizontal segments have nothing to fill
        if (p1.y != p2.y) segments.insert_sorted(Segment(p1, p2));
    }

    // 2. track active lines. take advantage of the fact that the outside
    // lines are already drawn. for each scan line, order the segment
    // intersections by x, and fill the line between each pair of
    // intersections.
    int index = 0;
    for (int y = segments.y_min; y < segments.y_max; y++) {
        SortedDoubles x_vals;

        // add any segments that came into focus
        while (index < segments.segment_count && segments[index].p1.y == y) index++;

        // sort x-intercepts, ignoring segments that left focus
        for (int i = 0; i < index; i++) if (segments[i].p2.y > y) {
            x_vals.insert_sorted(segments[i].x_intercept(y));
        }

        // draw intercept pairs
        for (int i = 0; i < x_vals.count; i += 2) {
            display.drawLine((uint16_t)round(x_vals[i]), y, (uint16_t)round(x_vals[i + 1]), y, color);
        }
    }

    return true;
}