## Problem 102: Triangle containment

*Difficulty: Easy

Problem:

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 (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.

How to solve: Python 2

Well, you can use one of **two** ways below:

**1.**

In general, the simplest (and quite optimal) algorithm is checking on which side of the half-plane created by the edges the point is.

Here is the triangle formed by three points, p1,p2,p3 and the point p inside

If p inside the triangle, p has to be on the side of the half-plane created by edges: p1p2, p2p3, p1p3 .

Here’s how you calculate the sign value of a point and an edge of triangle

p inside the triangle created by three point p1,p2,p3 only if all signs value of p and p1p2, p2p3, p1p3 must be negative. Here is the checking function:

p,p1,p2,p3 are Point constructed by the class below:

Open the file, read line by line and perform checking, if p inside the triangle, increase the count variable. Finally, print out the count variable

Solution took 11.66 ms

2.

Using Barycentric coordinate system

From stackoverflow:

I leave you the implementation of this method.

## Reply