Skip to content

Instantly share code, notes, and snippets.

@schmidt9
Last active Jul 15, 2021
Embed
What would you like to do?
Scaling points algorithm
// 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));
}