Close

The Continuing Odyssey of the Angle Bisector Problem

A project log for Narcissus 12.0

This project will explore a number of issues that are involved in creating a personality for an interactive chat-bot or actual robot.

glgormanglgorman 7 days ago0 Comments

I asked Microsoft Co-pilot to write a C++ function that calculates the angle bisectors of an arbitrary triangle, without using branches or trig calls, and got this mess in response.  Can you see what is wrong here?  First of all, the response isn't in C++, but I am O.K., with that - I would just like an algorithm that works.  Second, there is some conditional logic, which I stated was not desired, i.e. if the dot product is non-negative do this, or else do that.  Lastly, the solution is of course completely wrong.  Care to see a solution that at least "appears to work", at least for now?  How about this one:

int triangle::generate_bisectors ()
{
    fpoint U1,U2,U3;
    MATH_TYPE d; 
    MATH_TYPE dx1,dx2,dx3,dy1,dy2,dy3;
    MATH_TYPE L1,L2,L3;
    MATH_TYPE c1,c2,c3,s1,s2,s3;
    // first find the sines and cosines
    // of the line segments that make up
    // the triangle
    dx1 = current[1].x-current[0].x;
    dx2 = current[1].x-current[2].x;
    dx3 = current[2].x-current[0].x;
    dy1 = current[1].y-current[0].y;
    dy2 = current[1].y-current[2].y;
    dy3 = current[2].y-current[0].y;

    L1 = sqrt((dx1*dx1)+(dy1*dy1));
    L2 = sqrt((dx2*dx2)+(dy2*dy2));
    L3 = sqrt((dx3*dx3)+(dy3*dy3));

    c1 = dx1*(1.0/L1);
    c2 = dx2*(1.0/L2);
    c3 = dx3*(1.0/L3);
    s1 = dy1*(1.0/L1);
    s2 = dy2*(1.0/L2);
    s3 = dy3*(1.0/L3);

    // now generate three points that
    // represent the directional unit
    // vectors for each line segment
    d = 1.0; // compass distance!
    U1.x = d*c1;
    U1.y = d*s1;
    U2.x = d*c2;
    U2.y = d*s2;
    U3.x = d*c3;
    U3.y = d*s3;

    // now generate the compass
    // points
    fpoint C1,C2,C3,C4,C5,C6;
    C1 = current[0]+U1;
    C4 = current[0]+U3;
    C2 = current[1]-U2;
    C5 = current[1]-U1;
    C3 = current[2]-U3;
    C6 = current[2]+U2;

    fpoint P0,P1,P2;
    // the directional unit vectors
    // can be used to find the midpint
    // of a line that besects an
    // isosceles triangle that forms
    // from the base of the "arrow"
    P0 = fpoint::midpoint (C1,C4);
    P1 = fpoint::midpoint (C2,C5);
    P2 = fpoint::midpoint (C3,C6);

    fline AP1,BP2,CP3;
    AP1 = fline (current[0],P0);
    BP2 = fline (current[1],P1);
    CP3 = fline (current[2],P2);

    J = fpoint::intersect (AP1,BC);
    K = fpoint::intersect (BP2,AC);
    L = fpoint::intersect (CP3,AB);

    return 0;
}

Here is the method in other words.  Using the Pythagorean identity, find the sines and cosines of each of the line segments.  Then generate a set of unit vectors that correspond to each line segment.  Add or subtract the unit vectors as appropriate to each vertex, to obtain a set of points equidistant from each vertex as if we were using a traditional compass.  Find the midpoint of each "little arrow" so generated.   Then generate a line segment that passes from each vertex through each compass midpoint, and then continue that line segment until it intersects the opposite side of the triangle.  Optimization is hopefully a job that can be carried out by any good modern compiler, yet I unrolled some operations like calculating the sine and cosine values for the normalized unit vector for each line segment.  Then I went ahead and used the implementations of some functions like midpoint and intersect in the point and fline classes which are defined elsewhere.  Finding the intersection of two lines, when they are defined in parametric form is pretty simple, by coding an implementation of Cramer's rule, like this:

fpoint fpoint::intersect (const fline &L1, const fline &L2)
{
  fpoint result;
  MATH_TYPE det,recip_det;
  det = L1.a*L2.b-L1.b*L2.a;
  if (det!=0)
  {
    recip_det = 1.0/det;
    result.x = (L1.b*L2.c-L1.c*L2.b)*recip_det;
    result.y = (L1.c*L2.a-L1.a*L2.c)*recip_det;
    result.m_bvalid = true;
  }
  else
  {
    result.m_bvalid = false;
  }
  return result;
}

Of course, this means that I broke my own rule against conditional expressions., but on any CPU that has branch prediction, the test should always succeed, that is if we are being given valid triangles, so the performance cost should be minimal if not zero in terms of execution time.  Or else, it could be #ifdef'd out in a more performance-based, and possibly in-lined version of the code.  Haven't tried it yet on the pipelined CORDIC solver that is built into the Parallax Propeller P2 chip, or else what writing my own tessellation and convex hull routines would look like, let's say CUDA style, that is to say, to bypass OpenGL for other, non-graphics related things, like vector fields in electricity and magnetism, fluid mechanics, etc.   Thus, the built-in methods are not always the best, the most desirable, or even useful, according to the situation.  Enjoy!

Discussions