c++polygonc++20computational-geometrytriangulation

How to calculate angle of two vectors for determining vertex concavity in ear clipping algorithm


I am trying to implement this ear clipping algorithm (from the pseudocode) here Currently at the point in the algorithm where I am trying to calculate the angle of each vertex in a polygon. I also got the idea of how to calculate the angles with vectors here: here This way I can also determine convexity/concavity. Also my vertices are in counter clockwise order.

This is a helper function I wrote to help in calculating the angle of each vertex:

void calcConvexity(Node&* prev, Node&* curr, Node&* next) {
    glm::vec2 u(0.0f), v(0.0f);
    u.x = curr->x - prev->x;
    u.y = curr->y - prev->y;
    v.x = curr->x - next->x;
    v.y = curr->y - next->y;
        
        // Calculating angle (in radians)
    curr->Angle =
        ((u.x * v.y) - (u.y * v.x))        
        /
        std::sqrt((std::pow(u.x, 2.0f) + std::pow(u.y, 2.0f)) * 
                std::sqrt(std::pow(v.x, 2.0f) + std::pow(v.y, 2.0f));

        // Convert to degrees
    curr->Angle = (180 / 3.141592653589793238463) * curr->Angle;

    if (curr->Angle < 180.0f)
        curr->isConvex = true; // The vertex is convex
    else
        curr->isConvex = false;
}

I was expecting most of the angles to come out between 0 and 360 but they did not. I am not sure what further calculations or corrections I need to make. Also, in the node class I have a boolean attribute called isConvex. I know something wrong is happening because every vertex is having there isConvex attribute set to true even when there degree is greater than 180.0f (in the example below).

Here is an actual example output as well: (The blue arrows are suppose to be facing in towards the nodes I just cant update the picture on here) Polygon With vectors to each vertice as well as the isConvex values for each node: Node isConvex Values and the angles: Node angle values

I have tried facing the vectors in different directions as well as using the GLM library for vector operations.

I apologize if any of what I have supplied is confusing, this is my first time messing with computational geometry in general. So I am just wondering what am I doing wrong in my calcConvexity method?

UPDATED CODE:

void calcConvexity(Node&* prev, Node&* curr, Node&* next) {
    glm::vec2 u(0.0f), v(0.0f);
    u.x = curr->x - prev->x;
    u.y = curr->y - prev->y;
    v.x = curr->x - next->x;
    v.y = curr->y - next->y;

    float CrossProduct = ((u.x * v.y) - (u.y * v.x));
    
    if (CrossProduct < 0)
        curr->isConvex = true; // The vertex is convex
    else
        curr->isConvex = false; // Otherwise concave
     
    curr->Angle =
        (CrossProduct)        
        /
        std::sqrt((std::pow(u.x, 2.0f) + std::pow(u.y, 2.0f)) * 
                std::sqrt(std::pow(v.x, 2.0f) + std::pow(v.y, 2.0f));

    curr->Angle = glm::degrees(std::asin(curr->Angle));
}

So the solution I came up with is this: I use the Cross product to determine convexity and then I use a slightly different angle formula: cos(curr->Angle) = (u.b) / (|u||v|) My main problem was the the formula with sin was outputting between -90 and 90 while the formula with cos outputs between 0 and 180 Code that works:

void Graph::calcConvexity(Node*& prev, Node*& curr, Node*& next) {
    glm::vec2 u(0.0f), v(0.0f);
    u.x = curr->x - prev->x;
    u.y = curr->y - prev->y;
    v.x = curr->x - next->x;
    v.y = curr->y - next->y;

    float CrossProduct = ((u.x * v.y) - (u.y * v.x));

    if (CrossProduct < 0)
        curr->isConvex = true; // The vertex is convex
    else
        curr->isConvex = false; // Otherwise concave

    float dotProduct = (u.x * v.x) + (u.y * v.y);

    curr->Angle =
        std::acos(dotProduct /
                (std::sqrt(std::pow(u.x, 2.0f) + std::pow(u.y, 2.0f)) *
                std::sqrt(std::pow(v.x, 2.0f) + std::pow(v.y, 2.0f))));

    curr->Angle = glm::degrees(curr->Angle);
}

Solution

  • curr->Angle appears to be set to sin(Angle) from u to v. Therefore concavity/convexity is determined by the sign of ((u.x * v.y) - (u.y * v.x)), since the denominator is always positive.

    In particular, if the interior of the polygon is on the right as traversing the vector u from its tail to its head, the positive sign of ((u.x * v.y) - (u.y * v.x)) corresponds to a convex angle.