Polygon Convexity Check in C: Algorithm and Implementation

Convex Polygon Check in C: From Theory to Robust Implementation

Checking if a polygon is convex is a core task in computational geometry, essential for game engines, navigation systems, and computer graphics. Convex shapes process faster, making this check a key optimization step.

Geometric Foundation of the Algorithm

A polygon's convexity is determined by the direction of turns as you traverse its vertices. If all turns go the same way (left or right), it's convex. A change in direction means it's concave.

Turn direction is calculated for every three consecutive points A, B, C using the sign of the cross product:

cross = (B.x - A.x)(C.y - A.y) - (B.y - A.y)(C.x - A.x)

• cross > 0 — left turn
• cross < 0 — right turn
• cross = 0 — points are collinear

This formula gives the signed area of the parallelogram formed by vectors AB and AC. The sign shows if point C is "above" or "below" the direction from A to B.

Basic Data Structures

We start with structs for points and polygons. Vertices are dynamically allocated since the count is only known at runtime.

typedef struct {
    int x;
    int y;
} Point;

typedef struct {
    Point *vertices;
    int n;
} Polygon;

Creation and destruction functions manage this memory:

Polygon* CreatePolygon(int n) {
    Polygon *p = malloc(sizeof(Polygon));
    if (!p) return NULL;
    p->n = n;
    p->vertices = malloc(n * sizeof(Point));
    if (!p->vertices) {
        free(p);
        return NULL;
    }
    return p;
}

void DestroyPolygon(Polygon *p) {
    if (!p) return;
    free(p->vertices);
    free(p);
}

Orientation Function and Overflow Issues

The key Orient function computes the cross product. Using long long prevents overflow during coordinate multiplication, but even 64-bit types have limits.

long long Orient(Point a, Point b, Point c) {
    return (long long)(b.x - a.x) * (c.y - a.y) -
           (long long)(b.y - a.y) * (c.x - a.x);
}

For critical apps, add overflow protection:

#include <limits.h>

int SafeMul(long long a, long long b, long long *res) {
    if (a > 0 && b > 0 && a > LLONG_MAX / b) return 0;
    if (a > 0 && b < 0 && b < LLONG_MIN / a) return 0;
    if (a < 0 && b > 0 && a < LLONG_MIN / b) return 0;
    if (a < 0 && b < 0 && a < LLONG_MAX / b) return 0;
    *res = a * b;
    return 1;
}

long long OrientSafe(Point a, Point b, Point c) {
    long long p1, p2;
    if (!SafeMul((long long)b.x - a.x, (long long)c.y - a.y, &p1) ||
        !SafeMul((long long)b.y - a.y, (long long)c.x - a.x, &p2)) {
        // Overflow handling: returning 0 conflicts with collinearity
        // In practice, set an error flag or use __int128
        printf("OVERFLOW\n");
        exit(1);
    }
    return p1 - p2;
}

Important: Returning 0 on overflow is wrong since it also means collinear. Use an error flag or wider types in strict code.

Convexity Check Algorithm

The main IsConvex function checks the cross product sign for all vertex triplets. sign tracks the first non-zero turn direction.

int IsConvex(const Polygon *p) {
    int sign = 0;
    for (int i = 0; i < p->n; i++) {
        Point a = p->vertices[i];
        Point b = p->vertices[(i + 1) % p->n];
        Point c = p->vertices[(i + 2) % p->n];
        long long cross = Orient(a, b, c);
        if (cross == 0) continue; // Skip collinear points
        if (sign == 0) {
            sign = (cross > 0) ? 1 : -1; // Lock first direction
        } else if ((cross > 0 && sign < 0) || (cross < 0 && sign > 0)) {
            return 0; // Direction changed — not convex
        }
    }
    return 1; // All turns same direction
}

Key implementation features:

• % p->n wraps around for cyclic traversal.
• Collinear points (cross == 0) are skipped, fine for polygons with straight sections.
• O(n) time complexity, constant extra space.

Complete Program Example

This code shows a full app that reads polygons from stdin and analyzes them.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Structures and orientation functions (as above)
// ...

int ReadPolygon(Polygon *p) {
    for (int i = 0; i < p->n; i++) {
        if (scanf("%d %d", &p->vertices[i].x, &p->vertices[i].y) != 2) return 0;
    }
    return 1;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n < 3) {
        printf("INPUT ERROR: need at least 3 vertices\n");
        return 1;
    }
    Polygon *p = CreatePolygon(n);
    if (!p) {
        printf("MEMORY ERROR\n");
        return 1;
    }
    if (!ReadPolygon(p)) {
        printf("INPUT ERROR: invalid coordinates\n");
        DestroyPolygon(p);
        return 1;
    }
    printf(IsConvex(p) ? "CONVEX\n" : "NOT CONVEX\n");
    DestroyPolygon(p);
    return 0;
}

Practical Considerations and Limitations

The algorithm assumes vertices are in traversal order (clockwise or counterclockwise) and the polygon is simple (no self-intersections).

Key points:

• Collinearity handling: Skipping cross == 0 works for convex polygons with straight edges but might hide input errors.
• Overflow protection: Production code needs safe multiplication or __int128, especially for large coordinates.
• Performance: Base algorithm is O(n) optimal, but OrientSafe adds checks that slow it down. Pick based on input range.
• Applicability: For 2D polygons only. 3D needs face checks or volume sign analysis.
• Alternatives: Use libraries like CGAL or Boost.Geometry for complex cases, or GPU acceleration.

— Editorial Team