Efficiently determining whether a point is inside a triangle or on the edge WITHOUT DOUBLE PRECISION

How to determine whether a point lies inside of a triangle or on the edge efficiently, if possible with constant time. WITH NO DOUBLE PRECISION

Context:

The plane is two dimensional
Triangle is set according to three coordinate pairs Coord(int x, int y)
The bounds for coordinates are: [-2,000,000 , 2,000,000 ]
Triangle coordinates are assumed to be a valid triangle mesh
Test point is also an integer.

Visual example: Image link

Format example:

Triangle a(Coord(50000,50000),Coord(-4000,2000), Coord(300000,150000));

                               // Point  Result
a.test_point( 60000,  45000)   // G      true
a.test_point( 289500, 145500)  // F      true
a.test_point( 292000, 146000)  // E      false
a.test_point(-292000,-146000)  //-E      false
a.test_point( 260000, 134000)  // D      true

Solution

First notice that you can't escape computing the equations of the sides in a form or another, which is directly related to the classical "orientation test" (https://www.cs.cmu.edu/~quake/robust.html).

In your case, 64 bit integers will avoid overflow. And if the largest deltas do not exceed 46340, 32 bits are enough.

If 64 bits arithmetic is not available natively, I guess that you can implement a two-stage process that can make a decision when possible with 32 bits, and switch to 64 bits emulation when unavoidable.

A point is inside the triangle when the three orientation tests return the same sign. It is on the outline when one test returns 0 and the other two an inside condition. It is on a vertex when two tests return 0.

You may also consider this answer https://stackoverflow.com/a/21510010/1196549, though it must be adapted to integer arithmetic, with the same restrictions as above.

Also note that if you have many points to locate in a triangular mesh, the answer will be quite different.