alecxe alecxe - 1 year ago 53
Python Question

Getting number of points in a 2D triangle

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?

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?