0

I am a brand-new student of C++ and working through some of the practice exercises in a book called Engineering Problem Solving with C++ by Dolores Etter.

I'm currently stuck on an exercise where I have to write a program that determines if a given point lies inside or outside of a defined triangle.

In my approach, I used Heron's formula for the area of a triangle based on the lengths of its sides. In my program the sides (and subsequently, the area) of the triangle in questions are constructed via 3 defined points A, B, and C, and then a given point 'P' (called "input") is used to construct triangles PAB PAC and PBC.

The idea is that if the area of PAB + PAC + PBC = Area of ABC, then the point must be inside the triangle.

I went pretty carefully through the equations that I used, calculating it all out by hand, and I cannot see why the program keeps returning the wrong answer.

For instance, it tells me that for A (0,0), B (0,3), and C (3,0), that input (1,1) is outside the triangle. Which is not true.

I am totally new to this and have no idea what is wrong. Can you take a look at the code and tell me what my error might be?

#include <iostream>
#include <cmath>

using namespace std;

struct Point {
    double x, y;
    auto operator - (Point const &that) const -> double {
        double yy = y - that.y;
        double xx = x - that.x;
        return sqrt(xx * xx + yy * yy);
    }
};

int main() {
    Point A{0,0}, B{0,3}, C{3,0}, input{1,1.25};
    double AreaMain, AreaPAB, AreaPBC, AreaPAC;
  
    double lengthAB = (A - B);
    double lengthAC = (A - C);
    double lengthBC = (B - C);
    
    double lengthPA = (input - A);
    double lengthPB = (input - B);
    double lengthPC = (input - C); 
    
    double semipMain = (lengthAB + lengthAC + lengthBC)/2.0;
    double semipPAB = (lengthPA + lengthPB + lengthAB)/2.0;
    double semipPBC = (lengthPB + lengthPC + lengthBC)/2.0;
    double semipPAC = (lengthPA + lengthPC + lengthAC)/2.0;
    
    AreaMain = sqrt(semipMain*(semipMain - lengthAB)*(semipMain - lengthAC)*(semipMain - lengthBC));
    
    AreaPAB = sqrt(semipPAB*(semipPAB - lengthPA)*(semipPAB - lengthPB)*(semipPAB - lengthAB));
    AreaPBC = sqrt(semipPBC*(semipPBC - lengthPB)*(semipPBC - lengthPC)*(semipPBC - lengthBC));
    AreaPAC = sqrt(semipPAC*(semipPAC - lengthPA)*(semipPAC - lengthPC)*(semipPAC - lengthAC));

    if ((AreaPAB + AreaPBC + AreaPAC) == AreaMain)
        cout << "The given point is inside the triangle" << endl;    
    else
        cout << "The given point is outside the triangle" << endl;    
        
    return 0;
}

I think it must be something I don't know about the way C++ works, because the math has been verified! Is it something to do with the formula I am using for the semiperimeter of each triangle? An error implementing Heron's formula?

user3840170
  • 26,597
  • 4
  • 30
  • 62
Connor Becz
  • 17
  • 2
    Welcome to Stack Overflow! It sounds like you may need to learn how to use a debugger to step through your code. With a good debugger, you can execute your program line by line and see where it is deviating from what you expect. This is an essential tool if you are going to do any programming. Further reading: [How to debug small programs](http://ericlippert.com/2014/03/05/how-to-debug-small-programs/) and [Debugging Guide](http://idownvotedbecau.se/nodebugging/) – NathanOliver Jan 14 '22 at 21:24
  • 5
    Floating point numbers and exact equality is problematic. The results of floating point arithmetic can be imprecise, and little tiny differences are still differences. Usually you perform the comparison with an epsilon, a region in which the answer will be close enough. – user4581301 Jan 14 '22 at 21:26
  • 2
    You may be able to use this approach on paper, but in a program you've got to deal with the fact that the precision of the numbers stored is limited. Furthermore the approach is unnecessarily expensive to compute: To check if a point is in a triangle, simply check, if it's on the same side of one of the triangle sides as the opposite corner. You can do this by using the dot product with the normal. Let `(x, y)` be `(a - b)` then the a vector with the same direction as the normal is `n = (y, -x)` and you just need to check, if `n * (c - a)` and `n*(p - a)` have the same sign and repeat 3 times – fabian Jan 14 '22 at 21:29
  • *"I went pretty careful through the equations that I used, calculating it all out by hand"* -- a good step. Next, you should go pretty carefully through the instructions that the computer uses, checking the values produced at each step. (Stepping through your code with a debugger might help.) Where does the program diverge from your hand calculation? When you see where it diverges, see if you can preserve the bug while eliminating the earlier calculations. For example, if everything looks right until the `if`, try skipping all calculations and manually set the values of the `Area` variables. – JaMiT Jan 14 '22 at 22:01
  • _"The idea is that if the area of PAB + PAC + PBC = Area of ABC, then the point must be inside the triangle."_ This will only be reliable if the math you are doing has infinite precision. The math here does not. – Drew Dormann Jan 14 '22 at 22:31
  • 1
    [Is floating point math broken?](https://stackoverflow.com/questions/588004/is-floating-point-math-broken) should answer this at least in part, although there are some remarks to be made about your choice of algorithm and the Heron’s formula in particular. – user3840170 Jan 14 '22 at 23:05
  • Thanks for all of the great answers! I didn't realize some of the foibles of floating point data involved here and that was why it didn't work. I was able to implement a quick fix by changing the logic test from an equality test to an if(abs((PAB + PAC + PBC) - Area ABC) < 0.0001) statement. I am also going to look at the dot product method that you mentioned, fabian, since it looks interesting. Thanks again for your help! – Connor Becz Jan 15 '22 at 19:21

0 Answers0