Logarithmic's blog

Leftmost integer points on Triangle
By Logarithmic, history, 8 years ago, In English

Given 3 points of triangle, one of them is origin, coordinates of the other 2 are positive integers. I want to find the leftmost point inside triangle(could be on the edges of triangle). x_i, y_i <= 10^9. Is there any algorithm to solve this problem?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the leftmost point (as in smallest x-value, not sure what your definition is) is always going to be one of the vertices. Since your other two vertices both have positive coordinates, the leftmost point is always the origin.

→ Reply