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.
The Question:
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 efficient way to count the number of points in a triangle?
