Scaling points algorithm

scale_points.cpp

     // POINT STRUCT
     
     struct Point {

        double x = DBL_MAX;
        double y = DBL_MAX;

        Point() {};
        Point(double x, double y) : x{x}, y{y} {}
        Point(const std::pair<double, double> &p) : x{p.first}, y{p.second} {};

        inline std::string toString() const
        {
            return TextUtils::formatString("%.15f,%.15f", x, y);
        };

        inline bool isSet()
        {
            return fabs(x - DBL_MAX) > DBL_EPSILON && fabs(y - DBL_MAX) > DBL_EPSILON;
        }

        inline static Point parse(const std::string &str)
        {
            Point p;
            auto parts = TextUtils::splitString(str, ',');

            if (parts.size() == 2) {
                p.x = std::stod(parts[0]);
                p.y = std::stod(parts[1]);
            }

            return p;
        }

        inline Point operator * (double value)
        {
            return {this->x * value, this->y * value};
        }

        inline Point operator / (double value)
        {
            return {this->x / value, this->y / value};
        }

        inline Point operator + (const Point &other)
        {
            return {this->x + other.x, this->y + other.y};
        }

        template<
            typename T,
            typename = typename std::enable_if<std::is_arithmetic<T>::value, T>::type
            >
        inline Point operator + (T value) const
        {
            return {this->x + value, this->y + value};
        }

        inline Point operator - (const Point &other)
        {
            return {this->x - other.x, this->y - other.y};
        }

        inline Point operator - (const Point &other) const
        {
            return {this->x - other.x, this->y - other.y};
        }

        inline bool operator == (const Point &other)
        {
            return this->x == other.x && this->y == other.y;
        };
    };

     // MAIN METHOD
     
     /**
     * @see https://math.stackexchange.com/a/1849845
     * @param points Points to scale
     * @param inset Inset to scale, negative inset increases area (outset)
     * @param useInvertedY Use inverted or common coordinate system
     */
    std::vector<Point>
    MathUtils::scalePointsByInset(const std::vector<Point> &points, double inset, bool useInvertedY)
    {
        std::vector<Point> result;

        int error = 0;
        auto isClockwise = polygonIsClockwise(points, error, useInvertedY);

        if (error != 0) {
            return points;
        }

        auto _points = points;

        // invert flag for angleIsConvex method

        if (!isClockwise) {
            std::reverse(_points.begin(), _points.end());
        }

        for (int i = 0; i < _points.size(); i++) {

            // get angle

            auto currPt = _points[i];
            auto nextPt = _points[countInRange(1, i, 0, _points.size() - 1)];
            auto prevPt = _points[countInRange(-1, i, 0, _points.size() - 1)];

            auto angle = angleBetweenPoints(prevPt, currPt, nextPt);

            // calculate inset point

            auto _inset = angleIsConvex(prevPt, currPt, nextPt) ? inset * -2 : inset * 2;
            auto v = _inset / (2 * sin(angle));

            auto dist1 = calculateLineLength(prevPt, currPt);
            auto dist2 = calculateLineLength(currPt, nextPt);

            auto _u = (prevPt - currPt) / dist1 * v;
            auto _v = (nextPt - currPt) / dist2 * v;

            auto insetPt = currPt - _u - _v;

            result.push_back(insetPt);
        }

        return result;
    }
    
    // UTILS
    
    bool
    MathUtils::polygonIsClockwise(const std::vector<Point> &points, int &error, bool useInvertedY)
    {
        if (points.size() < 3) {
            error = TRIANGULATION_ERROR;
            return false;
        }

        auto minPtIt = std::min_element(points.begin(), points.end(), [](Point p1, Point p2) {
            return p1.x < p2.x && p1.y < p2.y;
        });
        auto minPt = *minPtIt;
        auto prevPt = (minPt == points.front()) ? points.back() : *(minPtIt - 1);
        auto nextPt = (minPt == points.back()) ? points.front() : *(minPtIt + 1);

        auto direction = (prevPt.x - minPt.x) * (nextPt.y - minPt.y) - (prevPt.y - minPt.y) * (nextPt.x - minPt.x);

        return useInvertedY ? direction <= 0 : direction > 0;
    }
    
    /**
     * Wraps to minValue or maxValue using closed interval logic
     */
    double
    MathUtils::countInRange(const int step, const double value, const double minValue, const double maxValue)
    {
        assert(minValue < maxValue);
        assert(value >= minValue && value <= maxValue);

        auto range = maxValue - minValue + 1;
        assert(abs(step) <= range);

        auto result = value + step;

        if (result < minValue) {
            result += range;
        } else if (result > maxValue) {
            result -= range;
        }

        return result;
    }
    
    /// https://www.quora.com/How-do-I-calculate-the-angle-between-two-points-using-C++-programming
    double
    MathUtils::angleBetweenPoints(const Point &prevPt, const Point &currPt, const Point &nextPt)
    {
        Point _p1 = prevPt - currPt;
        Point _p2 = nextPt - currPt;

        // calculate modulus of Vector V1 i.e. |V1|
        auto length1 = sqrt(_p1.x * _p1.x + _p1.y * _p1.y);
        // calculate modulus of Vector V2 i.e. |V2|
        auto length2 = sqrt(_p2.x * _p2.x + _p2.y * _p2.y);
        // calculate dot product between two vectors
        auto dot = _p1.x * _p2.x + _p1.y * _p2.y;

        auto a = dot / (length1 * length2);

        if (a >= 1.0) {
            return 0.0;
        }

        if (a <= -1.0) {
            return M_PI;
        }

        return acos(a);
    }
    
    /**
     * Requires anti-clockwise points in non-inverted coordinate system
     */
    bool
    MathUtils::angleIsConvex(const Point &prevPt, const Point &currPt, const Point &nextPt)
    {
        auto dp1 = currPt - prevPt;
        auto dp2 = nextPt - currPt;
        auto zCrossProduct = dp1.x * dp2.y - dp1.y * dp2.x;

        return zCrossProduct > 0;
    }
    
    double
    MathUtils::calculateLineLength(Point a, Point b)
    {
        return sqrt(pow(b.x - a.x, 2) + pow(b.y - a.y, 2));
    }
    
    

may give incorrect results, see https://ru.stackoverflow.com/questions/1304852/swift-%d0%a3%d0%b2%d0%b5%d0%bb%d0%b8%d1%87%d0%b8%d1%82%d1%8c-%d1%80%d0%b8%d1%81%d1%83%d0%b5%d0%bc%d1%83%d1%8e-%d1%84%d0%b8%d0%b3%d1%83%d1%80%d1%83-%d0%b2%d0%be-%d0%b2%d1%81%d0%b5-%d1%81%d1%82%d0%be%d1%80%d0%be%d0%bd%d1%8b