Calculate angle between two edges to create polygon

Question

Currently I am trying to create an algorithm that will create polygons from given edges, I ran into a problem with creating vectors between three points. The algorithm calculates the angle for the candidates for the next edge, looking for the one that has the smallest angle, but I've noticed that it does not always calculate the angle from the right place, so the overall result of the algorithm is that it takes the correct values (minimum) and sometimes chooses the wrong calculations. Here is my code to calculate that:

        public Edge GetEdgeWithLowestAngle(Point basePoint, Point headPoint, List<Edge> connectedEdges) 
        {
            var minValue = double.MaxValue;
            Edge minEdge = null;

            foreach (var edge in connectedEdges)
            {
                var radianAngle = CalculateAngle(headPoint, GetNextPoint(headPoint, edge), basePoint); 
                if (minValue > radianAngle)
                {
                    minValue = radianAngle;
                    minEdge = edge;
                }
            }
            
            return minEdge;
        }

        public double CalculateAngle(Point pointA, Point pointB, Point pointC)
        {
            Vector2 ab = new Vector2((float)(pointB.X - pointA.X), (float)(pointB.Y - pointA.Y));
            Vector2 ac = new Vector2((float)(pointC.X - pointA.X), (float)(pointC.Y - pointA.Y));

            var cosinus = Convert.ToDouble(Vector2.Dot(ab, ac) / (ab.Length() * ac.Length()));
            //var atanValue = Math.Atan2(pointB.Y - pointA.Y, pointB.X - pointA.X) - Math.Atan2(pointC.Y - pointA.Y, pointC.X - pointA.X); <- that's the second option, return nearly the same value
            return Math.Acos(cosinus);
        }

Where it suposed to calculate every angle like that for every edge (headPoint and connectedEdges are changing every iteration but basePoint is still):

But sometimes it doesn't - I discovered that in some case it took the opposite vector and did angle calculation to that. Am I missing something crucial at geometrical level because calculations seems to be fine (i've checked few times with calculator). My intuition telling me that the problem is with creation of vectors (ab, ac). My algorithm operates on edges which has standard points A and B with X,Y coordinates and for edges creates polygons (algorithm supposed to do as small as possible circle through edges and makes polygons from it).

A significant problem is the lack of constancy of the calculated angles - it seems that it is calculated differently for each new edge - it takes the outside angle, sometimes inside. Because of that algorithm cannot make circle and freezes. Hope I explained the problem and thank you for your attention! :)

Answer 1

The problem with using the dot product formula to calculate the angle between two vectors is, that it will always calculate the enclosed angle and loose the information about the direction of the sweep. Which means that it will always return min(angle,opposite angle). You can easily verify this by, for example, calculating the angle between (1,0) and (-1,1) vs. the angle between (1,0) and (-1,-1). Both return 3/4pi, whereas one would probably expect 5/4pi in the second case.

---

EDIT: My comments where somewhat imprecise: You have to apply the range normalization to each atan2 call and only then subtract them.

I have illustrated this with a simple python script:

import numpy as np
import math
import itertools as it
from tabulate import tabulate


# list of the 8 cardinal and intercardinal points
Ps = np.array([[1,0],[1,1],[0,1],[-1,1],[-1,0],[-1,-1],[0,-1],[1,-1]])

# converts radian to degree, for easier reasoning
def to_degree(alpha):
    return alpha*180/math.pi

# calculates the angle between the vector v and the (positive) x-axis
# result is in [0,2pi]
def get_angle(v):
    phi = math.atan2(v[1], v[0])
    if (phi < 0):
        phi += 2*math.pi
    return phi

# for each combination of two cardinal points (named B and C)
#   calculate the directed angle BAC (named phi) 
#   with A beeing the base point at [0,0].
# v1 is line segment AB
# v2 is line segment AC
# phi1 is angle between v1 and x-axis
# phi2 is angle betwwen v2 and x-axis
A = np.array([0,0])
data = []
for B, C in it.product(Ps, repeat=2):
    v1 = B-A
    v2 = C-A
    phi1 = get_angle(v1)
    phi2 = get_angle(v2)
    data.append((v1,to_degree(phi1),v2,to_degree(phi2),to_degree(phi2-phi1)))
     
print(tabulate(data, headers=["v1", "phi_v1", "v2", "phi_v2", "phi"]))

which prints

v1         phi_v1  v2         phi_v2    phi
-------  --------  -------  --------  -----
[1 0]           0  [1 0]           0      0
[1 0]           0  [1 1]          45     45
[1 0]           0  [0 1]          90     90
[1 0]           0  [-1  1]       135    135
[1 0]           0  [-1  0]       180    180
[1 0]           0  [-1 -1]       225    225
[1 0]           0  [ 0 -1]       270    270
[1 0]           0  [ 1 -1]       315    315
[1 1]          45  [1 0]           0    -45
[1 1]          45  [1 1]          45      0
[1 1]          45  [0 1]          90     45
[1 1]          45  [-1  1]       135     90
[1 1]          45  [-1  0]       180    135
[1 1]          45  [-1 -1]       225    180
[1 1]          45  [ 0 -1]       270    225
[1 1]          45  [ 1 -1]       315    270
[0 1]          90  [1 0]           0    -90
[0 1]          90  [1 1]          45    -45
[0 1]          90  [0 1]          90      0
[0 1]          90  [-1  1]       135     45
[0 1]          90  [-1  0]       180     90
[0 1]          90  [-1 -1]       225    135
[0 1]          90  [ 0 -1]       270    180
[0 1]          90  [ 1 -1]       315    225
[-1  1]       135  [1 0]           0   -135
[-1  1]       135  [1 1]          45    -90
[-1  1]       135  [0 1]          90    -45
[-1  1]       135  [-1  1]       135      0
[-1  1]       135  [-1  0]       180     45
[-1  1]       135  [-1 -1]       225     90
[-1  1]       135  [ 0 -1]       270    135
[-1  1]       135  [ 1 -1]       315    180
[-1  0]       180  [1 0]           0   -180
[-1  0]       180  [1 1]          45   -135
[-1  0]       180  [0 1]          90    -90
[-1  0]       180  [-1  1]       135    -45
[-1  0]       180  [-1  0]       180      0
[-1  0]       180  [-1 -1]       225     45
[-1  0]       180  [ 0 -1]       270     90
[-1  0]       180  [ 1 -1]       315    135
[-1 -1]       225  [1 0]           0   -225
[-1 -1]       225  [1 1]          45   -180
[-1 -1]       225  [0 1]          90   -135
[-1 -1]       225  [-1  1]       135    -90
[-1 -1]       225  [-1  0]       180    -45
[-1 -1]       225  [-1 -1]       225      0
[-1 -1]       225  [ 0 -1]       270     45
[-1 -1]       225  [ 1 -1]       315     90
[ 0 -1]       270  [1 0]           0   -270
[ 0 -1]       270  [1 1]          45   -225
[ 0 -1]       270  [0 1]          90   -180
[ 0 -1]       270  [-1  1]       135   -135
[ 0 -1]       270  [-1  0]       180    -90
[ 0 -1]       270  [-1 -1]       225    -45
[ 0 -1]       270  [ 0 -1]       270      0
[ 0 -1]       270  [ 1 -1]       315     45
[ 1 -1]       315  [1 0]           0   -315
[ 1 -1]       315  [1 1]          45   -270
[ 1 -1]       315  [0 1]          90   -225
[ 1 -1]       315  [-1  1]       135   -180
[ 1 -1]       315  [-1  0]       180   -135
[ 1 -1]       315  [-1 -1]       225    -90
[ 1 -1]       315  [ 0 -1]       270    -45
[ 1 -1]       315  [ 1 -1]       315      0