In computational geometry, a non-degenerate point set is a collection of points where no three points are collinear — meaning no three points lie on the same straight line. Generating such sets is essential for algorithms that rely on "general position" assumptions, including Delaunay triangulation, convex hull computation, and Voronoi diagrams. This article walks through what non-degeneracy means, how to check for it, and how to generate a valid point set in C++.

What Is a Non-Degenerate Point Set?

A set of 2D points is called non-degenerate (or in general position) when no three points are collinear. Collinearity is the primary degeneracy in 2D. Three points (x1, y1), (x2, y2), and (x3, y3) are collinear if the triangle they form has zero area. You can test this using the cross product of the vectors formed by the three points:

area = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)

If the absolute value of this expression is zero (or below a tolerance threshold for floating-point arithmetic), the three points are collinear.

Collinearity Check in C++

Here is a function that checks whether three points are collinear using a small epsilon tolerance:

1#include <cmath>
2#include <vector>
3
4struct Point {
5    double x, y;
6};
7
8bool areCollinear(const Point& a, const Point& b, const Point& c, double eps = 1e-9) {
9    double area = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
10    return std::abs(area) < eps;
11}

The epsilon value 1e-9 is a practical threshold. For integer coordinates, you can use exact arithmetic and check for area == 0 instead.

Generating a Non-Degenerate Point Set

The strategy is to generate random points and reject any new point that would create a collinear triple with existing points. Here is a complete implementation:

1#include <iostream>
2#include <vector>
3#include <cstdlib>
4#include <ctime>
5#include <cmath>
6
7struct Point {
8    double x, y;
9};
10
11bool areCollinear(const Point& a, const Point& b, const Point& c, double eps = 1e-9) {
12    double area = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
13    return std::abs(area) < eps;
14}
15
16bool isNonDegenerate(const std::vector<Point>& points, const Point& candidate) {
17    int n = points.size();
18    for (int i = 0; i < n; ++i) {
19        for (int j = i + 1; j < n; ++j) {
20            if (areCollinear(points[i], points[j], candidate)) {
21                return false;
22            }
23        }
24    }
25    return true;
26}
27
28std::vector<Point> generateNonDegenerateSet(int count, double rangeMin, double rangeMax) {
29    std::vector<Point> result;
30    int maxAttempts = count * 1000;
31    int attempts = 0;
32
33    while ((int)result.size() < count && attempts < maxAttempts) {
34        double x = rangeMin + (double)rand() / RAND_MAX * (rangeMax - rangeMin);
35        double y = rangeMin + (double)rand() / RAND_MAX * (rangeMax - rangeMin);
36        Point candidate = {x, y};
37
38        if (isNonDegenerate(result, candidate)) {
39            result.push_back(candidate);
40        }
41        ++attempts;
42    }
43
44    return result;
45}
46
47int main() {
48    srand(static_cast<unsigned>(time(nullptr)));
49
50    int n = 20;
51    auto points = generateNonDegenerateSet(n, -100.0, 100.0);
52
53    std::cout << "Generated " << points.size() << " non-degenerate points:\n";
54    for (const auto& p : points) {
55        std::cout << "(" << p.x << ", " << p.y << ")\n";
56    }
57
58    return 0;
59}

The function generateNonDegenerateSet builds the point set incrementally. For each candidate, it checks all existing pairs to ensure no triple becomes collinear. The worst-case cost is O(n^3) collinearity checks, which is fine for sets up to a few hundred points.

Using Integer Coordinates for Exact Arithmetic

Floating-point comparisons introduce precision concerns. If your application allows it, use integer coordinates to avoid epsilon-based checks:

1struct IntPoint {
2    long long x, y;
3};
4
5bool areCollinearExact(const IntPoint& a, const IntPoint& b, const IntPoint& c) {
6    long long area = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
7    return area == 0;
8}

With integer coordinates in a bounded range, the cross product is computed exactly, eliminating false positives and false negatives from rounding.

Common Pitfalls

• Choosing an epsilon that is too large: A tolerance like 1e-3 rejects points that are close to collinear but not truly collinear, resulting in unnecessarily sparse point sets. Use 1e-9 or smaller for double-precision floats.
• Not handling duplicate points: Two identical points are trivially collinear with every other point. Always check for and reject duplicate coordinates before the collinearity test.
• Running out of candidates in a small range: If the coordinate range is too narrow relative to the number of points requested, the rejection rate becomes very high. Ensure the range is large enough to accommodate the desired point count.
• Using rand() for high-quality randomness: The C rand() function has limited randomness quality and range. For production code, prefer <random> facilities like std::mt19937 with std::uniform_real_distribution.
• Ignoring the cubic time complexity: The brute-force O(n^3) approach works for small sets but becomes impractical beyond a few hundred points. For large sets, consider perturbation-based methods that start with a grid and add small random offsets.

Summary

• A non-degenerate 2D point set has no three collinear points, which is required by many computational geometry algorithms.
• Collinearity is tested by computing the signed area of the triangle formed by three points — a zero area means the points are collinear.
• The generate-and-reject approach builds the set incrementally, checking each candidate against all existing pairs.
• Use integer coordinates when possible to avoid floating-point precision issues in collinearity checks.
• The brute-force algorithm runs in O(n^3) time, which is suitable for small sets but should be optimized with spatial indexing for larger inputs.