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
Screen Shot 2016-07-14 at 5.54.58 PM

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

Screen Shot 2016-07-14 at 5.57.53 PM

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:
Screen Shot 2016-07-14 at 6.02.29 PM
p,p1,p2,p3 are Point  constructed by the class below:
Screen Shot 2016-07-14 at 6.04.21 PM 1
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
Screen Shot 2016-07-14 at 6.06.19 PM
Solution took 11.66 ms

2.
Using Barycentric coordinate system
From stackoverflow:
Screen Shot 2016-07-14 at 6.20.13 PM
Screen Shot 2016-07-14 at 6.20.51 PM
I leave you the implementation of this method.

Advertisements