compute_convex_hull_2d()

std::vector< glm::vec3 > MayaFlux::Kinesis::compute_convex_hull_2d	(	const std::vector< glm::vec3 > &	vertices,
		const glm::vec3 &	projection_normal = glm::vec3(0, 0, 1)
	)

Compute convex hull of vertex set (2D projection)

Parameters

vertices	Input vertex set
projection_normal	Normal of projection plane (default: Z-axis)

Returns

Vertices forming convex hull boundary (closed path)

Uses Graham scan on projected coordinates.

Definition at line 459 of file GeometryPrimitives.cpp.

{
    if (vertices.size() < 3) {
        return vertices;
    }
 
    glm::vec3 n = glm::normalize(projection_normal);
    glm::vec3 u;
 
    if (std::abs(n.z) < 0.9F) {
        u = glm::normalize(glm::cross(n, glm::vec3(0, 0, 1)));
    } else {
        u = glm::normalize(glm::cross(n, glm::vec3(1, 0, 0)));
    }
 
    glm::vec3 v = glm::cross(n, u);
 
    struct Point2D {
        glm::vec2 pos;
        size_t index;
    };
 
    std::vector<Point2D> points;
    points.reserve(vertices.size());
 
    for (size_t i = 0; i < vertices.size(); ++i) {
        glm::vec3 offset = vertices[i];
        float x = glm::dot(offset, u);
        float y = glm::dot(offset, v);
        points.push_back({ glm::vec2(x, y), i });
    }
 
    auto pivot_it = std::ranges::min_element(points,
        [](const Point2D& a, const Point2D& b) {
            if (std::abs(a.pos.y - b.pos.y) < 1e-6F) {
                return a.pos.x < b.pos.x;
            }
            return a.pos.y < b.pos.y;
        });
 
    std::swap(points[0], *pivot_it);
    Point2D pivot = points[0];
 
    std::sort(points.begin() + 1, points.end(),
        [&pivot](const Point2D& a, const Point2D& b) {
            glm::vec2 va = a.pos - pivot.pos;
            glm::vec2 vb = b.pos - pivot.pos;
 
            float cross = va.x * vb.y - va.y * vb.x;
            if (std::abs(cross) < 1e-6F) {
                return glm::length(va) < glm::length(vb);
            }
            return cross > 0.0F;
        });
 
    // Graham scan
    std::vector<size_t> hull;
    hull.push_back(points[0].index);
    hull.push_back(points[1].index);
 
    auto ccw = [](const glm::vec2& a, const glm::vec2& b, const glm::vec2& c) {
        return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) > 0.0F;
    };
 
    for (size_t i = 2; i < points.size(); ++i) {
        while (hull.size() >= 2) {
            size_t top = hull.back();
            size_t second = hull[hull.size() - 2];
 
            glm::vec2 p1 = points[second].pos;
            glm::vec2 p2 = points[top].pos;
            glm::vec2 p3 = points[i].pos;
 
            if (ccw(p1, p2, p3)) {
                break;
            }
            hull.pop_back();
        }
        hull.push_back(points[i].index);
    }
 
    std::vector<glm::vec3> result;
    result.reserve(hull.size() + 1);
 
    for (size_t idx : hull) {
        result.push_back(vertices[idx]);
    }
 
    result.push_back(vertices[hull[0]]);
 
    return result;
}

References a, and b.