Triangle and Point class for Project Euler

TrustyTony 0 1K Views

I have left my source of information as docstring comment on code side. If you want to solve the problem yourself do not run the code. This code actually gives the correct answer. I have not reacted to the border case comment in my formula source as it is quite common to consider on border part of inside. You can add the simple check with optional parameter for how to react to case, for example, if you need it.

As everybody have read carefully Python documentation, the source of Point object by namedtuple should be clear.

It is worth to notice the point of comparing floating point number to other with epsilon. Even there have been earlier discussion on topic.

Also notice that I have not avoided using the string as keyword parameter as the object type is str or BaseString, and it is OK to use those reserved words as keyword parameter names to make them more natural. Movie database can have attribute id, for example.

from __future__ import print_function, division
"""See Project Euler Problem 102 (http://projecteuler.net/index.php?section=problems&id=102) for the problem definition,
shortly we must determine which triangles contain the origin point.

Algorith used:

If a point P is inside triangle ABC, then

Area PAB+Area PBC +Area PAC=Area ABC

notice that if P is on the edge of AB, BC, or CA, the above hold. But effectively, one of the area PAB, PBC, PAC is 0 (so just make sure you check that).

if P is outside, the above equality does NOT hold...

How to determine area? you have two options:
1) Heron's theorem, involves sqrt, slower
2) the more perferred way is the cross products (or effectively, the half of absolute value of (sum of the down products minus the sum of up products))

for example, if A=(x1,y1) B=(x2,y2), C=(x3,y3)
Area= abs(x1*y2+x2*y3+x3*y1-x1*y3-x3*y2-x2*y1)/2

also you might want to be careful about floating point errors... instead of checking for strict inequality,
check for abs(b-a)<eps, where eps can be a small value, such as 1e-12 (0.000000000001)

Source:
http://compsci.ca/v3/viewtopic.php?t=6034"""
from  collections import namedtuple
Point = namedtuple('Point', 'x y')

origin = Point(0,0)
eps = 1e-12

class Triangle(object):
    def __init__(self, a = None, b = None, c = None, string = ""):
        if string:
            self.from_string(string)
        else:
            self.a = a
            self.b = b
            self.c = c

    def area(self):
        return abs(self.a.x * self.b.y +
                    self.b.x * self.c.y +
                    self.c.x * self.a.y -
                    self.a.x * self.c.y -
                    self.c.x * self.b.y -
                    self.b.x * self.a.y) / 2.0

    def is_inside(self, point):
        triangles = (Triangle(point, self.a, self.b), Triangle(point, self.b, self.c), Triangle(point, self.a, self.c))
#         print  sum(t.area() for t in triangles) , self.area()
        return abs(sum(t.area() for t in triangles) - self.area()) < eps

    def from_string(self, point_string):
        coords = map(float, point_string.strip().split(','))
        self.a, self.b, self.c  = Point(*coords[:2]), Point(*coords[2:4]),Point(*coords[4:])

    def __repr__(self):
        return 'Triangle({self.a}, {self.b}, {self.c})'.format(self = self)
    __str__ = __repr__

test = "Triangle(Point(x=-340, y=495), Point(x=-153, y=-910), Point(x=835, y=-947))"
assert repr(eval(test)) == test

print('Solution for Euler problem 102 is {0}'.format(sum(tri.is_inside(origin)
                                                for tri in (Triangle(string=line)
                                                for line in open('triangles.txt')))) )
# debug lines
# :#(Triangle(Point(-340,495),Point(-153,-910),Point(835,-947)), Triangle(Point(-175,41), Point(-421,-714), Point(574,-645))):
#     print('Origin inside %s: %s' % (tri, tri.is_inside(origin)))
#print( Triangle(Point(-340,495),Point(-153,-910),Point(835,-947)))
#print(str(Triangle(Point(-340,495),Point(-153,-910),Point(835,-947))))
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview