Polygons in c3dlas are 2-dimensional, "simple" polygons. They can be convex and concave, and can be sometimes be self-intersecting, but cannot have holes. There is currently no support for 3D arbitrary polygons. The polygon consists of a loop of points held in points, with the last one being implicitly connected to the first with no duplicate value stored at the end.

typedef struct Polygon { vec2* points; C3DLAS_ARRAY_SIZE_ pointAlloc; C3DLAS_ARRAY_SIZE_ pointCount; vec2 centroid; float maxRadiusSq; // squared distance from the centroid to the furthest point C3DLAS_ARRAY_SIZE_ minExtrema; // most minimum point; will always be convex } Polygon;

C3DLAS_ARRAY_SIZE_ is a configurable integer type that is int32_t by default. minExtrema is the index of the point with the lowest x and y values, which is always on the convex hull of the polygon and as such has useful mathematical properties. It is usually updated incrementally as the polygon is edited.

Centroid is the average of all the points, and maxRadiusSq is the squared distance of the farthest point from the centroid. The pair can be used for cheap early rejection of intersections. Some functions that modify the polygon invalidate these stats and fill them with NAN. The stats need to be recalculated manually with polyCalcStats() or friends.

Basic Operations

void polyFreeInternals(Polygon* poly)

O(1)

Free all internal memory.

void polyPushPoint(Polygon* poly, vec2 p)

O(1)

Adds a point to the end of the polygon point list. Stats need to be recalculated afterward.

void polyInsertPoint(Polygon* poly, int index, vec2 p)

O(n)

Insert a point at a specific index of the polygon point list. Index can be negative, but should be in the range [-pointCount+1, pointCount] inclusive. Stats need to be recalculated afterward.

void polyCopy(Polygon* dst, Polygon* src)

O(n)

Makes a full deep copy of the source polygon.

void polyReverse(Polygon* poly)

O(n)

Reverses the point list, which flips the winding.

int polyGetWinding(Polygon* poly)

O(1)

Calculates the polygon winding and returns C3DLAS_CCW (counter-clockwise) or C3DLAS_CW (clockwise).

void polyEnsureCCW(Polygon* poly)

O(n), if not already CCW

Calculates the polygon winding and reverses the point list if not already CCW.

void polyEnsureCW(Polygon* poly)

O(n), if not already CW

Calculates the polygon winding and reverses the point list if not already CW.

Stats

float polyCalcArea(Polygon* poly) float polyCalcSignedArea(Polygon* poly)

O(n)

Calculates the signed or unsigned area of the polygon.

void polyCalcMinExtrema(Polygon* poly)

O(n)

Updates minExtrema index. This is usually tracked internally automatically, and you only need to call this function if you have manually changed the points array.

AABB2 polyCalcBounds(Polygon* poly)

O(n)

Calculates the minimal axis-aligned bounding box that contains the polygon.

void polyCalcStats(Polygon* poly)

O(n)

Updates both the centroid and squared radius after operations that invalidate them.

void polyCalcCentroid(Polygon* poly)

O(n)

Updates the centroid after operations that invalidate it.

void polyCalcRadiusSq(Polygon* poly)

O(n)

Updates the squared radius from the centroid after operations that invalidate it. The centroid must already be valid.

int polyIsSelfIntersecting(Polygon* poly)

O(n^2)

Checks if the polygon is self-intersecting. Returns C3DLAS_TRUE or C3DLAS_FALSE.

Geometric Tests

// returns 1 if the polygon needs a more precise check, and 0 if the polygon is definitely farther away than the radius int polyCheckMaybeWithinRadius(Polygon* poly, vec2 p, float radius);

int polyCheckMaybeWithinRadius(Polygon* poly, vec2 p, float radius)

O(1)

Checks if the test point maybe is or definitely is not within a distance of radius outside of the polygon. Internally it does a basic check against centroid and maxRadiusSq. Returns C3DLAS_TRUE or C3DLAS_FALSE. Centroid and maxRadiusSq must be valid; GIGO.

// like the scalar one, but logical-OR's all the points' results

int mm8_polyCheckMaybeWithinRadius_group(Polygon* poly, float px[8], float py[8], float radius) int mm16_polyCheckMaybeWithinRadius_group(Polygon* poly, float px[16], float py[16], float radius) int mm32_polyCheckMaybeWithinRadius_group(Polygon* poly, float px[32], float py[32], float radius)

O(1)

These functions use AVX SIMD code, if available, to run the polyCheckMaybeWithinRadius algorithm with the same polygon on 8, 16, or 32 test points at the same time for approximately the same cost as a single call to polyCheckMaybeWithinRadius(), and performs a logical OR on the results. If SIMD intrinsics are not supported, these functions automatically degrade to whatever is supported.

int polyContainsPoint(Polygon* poly, vec2 p)

O(n)

Returns C3DLAS_TRUE or C3DLAS_FALSE depending on if the point is inside the polygon. I don't know how it handles self-intersecting polygons as I never use them.

float polyDistToPoint(Polygon* poly, vec2 p)

O(n)

Returns the distance from p to the closest point on the polygon. Interior distances are negative.

void mm8_polyDistToPoint(Polygon* poly, float px[8], float py[8], float out[8]) void mm16_polyDistToPoint(Polygon* poly, float px[16], float py[16], float out[16]) void mm32_polyDistToPoint(Polygon* poly, float px[32], float py[32], float out[32])

O(n)

These functions use AVX SIMD code, if available, to run the polyDistToPoint algorithm with the same polygon on 8, 16, or 32 test points at the same time for approximately the same cost as a single call to polyDistToPoint(). If SIMD intrinsics are not supported, these functions automatically degrade to whatever is supported.

int polyCheckIntersect(Polygon* a, Polygon* b)

O(a*b)

Checks if the lines of the two polygons intersect, but does not detect if one polygon is entirely contained within the other. Complete containment can be checked separately if desired by checking if the first point of a is inside b or vice versa; if the polygons are not intersecting according to this function and one point of a is inside b, then all points of a are inside b. Returns C3DLAS_INTERSECT or C3DLAS_DISJOINT. Uses centroid and maxRadiusSq if valid for early rejection.

int polyIntersect(Polygon* a, Polygon* b, int (*out_fn)(vec2 p, long seg_a, long seg_b, void* data), void* out_data)

O(a*b)

Calls out_fn once on every pair of edges in a and b that have at least one intersection. If out_fn returns nonzero, polyIntersect returns that value immediately, otherwise zero. seg_a and seg_b are the index of the point starting the segment which contains one or more intersections. out_data is passed to out_fn as the last parameter.

float polyMinDistToPoly(Polygon* a, Polygon* b, int* a_is_inside_b)

O(a*b)

There are three scenarios:

The edges intersect; returns 0.
One polygon is fully inside the other; returns a negative distance to the closest edge.
Both polygons are fully outside each other; returns a positive distance of the closest approach.

a_is_inside_b is only meaningful when the return value is negative and indicates which one is inside the other.

Geometric Operations

void polySubdivide(Polygon* poly, int degree)

O(n)

Subdivides each segment into degree equal segments. Degrees of 1 or less make no sense.

void polyCombineClosePoints(Polygon* poly, float dist)

O(n)

Walks along poly and deletes the next point if it's within dist of the current one.

void polyExteriorUnion(Polygon* a, Polygon* b, Polygon* poly)

fucking complicated dynamic algorithm, at least O(a*b)

Creates a polygon representing a shrink-wrapped hull around the union of the two inputs. All internal holes that would have been created in the union are eliminated. Both polygons must be wound in the same direction. Returns C3DLAS_INTERSECT if the union was successful and C3DLAS_DISJOINT if they don't intersect. If it returns disjoint then out will be a copy of either a or b.

void polyUnSelfIntersect(Polygon* poly)

O(n^2)

Works like polyExteriorUnion(), except only with itself. It produces a polygon that is not self-intersecting, but not necessarily the optimal one from any given perspective.

void polyExtrude(Polygon* poly, float dist, Polygon* out)

O(n)

Creates a new larger polygon by moving each point along a line out from the center of each corner far enough to create dist perpendicular separation between the original polygon edge and the new one. Only works on convex polygons.

void polyExtrude2(Polygon* poly, float dist, Polygon* out)

O(n)

Creates a new larger polygon by breaking the original one into individual segments, moving them outward by dist, then adding new lines connecting those segments end to end. This can easily create self-intersecting polygons, so you should probably call polyUnSelfIntersect() on the result.

void polySortCCW(Polygon* poly)

O(n log n)

Calculates the centroid of all the points then does a radial sort around that point. Niche use; dosn't do what you might think it does. It was originally built to create polygons representing the road-intersections of a road network based on the end points of the road segments.