//
//  GSGeometryHelpers.h
//
//  Created by Georg Seifert on 2009-12-01.
//  Copyright (c) 2009 schriftgestaltung.de. All rights reserved.
//

#if !TARGET_OS_IOS
#import <Foundation/NSGeometry.h>
#endif

#import <GlyphsCore/GSBase.h>

#ifndef GLYPHS_VIEWER
#import <GlyphsCore/GraphicsGems.h>
#endif

NS_ASSUME_NONNULL_BEGIN
#if defined(__cplusplus)
extern "C" {
#endif /* defined(__cplusplus) */

@class GSPathSegment;

typedef NS_ENUM(uint8_t, GSAlignment) {
	GSTopLeft = 6,
	GSTopCenter = 7,
	GSTopRight = 8,
	GSCenterLeft = 3,
	GSCenterCenter = 4,
	GSCenterRight = 5,
	GSBottomLeft = 0,
	GSBottomCenter = 1,
	GSBottomRight = 2,
	GSAlignmentNone = 0xff,
};

typedef NS_ENUM(uint8_t, GSIntersectionState) {
	ONTOP = 1,
	PARALLEL = 2
};

struct GSPoint3 {
	CGFloat x;
	CGFloat y;
	CGFloat z;
};
typedef struct GSPoint3 GSPoint3;

extern const CGFloat twoThirds; // used in TrueType conversion

#define GSRound(Value) lround(Value)

#ifndef GSGeometryHelpers
#define GSGeometryHelpers

#define M_PI_180 0.017453292519943295

@interface GSGeometry : NSObject

+ (CGFloat)angleOfVector:(NSPoint)point;

+ (CGFloat)angleBetweenVector:(NSPoint)point1 andVector:(NSPoint)point2;

+ (NSPoint)subtractPoint:(NSPoint)point1 andPoint:(NSPoint)point2;

+ (CGFloat)distance:(NSPoint)point1 toPoint:(NSPoint)point2;

+ (CGFloat)distanceOfPoint:(NSPoint)point1
				  fromLine:(NSPoint)line1
						  :(NSPoint)line2;

+ (NSPoint)nearestPointUnlimited:(NSPoint)point1
						onLineP1:(NSPoint)line1
							  p2:(NSPoint)line2
							   t:(out CGFloat *)t;

+ (NSPoint)nearestPoint:(NSPoint)point1
			   onLineP1:(NSPoint)line1
					 p2:(NSPoint)line2
					  t:(out CGFloat *)t;

+ (bool)angle:(CGFloat)angle toRun:(out int *)run rise:(out int *)rise;

@end

static inline NSPoint GSUnitVector(NSPoint A);

static inline CGFloat GSCross(NSPoint A, NSPoint B) {
	return A.x * B.y - B.x * A.y;
}

static inline NSPoint GSRoundHandle(NSPoint point) {
	NSPoint Unit = GSUnitVector(point);
	NSPoint Temp1 = point;
	Temp1.x += Unit.x * 0.4;
	Temp1.y += Unit.y * 0.4;
	NSPoint Temp2 = point;
	Temp2.x -= Unit.x * 0.4;
	Temp2.y -= Unit.y * 0.4;

	NSPoint Temp0;
	Temp0.x = round(point.x);
	Temp0.y = round(point.y);
	CGFloat C0 = GSCross(Temp0, point);
	Temp1.x = round(Temp1.x);
	Temp1.y = round(Temp1.y);
	CGFloat C1 = GSCross(Temp1, point);
	Temp2.x = round(Temp2.x);
	Temp2.y = round(Temp2.y);
	CGFloat C2 = GSCross(Temp2, point);
	if (point.x * point.y > 0) {
		if (C0 < C1 && C0 < C2) {
			return Temp0;
		}
		if (C1 < C0 && C1 < C2) {
			return Temp1;
		}
		return Temp2;
	}
	else {
		if (C0 > C1 && C0 > C2) {
			return Temp0;
		}
		if (C1 > C0 && C1 > C2) {
			return Temp1;
		}
		return Temp2;
	}
}

static inline CGFloat GSRoundGrid(CGFloat value, CGFloat grid) {
	value = round(value / grid) * grid;
	if (grid > 1) {
		value = round(value);
	}
	return value;
}

static inline NSPoint GSRoundPoint(NSPoint point) {
	point.x = round(point.x);
	point.y = round(point.y);
	return point;
}

NSPoint GSRoundPointToDirection(NSPoint point, NSPoint unitVector, GSGridSettings grid);

NSPoint GSRoundPointToLine(NSPoint point, NSPoint A, NSPoint B, GSGridSettings grid);

static inline NSPoint GSRoundPointGrid(NSPoint point, CGFloat grid) {
	if (grid >= 0.0001) {
		point.x = round((point.x + 0.0000001) / grid) * grid;
		point.y = round((point.y + 0.0000001) / grid) * grid;
		if (grid > 1) {
			point.x = round(point.x);
			point.y = round(point.y);
		}
	}
	return point;
}

NSPoint GSRoundPointGridSetting(NSPoint point, GSGridSettings grid);

NSPoint GSRoundPointGridSettingMax(NSPoint point, GSGridSettings grid, int maxGrid);

static inline NSSize GSRoundSize(NSSize size) {
	size.width = round(size.width);
	size.height = round(size.height);
	return size;
}

static inline NSRect GSRoundRectGrid(NSRect rect, CGFloat grid) {
	NSPoint topRight = NSMakePoint(NSMaxX(rect), NSMaxY(rect));
	topRight = GSRoundPointGrid(topRight, grid);
	NSPoint bottomLeft = NSMakePoint(NSMinX(rect), NSMinY(rect));
	bottomLeft = GSRoundPointGrid(bottomLeft, grid);
	rect.origin.x = bottomLeft.x;
	rect.origin.y = bottomLeft.y;
	rect.size.width = topRight.x - bottomLeft.x;
	rect.size.height = topRight.y - bottomLeft.y;
	return rect;
}

static inline NSRect GSRoundRect(NSRect rect) {
	return GSRoundRectGrid(rect, 1);
}

static inline NSPoint GSMaxPoint(NSPoint p1, NSPoint p2) {
	return NSMakePoint(fmax(p1.x, p2.x), fmax(p1.y, p2.y));
}

static inline NSPoint GSMinPoint(NSPoint p1, NSPoint p2) {
	return NSMakePoint(fmin(p1.x, p2.x), fmin(p1.y, p2.y));
}

static inline NSRect GSScaleRect(NSRect rect, CGFloat scale) {
	rect.origin.x *= scale;
	rect.origin.y *= scale;
	rect.size.height *= scale;
	rect.size.width *= scale;
	return rect;
}

static inline NSRect GSScaleRectAroundPoint(NSRect rect, NSPoint center, CGFloat scale) {
	CGFloat newWidth = rect.size.width * scale;
	CGFloat newHeight = rect.size.height * scale;
	CGFloat dx = (newWidth - rect.size.width) * ((center.x - rect.origin.x) / rect.size.width);
	CGFloat dy = (newHeight - rect.size.height) * ((center.y - rect.origin.y) / rect.size.height);
	rect.origin.x -= dx;
	rect.origin.y -= dy;
	rect.size.width = newWidth;
	rect.size.height = newHeight;
	return rect;
}

static __inline__ NSRect GSCenteredRectInRect(NSRect outerRect, NSSize innerSize) {
	NSRect rect;
	rect.origin.x = outerRect.origin.x + floor((outerRect.size.width - innerSize.width) / 2.0);
	rect.origin.y = outerRect.origin.y + floor((outerRect.size.height - innerSize.height) / 2.0);
	rect.size = innerSize;
	return rect;
}

BOOL GSValidateRect(NSRect rect);

NSRange GSValidateRange(NSRange range, NSUInteger max);

static inline NSSize GSScaleSize(NSSize aSize, CGFloat scale) {
	aSize.width *= scale;
	aSize.height *= scale;
	return aSize;
}

static inline NSPoint GSScalePoint(NSPoint P, CGFloat scalar) {
	return NSMakePoint(P.x * scalar, P.y * scalar);
}

static inline NSPoint GSAddPoints(NSPoint A, NSPoint B) {
	A.x += B.x;
	A.y += B.y;
	return A;
}

static inline NSPoint GSSubtractPoints(NSPoint A, NSPoint B) {
	A.x -= B.x;
	A.y -= B.y;
	return A;
}

static inline NSPoint GSFlipUnitPoint(NSPoint p) {
	p.y = 1 - p.y;
	return p;
}

#ifndef GLYPHS_VIEWER
static inline NSPoint GSInterpolatePoints(NSPoint a, NSPoint b, CGFloat t) {
	return NSMakePoint(LERP(t, a.x, b.x), LERP(t, a.y, b.y));
}
#endif

static inline NSPoint GSAbsolutePointInRect(NSPoint relativePoint, NSRect rect) {
	return NSMakePoint(rect.origin.x + (NSWidth(rect) * relativePoint.x),
					   rect.origin.y + (NSHeight(rect) * relativePoint.y));
}

static inline NSPoint GSRelativePointInRect(NSPoint absolutePoint, NSRect rect) {
	return NSMakePoint((absolutePoint.x - rect.origin.x) / NSWidth(rect),
					   (absolutePoint.y - rect.origin.y) / NSHeight(rect));
}

static inline NSPoint GSUnitVector(NSPoint A) {
	CGFloat length = sqrtf((float)((A.x * A.x) + (A.y * A.y)));
	A.x /= length;
	A.y /= length;
	return A;
}

static inline NSPoint GSUnitVectorFromTo(NSPoint B, NSPoint A) {
	A.x -= B.x;
	A.y -= B.y;
	CGFloat length = sqrtf((float)((A.x * A.x) + (A.y * A.y)));
	A.x /= length;
	A.y /= length;
	return A;
}

static inline NSPoint GSUnitVectorFromAngle(CGFloat Angle) { // in degree, x axis is 0°
	Angle *= M_PI_180;
	return NSMakePoint(cos(Angle), sin(Angle));
}

static inline NSPoint GSNormalVector1(NSPoint A);
static inline NSPoint GSNormalVector1(NSPoint A) {
	return NSMakePoint(A.y, -A.x);
}

static inline NSPoint GSNormalVector2(NSPoint A);
static inline NSPoint GSNormalVector2(NSPoint A) {
	return NSMakePoint(-A.y, A.x);
}

NSPoint GSSkewVectorRelativeToItself(NSPoint vector, double skewAngleDegrees);

static inline double GSSquareDistance(NSPoint a, NSPoint b) {
	double dx = a.x - b.x;
	double dy = a.y - b.y;
	return dx * dx + dy * dy;
}

static inline double GSDistance(NSPoint a, NSPoint b) {
	double dx = a.x - b.x;
	double dy = a.y - b.y;
	return hypot(dx, dy);
}

static inline double GSLengthOfVector(NSPoint A) {
	return hypot(A.x, A.y);
}

CGFloat GSDistanceN(CGFloat * __counted_by(count) A, CGFloat * __counted_by(count) B, unsigned int count);

// t may be just outside 0 or 1. -0.0001 <= t <= 1.0001
#define T_EPSILON 0.00001
// arbitrary but catching when intersection is found and points are close but just outside
//#define PT_EPSILON	0.0000001
#define PT_EPSILON 0.00000099

#define GSFloatsEqualThreshold(A, B, threshold) (fabs(A - B) < threshold)
#define GSFloatsEqual(A, B) GSFloatsEqualThreshold(A, B, T_EPSILON)

#define GSPointsEqual(A, B, threshold) (fabs(A.x - B.x) < threshold && fabs(A.y - B.y) < threshold)

#define GSRectsEqual(A, B, threshold) (fabs(A.origin.x - B.origin.x) < threshold && fabs(A.origin.y - B.origin.y) < threshold && fabs(A.size.width - B.size.width) < threshold && fabs(A.size.height - B.size.height) < threshold)

#define GSPointIsZero(A, threshold) (fabs(A.x) < threshold && fabs(A.y) < threshold)

#define RAD(A) ((A) * M_PI_180)

#define DEG(A) ((A) / M_PI_180)

/// Returns a value in the interval [0, 2π).
static inline CGFloat GSNormalizeAngleRAD(CGFloat angle) {
	return angle - floor(angle / (2 * M_PI)) * 2 * M_PI;
}

/// Returns a value in the interval [0, 360).
static inline CGFloat GSNormalizeAngleDEG(CGFloat angle) {
	return angle - floor(angle / 360) * 360;
}

typedef NS_ENUM(uint8_t, GSRotationDirection) {
	GSRotationDirectionSmallestAngle = 0,
	GSRotationDirectionClockwise = 1,
	GSRotationDirectionCounterclockwise = 2,
};

/// Returns a version of the angle that matches the given direction.
///
/// - Parameter angle: An angle in arc degree.
/// - Parameter direction: The direction in which to normalize the angle.
///                   If `GSRotationDirectionSmallestAngle`, the return value is in the interval (-180, 180].
///                   If `GSRotationDirectionClockwise`, the return value is in the interval (-360, 0].
///                   If `GSRotationDirectionCounterclockwise`, the return value is in the interval [0, 360).
CGFloat GSNormalizeAngleDirection(CGFloat angle, GSRotationDirection direction);

static inline CGFloat GSSlope(NSPoint P1, NSPoint P2) {
	if (fabs(P2.x - P1.x) < 0.001) {
		return NSNotFound;
	}
	return (P2.y - P1.y) / (P2.x - P1.x);
}

NSRect GSRectFromTwoPoints(NSPoint a, NSPoint b);
/// Returns the bounds of the given four points.
NSRect GSRectFromFourPoints(NSPoint a, NSPoint b, NSPoint c, NSPoint d);

NSRect GSRectInsetWithEdgeInsets(NSRect rect, NSEdgeInsets insets);
#endif

CGFloat GSAngleOfVector(NSPoint P);

CGFloat GSAngleBetweenVectors(NSPoint firstPoint, NSPoint secondPoint);

NSPoint GSSlantPointAroundY(NSPoint point, CGFloat slantHeightY, CGFloat angleDegrees);

void GSCircleSegmentFromPointsAndTangents(const NSPoint *tangent1, const NSPoint *tangent2, const NSPoint *p1, NSPoint *p2, NSPoint *p3, const NSPoint *p4);

BOOL GSOffsetLine(NSPoint *P0, NSPoint *P1, CGFloat OffsetX, CGFloat OffsetY);

/*****
 *
 *   dot
 *
 *****/
CGFloat GSDot(NSPoint P1, NSPoint P2);

CGFloat GSClamp(CGFloat v, CGFloat a, CGFloat b);

BOOL GSPointIsLeftOfLine(NSPoint P0, NSPoint P1, NSPoint point);

int GSLeftRayHitsLine(NSPoint P0, NSPoint P1, NSPoint point);

/**
 @param segment a segment to hit
 @param point the start of the ray
 @param ignoreT t value to ignore. this is needed for the selftest branch
 */
int GSLeftRayHitsSegment(GSPathSegment *segment, NSPoint point, int ignoreT);

int GSLeftRayHitsCubic(NSPoint point, NSPoint p0, NSPoint p1, NSPoint p2, NSPoint p3, int ignoreT);

int GSLeftRayHitsQuadraticSpline(const NSPoint * __counted_by(count) elements, size_t count, CGFloat minBounds, NSPoint point, int ignoreT);

/*****
 *
 *   lerp
 *
 *****/
// NSPoint GSLerp(NSPoint P1, NSPoint P2, CGFloat t);

NSPoint GSMiddlePointLine(NSPoint P1, NSPoint P2);

NSPoint GSMiddlePointCubic(NSPoint P1, NSPoint P2, NSPoint P3, NSPoint P4);

// check if line ab and bc have the same direction
static inline BOOL GSCheckColinearLines(NSPoint a, NSPoint b, NSPoint c) {
	CGFloat area = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
	// GSLog(@"__area %f", area);
	return fabs(area) < 0.001;
}

NSArray *GSIntersectCubicCubicPoints(const NSPoint a1, const NSPoint a2, const NSPoint a3, const NSPoint a4, const NSPoint b1, const NSPoint b2, const NSPoint b3, const NSPoint b4) GSDeprecated("GSIntersectCubicCubicPointsA");

void GSIntersectCubicCubicPointsA(const NSPoint a1, const NSPoint a2, const NSPoint a3, const NSPoint a4, const NSPoint b1, const NSPoint b2, const NSPoint b3, const NSPoint b4, GSIntersectResultsStruct *intersections);

NSArray *GSIntersectCubicCubicUnlimited(const NSPoint P1, const NSPoint P2, const NSPoint P3, const NSPoint P4, const NSPoint Q1, const NSPoint Q2, const NSPoint Q3, const NSPoint Q4) GSDeprecated("GSIntersectCubicCubicUnlimitedA");

void GSIntersectCubicCubicUnlimitedA(const NSPoint P1, const NSPoint P2, const NSPoint P3, const NSPoint P4, const NSPoint Q1, const NSPoint Q2, const NSPoint Q3, const NSPoint Q4, GSIntersectResultsStruct *intersections);
/** Finds all intersections between a curve and a line.

@param p1 start point of the curve.
@param p2 first offcurve point of the curve.
@param p3 second offcurve point of the curve.
@param p4 end point of the curve.
@param a1 first point of the line.
@param a2 second point of the line.
@return an NSArray of point values for all intersections.
*/
NSArray *_Nullable GSIntersectCubicLine(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4, NSPoint a1, NSPoint a2) GSDeprecated("GSIntersectCubicLineA");

void GSIntersectCubicLineA(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4, NSPoint a1, NSPoint a2, GSIntersectResultsStruct *intersections);

NSArray *_Nullable GSIntersectCubicLineTimes(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4, NSPoint a1, NSPoint a2, BOOL checkBounds);

NSArray *_Nullable GSIntersectCubicLineUnlimited(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4, NSPoint a1, NSPoint a2);

void GSIntersectCubicLineUnlimitedA(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4, NSPoint a1, NSPoint a2, GSIntersectResultsStruct *intersections);

NSArray *_Nullable GSIntersectCubicLineUnlimitedTimes(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4, NSPoint a1, NSPoint a2);

NSArray *GSIntersectQuadraticSplineLine(NSPoint * __counted_by(count) points, NSUInteger count, NSPoint a1, NSPoint a2) GSDeprecated("GSIntersectQuadraticSplineLineA");

void GSIntersectQuadraticSplineLineA(NSPoint *points, NSUInteger count, NSPoint a1, NSPoint a2, GSIntersectResultsStruct *intersections);

BOOL GSIntersectQuadraticLineMatchEndA(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint a1, NSPoint a2, BOOL matchEnd, GSIntersectResultsStruct *intersections);

NSArray *GSIntersectQuadraticLine(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint a1, NSPoint a2);

NSArray *GSIntersectQuadraticQuadraticSpline(const NSPoint * __counted_by(count) elements, const int count, const NSPoint * __counted_by(otherCount) otherElements, const int otherCount) GSDeprecated("GSIntersectQuadraticQuadraticSplineA");

void GSIntersectQuadraticQuadraticSplineA(const NSPoint *elements, const int count, const NSPoint *otherElements, const int otherCount, GSIntersectResultsStruct *intersections);

NSArray *GSIntersectCubicQuadraticSpline(const NSPoint cubic[_Nonnull 4], const NSPoint * __counted_by(count) quadratic, const int count) GSDeprecated("GSIntersectCubicQuadraticSplineA");

void GSIntersectCubicQuadraticSplineA(const NSPoint cubic[_Nonnull 4], const NSPoint * __counted_by(count) quadratic, const int count, GSIntersectResultsStruct *results);

NSPoint GSPointOnQuadraticSpline(const NSPoint * __counted_by(count) curve, const int count, const double segmentT);

BOOL GSCollinearLines(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4);

NSPoint GSIntersectLineLine(const NSPoint a1, const NSPoint a2, const NSPoint b1, const NSPoint b2);

NSPoint GSIntersectLineLineUnlimited(const NSPoint aa, const NSPoint ab, const NSPoint ba, const NSPoint bb);

BOOL GSIntersectRays(NSPoint p1, NSPoint p2, NSPoint q1, NSPoint q2, NSPoint *intersection);

BOOL GSIntersectLineWithRect(NSPoint p1, NSPoint p2, NSRect rect, NSPoint *i1, NSPoint *i2);

BOOL GSClipLineWithRect(NSPoint *start, NSPoint *end, NSRect rect);

BOOL GSCircleContainsRect(NSPoint center, CGFloat radius, NSRect rect);

void GSIntersectCircles(NSPoint M0, CGFloat R0, NSPoint M1, CGFloat R1, NSPoint *Q0, NSPoint *Q1);

NSPoint GSNearestPointOnCubicSegmentBounds(NSPoint P, NSPoint *V, CGFloat *__nullable t);

NSPoint GSNearestPointOnCubicSegment(NSPoint P, NSPoint *V, CGFloat *__nullable t);

NSPoint GSNearestPointOnQuarticSegment(NSPoint P, NSPoint *V, CGFloat *__nullable t);

NSPoint GSNearestPointOnQuartic(NSPoint inPoint, NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4, NSPoint p5, CGFloat *__nullable t);

NSPoint GSNearestPointOnQuadraticPoints(NSPoint P, NSPoint pt0, NSPoint pt1, NSPoint pt2, CGFloat *__nullable t);

CGFloat GSDistanceOfPointFromCurve(NSPoint inPoint, NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4);

CGFloat GSSquareDistanceOfPointFromCurveSegment(NSPoint inPoint, NSPoint *V);

CGFloat GSDistanceOfPointFromLineSegment(NSPoint inPoint, NSPoint a, NSPoint b);

CGFloat GSDistanceOfPointFromLine(NSPoint inPoint, NSPoint a, NSPoint b);

NSPoint GSNearestPointOnCubic(NSPoint inPoint, NSPoint p1, const NSPoint p2, const NSPoint p3, const NSPoint p4, CGFloat *__nullable t);

NSPoint GSNearestPointOnQuadraticSpline(NSPoint inPoint, NSPoint * __counted_by(count) V, int count, CGFloat *__nullable t);

NSPoint GSNearestPointOnLinePoints(NSPoint inPoint, NSPoint a, NSPoint b, CGFloat *__nullable t);

NSPoint GSNearestPointOnLineUnlimited(NSPoint inPoint, NSPoint a, NSPoint b, CGFloat *__nullable t);

void GSDividCubicPointsAtDistance(NSPoint p0, NSPoint p1, NSPoint p2, NSPoint p3, NSPoint *q1, NSPoint *q2, NSPoint *q3, NSPoint *r1, NSPoint *r2, CGFloat offset, CGFloat *length);

void GSCalcCubicParameters(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4, NSPoint *a, NSPoint *b, NSPoint *c, NSPoint *d);

void GSCalcQuadraticParameters(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint *a, NSPoint *b, NSPoint *c);

NSPoint GSSolveQuadratic(CGFloat a, CGFloat b, CGFloat c);

void GSSolveCubic(long double a, long double b, long double c, long double d, long double roots[_Nonnull 3]);

NSPoint GSDividLineAtDistance(NSPoint p0, NSPoint p1, CGFloat offset);

void GSExtendCurvePoints(const NSPoint P0, NSPoint *P1, NSPoint *P2, NSPoint *P3, CGFloat offset);

BOOL GSFitCurveToOriginPoints(NSPoint fitPoints[_Nonnull 4], const NSPoint * __counted_by(count) originPoints, const unsigned short count, CGFloat *__nullable curveError);

BOOL GSFitCurveToOriginPointsDirection(NSPoint fitPoints[_Nonnull 4], const NSPoint * __counted_by(count) originPoints, const NSPoint * __counted_by(count) __nullable originDirections, const unsigned short count, CGFloat *__nullable curveError);

BOOL GSCurveIsFlat(NSPoint on1, NSPoint off1, NSPoint off2, NSPoint on2, CGFloat threshold);

BOOL GSCurveIsFlatError(NSPoint on1, NSPoint off1, NSPoint off2, NSPoint on2, CGFloat flatError);

/******
 *
 * Bezier dividing
 *
 ******/

void GSHalveCubicPoints(NSPoint P0, NSPoint P1, NSPoint P2, NSPoint P3, NSPoint *q0, NSPoint *q1, NSPoint *q2, NSPoint *q3, NSPoint *r1, NSPoint *r2, NSPoint *r3);

void GSHalveCubicSegment(const NSPoint P[_Nonnull 4], NSPoint q[_Nonnull 4], NSPoint r[_Nonnull 4]);

void GSHalveQuadraticPoints(NSPoint P0, NSPoint P1, NSPoint P2, NSPoint *q0, NSPoint *q1, NSPoint *q2, NSPoint *r1, NSPoint *r2);

void GSHalveQuadraticSegment(const NSPoint *p, NSPoint *q, NSPoint *r);

void GSQuadratic2Cubic(NSPoint pt0, NSPoint pt1, NSPoint pt2, NSPoint *off1, NSPoint *off2);

void GSDividQuadraticPoints(NSPoint P0, NSPoint P1, NSPoint P2, NSPoint *off1, NSPoint *on, NSPoint *off2, CGFloat t);

// void GSDividQuadraticSegment(const NSPoint p[_Nonnull 3], NSPoint q[_Nullable 3], NSPoint r[_Nullable 3], CGFloat t);

BOOL GSDividQuadraticSpline(const NSPoint * __counted_by(pCount) p,const  int pCount, NSPoint * __counted_by(qCount) _Nullable q, const int qCount, NSPoint * __counted_by(rCount) _Nullable r, const int rCount, const CGFloat segmentT);

void GSDividCubicPoints(NSPoint P0, NSPoint P1, NSPoint P2, NSPoint P3, NSPoint *q0, NSPoint *q1, NSPoint *q2, NSPoint *q3, NSPoint *r1, NSPoint *r2, NSPoint *r3, CGFloat t);

NSArray<NSArray<NSValue *> *> *GSDividCubicPointsTs(NSPoint pt1, NSPoint pt2, NSPoint pt3, NSPoint pt4, NSArray<NSNumber *> *ts);

void GSDividCubicSegment(const NSPoint P[_Nonnull 4], NSPoint q[_Nonnull 4], NSPoint r[_Nonnull 4], CGFloat t);

void GSDividQuarticSegment(const NSPoint P[_Nonnull 5], NSPoint q[_Nonnull 5], NSPoint r[_Nonnull 5], CGFloat t);

#if DEBUG
void GSApproximateQuartic(NSPoint quart[_Nonnull 5], NSPoint *lines);
#endif

/// Converts from a quartic curve segment to two cubic curve segments.
///
/// The following constraints hold:
///
/// - `cubic1[0] == quartic[0]`
/// - `cubic1[3] == cubic2[0]`
/// - `cubic2[3] == quartic[4]`
///
/// - Parameter quartic: The five points of a quartic segment: start point, three control points, and the end point.
/// - Parameter cubic1: The four points of a cubic segment: start point, two control points, and the end point.
/// - Parameter cubic2: The four points of a cubic segment: start point, two control points, and the end point.
void GSQuarticToCubic(const NSPoint quartic[_Nonnull 5], NSPoint cubic1[_Nonnull 4], NSPoint cubic2[_Nonnull 4]);

void GSSegmentBetweenPoints(NSPoint P0, NSPoint P1, NSPoint P2, NSPoint P3, NSPoint *q0, NSPoint *q1, NSPoint *q2, NSPoint *q3, NSPoint StartRangePoint, NSPoint EndRangePoint);

// NSPoint GSDivideLine(NSPoint P0, NSPoint P1, CGFloat t); // Deprecated -> GSPointOnLine

NSPoint GSPointOnLine(NSPoint P0, NSPoint P1, CGFloat t);

/// Like `GSPointOnLine`, but with the returned point offset by a certain amount onto a parallel line.
/// So, more like the inverse of `GSNearestPointOnLine`.
///
/// - Parameter offset: Offset to the right of the line if positive or to the left of the line if negative.
NSPoint GSPointOffsetFromLine(NSPoint p0, NSPoint p1, CGFloat t, CGFloat offset);

/// Returns a new point offset by the given distance in the direction of the given angle in radiants.
NSPoint GSPointOffsetAtAngle(NSPoint p, CGFloat offset, CGFloat angle);

NSPoint GSPointAtTime(NSPoint P0, NSPoint P1, NSPoint P2, NSPoint P3, CGFloat t) GSDeprecated("GSPointOnCurve");

NSPoint GSPointOnCubicPoints(NSPoint P0, NSPoint P1, NSPoint P2, NSPoint P3, CGFloat t);

NSPoint GSPointOnCubicSegment(NSPoint *P, CGFloat t);

NSPoint GSPointOnQuarticPoints(NSPoint P0, NSPoint P1, NSPoint P2, NSPoint P3, NSPoint P4, CGFloat t);

NSPoint GSPointOnQuarticSegment(NSPoint *P, CGFloat t);

NSPoint GSPointOnQuadraticPoints(NSPoint P0, NSPoint P1, NSPoint P2, CGFloat t);

NSPoint GSTangentOnQuadraticPoints(NSPoint P0, NSPoint P1, NSPoint P2, CGFloat t);

NSPoint GSPointOnQuadraticSpline(const NSPoint * __counted_by(count) curve, const int count, const double segmentT);

NSPoint GSTangentOnQuadraticSegment(const NSPoint * __counted_by(count) curve, const int count, const double segmentT);

NSPoint GSTangentOnCubicSegment(const NSPoint curve[_Nonnull 4], const CGFloat t);

NSPoint GSTangentOnCubicPoints(NSPoint P0, NSPoint P1, NSPoint P2, NSPoint P3, const CGFloat t);

typedef struct GSTangentInfo {
	NSPoint tangentPoint;
	NSPoint tangentVector;
} GSTangentInfo;

int GSTangentOnQuadraticThroughPoint(NSPoint P0, NSPoint P1, NSPoint P2, NSPoint externalPoint, GSTangentInfo *tangents);

CGFloat GSLengthOfCubicPoints(NSPoint P0, NSPoint P1, NSPoint P2, NSPoint P3);

CGFloat GSLengthOfQuadraticSpline(NSPoint * __counted_by(count) curve, int count);

CGFloat GSTForDistanceCubic(CGFloat Distance, NSPoint P0, NSPoint P1, NSPoint P2, NSPoint P3, CGFloat maxT);

CGFloat GSTForDistanceQuadraticSpline(CGFloat distance, NSPoint * __counted_by(count) curve, int count);

void GSExtremeTimesOfCubicUnlimited(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4, CGFloat *t1, CGFloat *t2, CGFloat *t3, CGFloat *t4);

void GSExtremeTimesOfCubic(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4, CGFloat *t1, CGFloat *t2, CGFloat *t3, CGFloat *t4);

void GSExtremePointsOfCubic(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4, NSPoint *r, int *count);

NSArray *GSExtremesOfCubic(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4) NS_RETURNS_RETAINED;

void GSTangentPointsAtAngel(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4, CGFloat angle, CGFloat *t1, CGFloat *t2);

void GSBoundsOfQuadratic(NSPoint p1, NSPoint p2, NSPoint p3, CGFloat *minX, CGFloat *minY, CGFloat *maxX, CGFloat *maxY, BOOL *isSimple);

void GSBoundsOfQuadraticSpline(const NSPoint * __counted_by(count) elements, int count, CGFloat *minX, CGFloat *minY, CGFloat *maxX, CGFloat *maxY);

void GSBoundsOfCubic(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4, CGFloat *minX, CGFloat *minY, CGFloat *maxX, CGFloat *maxY, BOOL *isSimple);

NSRect GSBoundingRectOfCubic(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4);

void GSBoundsOfQuartic(NSPoint quart[_Nonnull 5], CGFloat *minX, CGFloat *minY, CGFloat *maxX, CGFloat *maxY, BOOL *isSimple);

NSRect GSBoundingRectOfQuadratic(NSPoint p1, NSPoint p2, NSPoint p3);

NSRect GSBoundsOfTransformedRect(NSRect rect, NSAffineTransform *transform);

BOOL GSCubicHasInflection(NSPoint p0, NSPoint p1, NSPoint p2, NSPoint p3);

NSArray *GSComputeInflection(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4);

void GSComputeInflectionTimes(NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4, CGFloat t[_Nonnull 2], int *_Nonnull count);

void GSTransformComponents(NSAffineTransformStruct M, CGFloat *__nullable sX, CGFloat *__nullable sY, CGFloat *__nullable R, CGFloat *__nullable shearX, CGFloat *__nullable shearY);

NSArray *curvatureMaxima(NSPoint P1, NSPoint P2, NSPoint P3, NSPoint P4);

CGFloat GSCurvatureSquaredForT(NSPoint P1, NSPoint P2, NSPoint P3, NSPoint P4, CGFloat t);

/// Use this function as compared to `curvatureSquaredForT` if you compute the square root of the result anyway or if you need to know the sign of the curvature.
CGFloat GSSignedCurvatureForT(NSPoint P1, NSPoint P2, NSPoint P3, NSPoint P4, CGFloat t);

NSPoint GSNormalCubicForT(NSPoint P1, NSPoint P2, NSPoint P3, NSPoint P4, CGFloat t);

NSPoint GSNormalQuadraticForT(NSPoint P1, NSPoint P2, NSPoint P3, CGFloat t);

BOOL GSCombineSegments3(NSPoint *P, NSPoint *Q, NSPoint *R);

BOOL GSCombineSegments3Fit(NSPoint *P, NSPoint *Q, NSPoint *R, CGFloat *__nullable error);

BOOL GSFixDeadCurve(NSPoint P0, NSPoint *P1, NSPoint *P2, NSPoint P3, BOOL force);

BOOL GSNormalizeCubicHandleRatios(NSPoint P0, NSPoint *P1, NSPoint *P2, NSPoint P3);

// this is mostly useful for TT convertion
CGFloat GSGetOptimalSplitParameter(NSPoint P0, NSPoint P1, NSPoint P2, NSPoint P3);

NSPoint GSShiftPointAlongLine(NSPoint p, NSPoint b, NSPoint shiftVector);

void GSFixBounds(NSRect *bounds);

struct GSNVector {
	double coord[30];
};
typedef struct GSNVector GSNVector;
GSNVector GSMakeNVector(int n, ...);
GSNVector GSInitNVector(CGFloat d);
CGFloat GSDistanceOfPointFromLineN(GSNVector inPoint, GSNVector a, GSNVector b, int n);

GSNVector GSMultiplyNVectors(GSNVector a, GSNVector b, int n);

#pragma mark Compare
NSComparisonResult GSSortPointValue(id value1, id value2, void *reverse);

NSComparisonResult GSSortPoint(NSPoint point1, NSPoint point2, void *reverse);

NSComparisonResult GSSortInteger(NSInteger idx1, NSInteger idx2);

NSComparisonResult GSSortFloat(CGFloat value1, CGFloat value2);

NSComparisonResult GSSortFloatLenient(CGFloat value1, CGFloat value2);

BOOL GSComparePoint(NSPoint P1, NSPoint P2);

static inline BOOL GSCompareSize(NSSize S1, NSSize S2) {
	return fabs(S1.width - S2.width) < 0.001 && fabs(S1.height - S2.height) < 0.001;
}

BOOL GSCompareTransformStruct(NSAffineTransformStruct T1, NSAffineTransformStruct T2);

BOOL GSAffineTransformIsIdentity(NSAffineTransform *transform);

static inline BOOL GSCompareRect(NSRect r1, NSRect r2) {
	return fabs(r1.origin.x - r2.origin.x) < 0.0001 && fabs(r1.origin.y - r2.origin.y) < 0.0001 && fabs(r1.size.width - r2.size.width) < 0.0001 && fabs(r1.size.height - r2.size.height) < 0.0001;
}

BOOL GSCompareRange(NSRange r1, NSRange r2);

BOOL GSFloatToFraction(CGFloat value, CGFloat accuracy, int *numr, int *dnom);

/// convert and angle (CCV from 12 o’clock) to run/rise as stored in the hhea table
BOOL GSAngleToSlope(CGFloat angle, int *run, int *rise);

/// The angle of run/rise. This can be used to write the italic angle so the angle is positive CCV from 12 o’clock
CGFloat GSAngleFromString(NSString *string);

NSPoint GSRotatePointAroundCenter(NSPoint point, NSPoint center, CGFloat angle);

NSPoint GSRotatePoint(NSPoint point, CGFloat angle);

NSPoint GSNearestPointOnEllipse(NSPoint center, NSSize size, CGFloat angle, NSPoint point);

CGFloat GSDistanceOfPointFromEllipse(NSPoint point, NSPoint center, NSSize size, CGFloat angle);

NSPoint GSNearestPointOnRect(NSRect rect, CGFloat angle, NSPoint point);

CGFloat GSDistanceOfPointFromRect(NSPoint point, NSRect rect, CGFloat angle);

BOOL GSMakeClothoid(NSPoint *p0, NSPoint *p1, NSPoint *p2, NSPoint *p3, NSPoint *q1, NSPoint *q2, NSPoint *q3, CGFloat t, CGFloat shift1, GSGridSettings grid);

BOOL GSMakeClothoidSymmetric(NSPoint *p0, NSPoint *p1, NSPoint *p2, NSPoint *p3, NSPoint *q1, NSPoint *q2, NSPoint *q3, CGFloat shift1, GSGridSettings grid);

NSString *GSStringFromPoint(NSPoint p);

NSString *GSStringFromRect(NSRect rect);
#ifndef GLYPHS_VIEWER
NSString *GSStringFromPoint3(GSPoint3 p);

NSString *GSStringFromTransformStruct(NSAffineTransformStruct ts);

void GSAffineSolver(NSAffineTransformStruct *ts, NSPoint *p, NSPoint *p_);
#endif

NSRect GSRectWithCenter(NSPoint center, NSSize size);

NSRect GSHandleRect(NSPoint pos, CGFloat handleSize);

#ifndef GLYPHS_VIEWER
GSAlignment GSMirrorAlignment(GSAlignment corner);

NSPoint GSAlignedPointForBounds(NSRect bounds, GSAlignment corner);

NSRect GSHandleRectForBounds(NSRect bounds, GSAlignment corner, CGFloat handleSize);

#pragma mark Point3

NS_INLINE GSPoint3 GSMakePoint3(CGFloat x, CGFloat y, CGFloat z) {
	GSPoint3 p;
	p.x = x;
	p.y = y;
	p.z = z;
	return p;
}

// cuts of the z-dimension.
NS_INLINE NSPoint GSFlatPoint(GSPoint3 point3) {
	return NSMakePoint(point3.x, point3.y);
}

GSPoint3 GSRotatePoint3(GSPoint3 point, double angleX, double angleY, double angleZ);

GSPoint3 GSRotatePoint3Center(GSPoint3 point, double angleX, double angleY, double angleZ, double centerX, double centerY, double centerZ);

/*
GSPoint3 GSNearestPointOnLine3D(GSPoint3 inPoint, GSPoint3 a, GSPoint3 b, CGFloat* t);
*/
CGFloat GSCalc(CGFloat operand1, char op, CGFloat operand2);

NSPoint GSPointFromArray(NSArray *value);
#endif

CGFloat GSFindDivisorClosestTo(CGFloat number, int target);

CGFloat GSAlphaForDistance(CGFloat distance, CGFloat min, CGFloat max);

NSAffineTransform * _Nullable GSAffineTransformMappingLine2Line(NSPoint p1, NSPoint p2, NSPoint q1, NSPoint q2, BOOL preserveLength, NSError **outError);

BOOL GSColinearLines(NSPoint p1, NSPoint mid, NSPoint p2);

BOOL GSColinearLinesTolerance(NSPoint p1, NSPoint mid, NSPoint p2, double eps);

NSPoint GSGreenHarmony(NSPoint a0, NSPoint a1, NSPoint a2, NSPoint a3, NSPoint b1, NSPoint b2, NSPoint b3);

NS_ASSUME_NONNULL_END
#if defined(__cplusplus)
} // extern "C"
#endif /* defined(__cplusplus) */
