alecxe - 1 year ago 59

Python Question

**The Story:**

*Input:*3 coordinates - the vertices of a triangle*Desired Output:*number of points with*integer coordinates*located inside a triangle, not including boundaries

My initial idea was to get the coordinates of the rectangle containing the triangle, iterate over the points inside it and use one of the "Is this point inside a triangle?" solutions to determine if a point is inside a triangle. What I have so far:

`from collections import namedtuple`

from operator import attrgetter

def is_inside_triangle(s, p1, p2, p3):

as_x = s.x - p1.x

as_y = s.y - p1.y

s_ab = (p2.x - p1.x) * as_y - (p2.y - p1.y) * as_x > 0

if ((p3.x - p1.x) * as_y - (p3.y - p1.y) * as_x > 0) == s_ab:

return False

if ((p3.x - p2.x) * (s.y - p2.y) - (p3.y - p2.y) * (s.x - p2.x) > 0) != s_ab:

return False

return True

def solution(vertices):

Point = namedtuple('Point', 'x,y')

vertices = [Point(x, y) for x, y in vertices]

min_x = min(vertices, key=attrgetter('x')).x

min_y = min(vertices, key=attrgetter('y')).y

max_x = max(vertices, key=attrgetter('x')).x

max_y = max(vertices, key=attrgetter('y')).y

return sum(1

for x in range(min_x + 1, max_x)

for y in range(min_y + 1, max_y)

if is_inside_triangle(Point(x, y), *vertices))

It works for the following inputs:

`print(solution([(-1, -1), (1, 0), (0, 1)])) # 1`

print(solution([[3, 3], [4, 2], [10, 190]])) # 96

This approach though proved to be very slow on large enough triangles, like:

`print(solution([[91207, 89566], [-88690, -83026], [67100, 47194]]))`

which works for hours.

I think the main problem is that I am trying to check too many points that can be ruled out beforehand. What is the most

Answer Source

The word "point" seems very inaccurate to me, the number of *points* is infinite in most cases. Do you mean number of "pixels"? Then why not use the equation for triangle area, e.g. `abs((xB*yA-xA*yB)+(xC*yB-xB*yC)+(xA*yC-xC*yA))/2`

, measured in pixels?