Project Euler 102: For how many triangles in the text file does the interior contain the origin?

Problem 102 of Project Euler asks us the following question

Three distinct points are plotted at random on a Cartesian plane, for which -1000 ≤ xy ≤ 1000, such that a triangle is formed.

Consider the following two triangles:

A(-340,495), B(-153,-910), C(835,-947)

X(-175,41), Y(-421,-714), Z(574,-645)

It can be verified that triangle ABC contains the origin, whereas triangle XYZ does not.

Using triangles.txt  a 27K text file containing the co-ordinates of one thousand “random” triangles, find the number of triangles for which the interior contains the origin.

NOTE: The first two examples in the file represent the triangles in the example given above.

This problem can be solved in a plethora of ways as far as I have seen. I like one particular solution though, which involves calculating the area of triangle and compare it to triangles containing the point P which we are testing if it is in the interior of the triangle.

Area = Area

We want to test if the triangle ABC contains the point P. The main concept of the solution is that the area of the triangle ABC is equal to the area of the triangles ABP + APC + PBC. I wont prove that it is true, but I have found Geogebra again and made a small applet you can play around with and convince yourself that it is indeed true.

You get the feeling for it now I assume?

Area of a triangle

The next thing we need is to calculate the area of the different triangles. Again there is a plethora of methods to do this. But since we have the coordinates of the corners we might as well utilize that.

Wikipedia is happy to inform us that such a formula exists. It is based on the determinant of the vertices.  Which in the general case will give us the following formula

where is the x coordinate of the A vertex of the triangle.

From here on it should be pretty simple.

Coding the solution

The majority of the code for this is made for parsing the input file, and the main file looks like

string[] lines = File.ReadAllLines(filename);
int result = 0;

foreach (string line in lines) {
    //Parse the line
    string[] segments = line.Split(',');
    int[,] coordinates = new int[2, segments.Length/2];

    int[] A = {Convert.ToInt32(segments[0]) ,
               Convert.ToInt32(segments[1])};
    int[] B = {Convert.ToInt32(segments[2]) ,
               Convert.ToInt32(segments[3])};
    int[] C = {Convert.ToInt32(segments[4]) ,
               Convert.ToInt32(segments[5])};
    int[] P = {0,0};

    if (area(A, B, C) ==
        area(A, B, P) +
        area(A, P, C) +
        area(P, B, C))
        result++;
}

The area function I have implemented as

private int area(int[] a, int[] b, int[] c) {
    return Math.Abs((a[0] - c[0])*(b[1] -a[1]) -
                    (a[0]-b[0])*(c[1]-a[1]));
}

As you can see I have removed the 1/2 factor in the front. Since we are not interested in the actual area, but only if they are equal the factor doesn’t have any function. By removing it I can avoid using floating point operations and therefor make the comparison more accurate.

Wrapping up

I have chosen a simple method to figure out if a point is inside a triangle. Besides being simple it is also rather fast. The execution of the problem gives us

 The number of Triangles containing (0,0): 228
 Solution took 2,5883 ms
 

You can find the complete source code here.

I think this method is pretty neat. However, there are many more methods. Blackpawn covers two of these methods. Another method is to measure the angles in the triangles made and so on. The big question is; How did you solve it?

Posted by Kristian

14 comments

Nice, I have read in your post that there is a formula for this problem.
My code was really inaccurate. Can you give me some hints how to search for information???

Hi Eman

I am uncertain what you refer to here. I think I cover the whole solution approach including the needed formulas.

If you want alternative solution strategies google is really your friend for this specific problem. Searching for something like “point in the interior of a triangle”. Will return several hits with good information.

If you mean something different with your question, please elaborate a bit more.

/Kristian

And also I can’t understand why the Area is calculated like this:

Math.Abs((a[0] – c[0])*(b[1] -c[1]) – (a[1]-c[1])*(b[0]-c[0]));

instead of this (like in the formula form wiki)

Math.Abs((a[0] – c[0])*(b[1] -c[1]) – (a[1]-c[1])*(b[0]-c[0]));

aaa sorry I posted it wrong it should be:

instead of this (like in the formula form wiki)

Math.Abs((a[0] – c[0])*(b[1] -a[1]) – (a[0]-b[0])*(c[1]-a[1]));

That looks more like a mistake than anything else. You can see that the formula I write is different from the code implementation. It is possible that you can write it both ways, but I think I should be consistent.

I will change that, and thanks for noticing.

It might be faster to use Barycentric Coordinates. Essentially, given triangle ABC, you get two vectors AB and AC and, for any point P, you write P = u(AB) + v(AC). If u and v are both in (0, 1) then P is in the interior of ABC.

I touched on Barycentric coordinates. However, I dismissed the idea for this one, I just don’t remember why. But you are certainly right that it is a valid way to go.

Don’t usually comment when we get the same answer, but the approaches described seem unnecessarily complicated? – so here was how I did it.

(Really important to understand steps 1-4 and this may be easierif you sketch the situation)

1) Any triangle has at least two vertices whose angles are less than
90 degrees (If all three are less than 90 degrees then just pick
any two.)
2) Draw the triangle with one of the two “acute” vertices at the
origin, and the other on the positive x-axis.
3) Ensure that the third vertex is in the positive-y quadrant (reflect
in the x-axis if necessary)
4) For a triangle drawn in this way it is really pretty trivial to
determine whether any other point lies inside

You have to be able to *get* this before it is worth reading the rest of this note

*********************************************************************

The problem then reduces to manipulating the starting triangle (and starting origin) to the required position. Algorithm is as follows

5) Use Pythagoras theorem to get all three side lengths
6) Use the cosine rule with the side lengths to get all three angles
(involves an arccos, but that isn’t going to kill anyone)
7) Pick one vertex whose angle is less than pi/2, and translate to
(0,0). Obviously all other vertices and the starting origin have
to be translated as well.
8) Pick another vertex whose angle is less than pi/2. Figure out its
angle relative to the x-axis (involves an arctan). Rotate
everything by this angle to bring the second vertex on to the
x-axis. Starting origin has now been translated and rotated.
9) Check whether the third triangle vertex is above or below the
x-axis. If below, then reflect it in the x-axis – if third vertex
is reflected, then the translated, rotated, starting origin has to
be reflected as well

*********************************************************************

Steps (5)-(9) may sound complicated but they really are very simple matrix manipulations. Translation is a matrix-add, rotation is a matrix-multiply, and reflection in x-axis is a sign change on the y-value

rgds
Tom

Hi Tom

First of all thanks for providing an alternative solution to mine. It is always a great learning experience for me to see how other people think.

I don’t necesarily agree with you, that your method is easier, taking into account that you have to find the angle, translate and rotate the points. Afterall I just calculate the sum of 4 triangles using a standard formula.

But what I do agree with you, is that it is probably easier to deduce if you sit down with pen and paper and start drawing.

Mmmmmm,

Probably explained myself badly – I was trying to focus on the issue of “conceptually” simple/complicated.

Assume that the original problem had been posed something like:

#####################################################################
Given a set of triangles with one vertext at the origin, one edge along the positive x-axis, where both vertices on the x-axis are guaranteed acute-angled and the third vertex is guaranteed to be in the positiveX,positiveY quadrant. Now given a “more-or-less-random-point”, does it lie within the triangle or not?
#####################################################################

Stated this way the problem would be too trivial for ProjectEuler.

Which method would you have used to solve this revised problem?

My point was that it was simple to produce this revised situation by simple geometric manipulation of the original problem: translate, rotate, and if necessary reflect – all of which are “conceptually” simple (and as it happens computationally trivial)

Sometimes conceptually simple is good – and sometimes it isn’t. I just happen to think that this is one of the cases where the “conceptually” simple wins

rgds
Tom

That part we agree on.

That’s a nice solution. It might even be simpler than my solution.

It is possible in coordinate geometry to take a line (x1 y1 x2 y2) and a point (x,y) and test where that point lies in relation to the line. Specifically, you can do this test on a given line for two different points, and determine whether both points are on the same side of the line, or different sides. How to do this:
(x-x1)(y2-y1) – (y-y1)(x2-x1)
Perform this calculation on both points. If both results are positive (or negative) then they are on the same side of the line. Otherwise they are on different sides.

How does this help solve problem 102? Well, a triangle is made of three lines. Each of those lines connects 2 of the points of the triangle, and the third lies on a particular side of that line. If the origin lies on the other side of that line, then the origin is not within the triangle. It’s simple enough to verify with pen & paper that if a point is on the same side as the third point for all three lines, then it must lie within the triangle.

Solution: check all three lines of each triangle and test whether the origin is on the same side as the third point. Because we’re checking the origin (x,y = 0), the formula simplifies somewhat:

for every triangle x1 y1 x2 y2 x3 y3
if ((x1-x2)(y3-y2) - (y1-y2)(x3-x2))(x3.y2-y3.x2) is less than 0 then continue
if ((x2-x1)(y3-y1) - (y2-y1)(x3-x1))(x3.y1-y3.x1) is less than 0 then continue
if ((x3-x1)(y2-y1) - (y3-y1)(x2-x1))(x2.y1-y2.x1) is less than 0 then continue
answer + 1

A pretty simple solution that only uses integer calculations.

Jean-Marie Hachey

One way to determine if a point P of coordinates (xp, yp) is inside or outside of a triangle ABC, is to calculate the vector cross products of the three vertices of the triangle (xa, ya), (xb, yb), (xc, yc) :

(xa-xp)*(yb-yp) – (ya-yp)*(xb-xp)
(xb-xp)*(yc-yp) – (yb-yp)*(xc-xp)
(xc-xp)*(ya-yp) – (yc-yp)*(xa-xp)

___

Table 1
Vector cross products for a series of triangles vertices and a point P
at origin (0,0).
Re: Project Euler – Problem 102
« For how many triangles in the text file does the interior contain the origin? »

http://img4.hostingpics.net/pics/816247pe102tableone.jpg

If the vector cross products are all positive or negative; then, point P is inside the triangle.
If the vector cross products are of different signs then point P is outside the triangle.

All the results in Table 1 were calculated with Excel (4).

___

Sources:
1) Project Euler – Problem 102
Data source
http://projecteuler.net/project/triangles.txt
2) Project Euler – Problem 102
Kristian’s algorithm
http://www.mathblog.dk/files/euler/Problem102.cs
3) Microsoft Visual C# 2010 Express
4) Microsoft Office Excel (2007)
5) Microsoft Office Word (2007)
6) Project Euler – Problem 102
http://www.tushar-mehta.com/misc_tutorials/project_euler/euler102.html
7) Caractériser tout point à l’intérieur d’un triangle quelconque
http://forums.futura-sciences.com/mathematiques-superieur/521026-caracteriser-point-a-linterieur-dun-triangle-quelconque.html

Carl J Appellof

Nice solution! I went about it a different way. Calculated the slope-intercept of each line segment of the triangle and whether the segment crosses the y axis. If one crosses the y axis at a positive y coordinate and another crosses the y axis at a negative coordinate, the triangle contains the origin. Otherwise it doesn’t. Eliminating the time it takes to read the data, My method is a little slower than yours on my computer. Not a lot of difference, though.

Leave a Reply