Rounding polygon corners

List.hpp

#ifndef ARRAYLIST_HPP
#define ARRAYLIST_HPP

#include <stdlib.h>
#include <assert.h>
#include <string.h>

//NOTE: this struct zero-initializes to a valid state!
//      List<T> list = {}; //this is valid
template <typename TYPE>
struct List {
    TYPE * data;
    size_t len;
    size_t max;

    void init(size_t reserve = 1024 / sizeof(TYPE) + 1) {
        assert(reserve > 0);
        data = (TYPE *) malloc(reserve * sizeof(TYPE));
        max = reserve;
        len = 0;
    }

    void add(TYPE t) {
        if (len == max) {
            max = max * 2 + 1;
            data = (TYPE *) realloc(data, max * sizeof(TYPE));
        }

        data[len] = t;
        ++len;
    }

    template <typename ALLOC>
    void add(TYPE t, ALLOC & alloc) {
        if (len == max) {
            max = max * 2 + 1;
            data = (TYPE *) alloc.realloc(data, len * sizeof(TYPE), max * sizeof(TYPE), alignof(TYPE));
        }

        data[len] = t;
        ++len;
    }

    void remove(size_t index) {
        assert(index < len);
        --len;
        for (int i = index; i < len; ++i) {
            data[i] = data[i + 1];
        }
    }

    //removes elements in range [first, last)
    void remove(size_t first, size_t last) {
        assert(first < last);
        assert(last <= len);
        size_t range = last - first;
        len -= range;
        for (int i = first; i < len; ++i) {
            data[i] = data[i + range];
        }
    }

    void shrink_to_fit() {
        data = (TYPE *) realloc(data, len * sizeof(TYPE));
    }

    List<TYPE> clone() {
        List<TYPE> ret = { (TYPE *) malloc(len * sizeof(TYPE)), len, len };
        memcpy(ret.data, data, len * sizeof(TYPE));
        return ret;
    }

    void finalize() {
        free(data);
        *this = {};
    }

    TYPE & operator[](size_t index) {
    	assert(index < len);
        return data[index];
    }

    //no need to define an iterator class, because range-for will work with raw pointers
    TYPE * begin() { return { data }; }
    TYPE * end() { return { data + len }; }
};

//convenience function for same-line declaration+initialization
template<typename TYPE>
static inline List<TYPE> create_list(size_t reserve = 1024 / sizeof(TYPE) + 1) {
    List<TYPE> list;
    list.init(reserve);
    return list;
}

#endif

round-corners.cpp

#include <stdint.h>
#include <math.h>
#include "List.hpp" //my personal arraylist implementation

static const float PI = 3.1415926535;
static const float HALF_PI = PI / 2;
static const float QUARTER_PI = PI / 4;

struct Vec2 { float x, y; };
struct Mat2 { float m00, m01, m10, m11; };

static inline Vec2 vec2(float f) { return { f, f }; }
static inline Vec2 vec2(float x, float y) { return { x, y }; }

static inline Vec2 operator-(Vec2 v) { return { -v.x, -v.y }; }
static inline Vec2 operator-(Vec2 l, Vec2 r) { return { l.x - r.x, l.y - r.y }; }
static inline Vec2 operator+(Vec2 l, Vec2 r) { return { l.x + r.x, l.y + r.y }; }
static inline Vec2 operator*(float f, Vec2  v) { return { f * v.x, f * v.y }; }
static inline Vec2 operator*(Vec2  v, float f) { return { f * v.x, f * v.y }; }
static inline Vec2 operator*(Vec2  l, Vec2  r) { return { l.x * r.x, l.y * r.y }; }
static inline Vec2 operator/(Vec2  v, float f) { return { v.x / f, v.y / f }; }
static inline Vec2 operator/(Vec2  l, Vec2  r) { return { l.x / r.x, l.y / r.y }; }

static inline Vec2 nor(Vec2 v) {
    float f = 1 / sqrtf(v.x * v.x + v.y * v.y);
    return { v.x * f, v.y * f };
}

static inline float dot(Vec2 l, Vec2 r) {
    return l.x * r.x + l.y * r.y;
}

static inline float cross(Vec2 l, Vec2 r) {
    return l.x * r.y - l.y * r.x;
}

static inline float len (Vec2 v) {
    return sqrtf(v.x * v.x + v.y * v.y);
}

static inline Vec2 operator*(Mat2 m, Vec2 v) {
    return { m.m00 * v.x + m.m01 * v.y,
             m.m10 * v.x + m.m11 * v.y, };
}



int circle_detail(float radius, float delta) {
    return fminf(11, sqrtf(radius / 4)) / QUARTER_PI * fabsf(delta) + 1;
}

//PRECONDITION: points.len > 2
//PRECONDITION: no points are duplicate
//PRECONDITION: shape is non-self-intersecting
List<Vec2> round_corners(List<Vec2> points, float pathRadius) {
    List<Vec2> path = {};
    for (int i = 1; i <= points.len; ++i) {
        Vec2 p1 = points[i - 1];
        Vec2 p2 = points[i % points.len];
        Vec2 p3 = points[(i + 1) % points.len];

        Vec2 leg1 = nor(p2 - p1);
        Vec2 leg2 = nor(p3 - p2);
        if (dot(leg1, leg2) > 0.999) {
            path.add(p2);
        } else {
            float cwMul = cross(leg1, leg2) < 0? 1 : -1;

            //we use 0.49 instead of 0.5 to avoid generating duplicate verts, which could confuse triangulation
            float minLeg = fminf(len(p2 - p1) * 0.49f, len(p3 - p2) * 0.49f);

            Vec2 a = leg2 - leg1;
            Vec2 b = vec2(leg1.y, -leg1.x) * cwMul; //cw right angle
            Vec2 c = a * (pathRadius / dot(a, b));
            float r = fminf(pathRadius, pathRadius * minLeg / dot(leg2, c));
            Vec2 p = p2 + c * (r / pathRadius);

            Vec2 d1 = vec2(-leg1.y, leg1.x) * cwMul * r;
            Vec2 d2 = vec2(-leg2.y, leg2.x) * cwMul * r;

            float theta = atan2f(cross(d1, d2), dot(d1, d2));
            int segments = circle_detail(r, theta);
            path.add(p + d1);
            if (segments > 1) {
                float cos = cosf(theta / segments);
                float sin = sinf(theta / segments);
                Mat2 rot = { cos, -sin, sin, cos };
                for (int i = 1; i < segments; ++i) {
                    d1 = rot * d1;
                    path.add(p + d1);
                }
            }
            path.add(p + d2);
        }
    }
    return path;
}