Problem #102 concerns determining whether a point is within the triangle formed by a triple of coordinates. The question reads:
Project Euler Problem 102: Triangle containment 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.
I must confess, I am unsure whether my solution will get the correct answer for all possible inputs. Regardless, here is my solution:
Solution #1: Relative Position Approach
First I implemented two methods that determine whether an arbitrary line on the coordinate plane passes above or below and to the left or to the right of the origin. Using these methods, I could determine how the three lines formed by the sides of the triangle were positioned relative to the origin.
Next, I translated the triangle such that its new centroid was at the origin and performed the same operations to check how the translated triangle was positioned relative to the origin. Finally, I concluded that if the original relative position was equivalent to the translated relative position, the translation did not change whether the origin was within the triangle. Because in the second case, the origin is the centroid which is within the triangle, it can be concluded that the original triangle contained the origin. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Analytic Geometry Approach to Project Euler Problem #102
'''
import time
f = open("PE102Triangles.txt","r")
if f.mode=="r":
contents = f.readlines()
realContents = []
for x in contents:
coords = map(int, x.split(","))
realContents.append([[coords[0],coords[1]],[coords[2],coords[3]],[coords[4],coords[5]]])
else:
raise ValueError("Cannot read from file")
def containsOrigin(A,B,C):
d = aboveBelowOrigin(A, B)
e = aboveBelowOrigin(B, C)
f = aboveBelowOrigin(C, A)
g = leftRightOrigin(A, B)
h = leftRightOrigin(B, C)
i = leftRightOrigin(C, A)
return [[d,g],[e,h],[f,i]] == relCentroid(A, B, C)
def relCentroid(A,B,C):
centroidX = (A[0]+B[0]+C[0])/3.0
centroidY = (A[1]+B[1]+C[1])/3.0
newA = [A[0]-centroidX,A[1]-centroidY]
newB = [B[0]-centroidX,B[1]-centroidY]
newC = [C[0]-centroidX,C[1]-centroidY]
d = aboveBelowOrigin(newA, newB)
e = aboveBelowOrigin(newB, newC)
f = aboveBelowOrigin(newC, newA)
g = leftRightOrigin(newA, newB)
h = leftRightOrigin(newB, newC)
i = leftRightOrigin(newC, newA)
return [[d,g],[e,h],[f,i]]
def aboveBelowOrigin(A,B):
# Left = False, Right = True
c = A[0]
d = A[1]
e = B[0]
f = B[1]
if c==e and d==f:
return "ONLINE"
if(c==e):
return c>0
if c*f==d*e:
return "ONLINE"
if c>e:
return c*f>d*e
return c*f<d*e
def leftRightOrigin(A,B):
# Below = False, Above = True
c = A[0]
d = A[1]
e = B[0]
f = B[1]
if c==e and d==f:
return "ONLINE"
if(d==f):
return f>0
if c*f==d*e:
return "ONLINE"
if(d>f):
return e*d>c*f
return c*f>d*e
def projectEulerProblemOneHundredTwo(myList):
total = 0
for x in myList:
A = x[0]
B = x[1]
C = x[2]
if containsOrigin(A, B, C):
total+=1
return total
start = time.time()
print projectEulerProblemOneHundredTwo(realContents)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
228
--- 0.00690007209778 seconds ---
for input of given list of triangles.
'''
And with that, we’re done. This approach makes intuitive sense, but I am unsure how to prove that it will always get the correct solution. Regardless, it was more than efficient enough to check the 1000 triangles in this problem.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 