Here's an example algorithm that finds the smallest denominator point in the interior:

1. Take the triangle's center and denote D to be its denominator.
2. Find all horizontal lines with y-coordinate's denominator not greater than D and that have a chance of intersecting your triangle.
3. Same for vertical lines.
4. Intersect these line families, select points inside your triangle and minimize their denominator.

This does look like an *unsatisfying* algorithm, but then your problem might benefit from being phrased in a different way, perhaps 

*    Can we find the smallest denominator point in the interior using some beautiful O(D) algorithm? 

(where, presumably, D is the final answer)