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 ≤ x, y ≤ 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?