Triangle Containment

Three distinct points are plotted at random on a Cartesian plane, for which $-1000 \le x, y \le 1000$, such that a triangle is formed.
Consider the following two triangles:
\begin{gather}
A(-340,495), B(-153,-910), C(835,-947)\\
X(-175,41), Y(-421,-714), Z(574,-645)
\end{gather}
It can be verified that triangle $ABC$ contains the origin, whereas triangle $XYZ$ does not.
Using triangles.txt (right click and ‘Save Link/Target As…’), 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.

For finding whether a given point is inside a triangle, we can use the method of barycentric coordinates or a more intuitive way of checking triangle areas.

Given any point P, it is inside the triangle ABC if it splits the triangle into three smaller triangles, each with non-negative area. This is based on the fact that if the point is outside the triangle, at least one of these areas will be negative.

Following this logic, the way to determine whether the origin is inside a triangle defined by points A(x1, y1), B(x2, y2), C(x3, y3) is to check that the following three conditions are all true:

“`
Area(ABC) = Area(0AB) + Area(0BC) + Area(0CA)

Area(0AB) = 0.5*abs(x1*y2 – x2*y1)

Area(0BC) = 0.5*abs(x2*y3 – x3*y2)

Area(0CA) = 0.5*abs(x3*y1 – x1*y3)
“`
Where “abs” indicates absolute value, and “Area(0AB)” means “the area of the triangle with points 0 (the origin), point A and point B.”

For every triangle in the file, calculate the areas as described above and check if all are non-negative.

Count the number of triangles for which this property holds, and you’ve found your answer.

In the example given:

“`
The three areas for triangle ABC are:

Area(0AB) = 0.5*abs((-340)*(-910) – (-153)*(495)) = 185050

Area(0BC) = 0.5*abs((-153)*(-947) – (835)*(-910)) = 542767.5

Area(0CA) = 0.5*abs((835)*(495) – (-340)*(-947)) = 253865
“`
All of these are positive, so the origin is within triangle ABC.

Please note: in order to accomplish this task, you’ll need to write a program or script that can automate these calculations and read the data from the triangles.txt file. This involves skills in a programming language such as Python, Java, or another language of your choice.

More Answers: