Does a triangle contain the origin?

gerry87

I'm trying to do this puzzle from project euler, wondering could someone tell me if the method i'm trying is wrong?

I'm not looking for an answer, just maybe an example of when it wouldn't work?

Basically I was saying for the triangle ABC, look to see if the intersect of the line from A to the Origin and the line BC are both in the same quadrant, then the same for the other three points. If any of them show up in the same quadrant then it doesn't contain the origin.

Could this method work?

ArmCandyBaby

What two points specifically lie in the same quadrant? The intersection of the lines AO and BC and what other point? I might be missing something here but I don't think this method will work.

CJC86

Yeah, I don't quite understand your method either, but it doesn't sound correct.

If you form the equation of the line AB, then you can check if C and the origin are on the same side of the line by plugging them into the equation, and seeing if the results are both positive or both negative. I think this is what you need to use.

gerry87

I probably didn't explain it very well... time for pictures!

Basically I was thinking that if the line from any point to the origin, crosses the line between the other two points in the same quadrant as itself, then it can't contain the origin.

If all the points are around the origin, then for example it would look like this, so the red point is in a different quadrant to B


On the other hand, if the triangle doesn't contiain the origin then the red point would be in the same quadrant as B


Is that clearer?

I can't think of any examples of a case where it wouldn't work, but i'm not getting the right answe so I'm not sure is it my code or method.

ArmCandyBaby

Yeah that looks OK I think but remember to include the code where the intersection of AO and BC lies outside either B or C because they could be in different quadrants and still not contain the origin.

bnt

My first instinct is to work with the angles, from each vertex to the other two points and the origin, expressed in terms of absolute bearing. If the bearing to the origin is between the bearings to the other two points, in the case of all three vertices, then the origin must be inside the triangle. Let me fire up Gnumeric and we'll see ... it might be sufficient to do this for any two vertices, rather than all three?

ray giraffe

gerry87 wrote: »

I probably didn't explain it very well... time for pictures!

Basically I was thinking that if the line from any point to the origin, crosses the line between the other two points in the same quadrant as itself, then it can't contain the origin.

If all the points are around the origin, then for example it would look like this, so the red point is in a different quadrant to B


On the other hand, if the triangle doesn't contiain the origin then the red point would be in the same quadrant as B


Is that clearer?

I can't think of any examples of a case where it wouldn't work, but i'm not getting the right answe so I'm not sure is it my code or method.

Method looks good to me. Check you have dealt properly with special cases - where the origin is on an edge of the triangle, or the origin is a vertex.

bnt wrote: »

My first instinct is to work with the angles, from each vertex to the other two points and the origin, expressed in terms of absolute bearing. If the bearing to the origin is between the bearings to the other two points, in the case of all three vertices, then the origin must be inside the triangle. Let me fire up Gnumeric and we'll see ... it might be sufficient to do this for any two vertices, rather than all three?

Sufficient for two vertices I think. Would be more computationally expensive that the OP's solution, I believe.

gerry87

Cheers guys, got the answer. Kinda cheated with the special cases ray mentioned, there was only one special case so I got it to print it out and did it by hand, ah well!