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

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

Written by on 23 June 2012

Topics: Project Euler

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?

13 Comments For This Post I'd Love to Hear Yours!

  1. Eman says:

    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???

  2. Kristian says:

    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

  3. Eman says:

    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]));

  4. Eman says:

    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]));

  5. Kristian says:

    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.

  6. Kal says:

    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.

  7. Kristian says:

    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.

  8. Tom Leslie says:

    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

  9. Kristian says:

    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.

  10. Tom Leslie says:

    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

  11. Kristian says:

    That part we agree on.

  12. Lou says:

    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.

  13. Jean-Marie Hachey says:

    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

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.