-3

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
Reblochon Masque
  • 35,405
  • 10
  • 55
  • 80
Zechariah Kapustin
  • 11
  • 2
  • For point(x,y) and triangle(x1,y1,x2,y2,x3,y3), point is inside the triangle if: `abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))/2.0) == abs((x*(y2-y3) + x2*(y3-y)+ x3*(y-y2))/2.0) + abs((x1*(y-y3) + x*(y3-y1)+ x3*(y1-y))/2.0) + abs((x1*(y2-y) + x2*(y-y1)+ x*(y1-y2))/2.0)` – DimChtz Apr 28 '18 at 16:35
  • 1
    Possible duplicate of [How to determine if a point is in a 2D triangle?](https://stackoverflow.com/questions/2049582/how-to-determine-if-a-point-is-in-a-2d-triangle) – MBo Apr 28 '18 at 17:04
  • @DimChtz Doesn't produce correct results with sample data – Zechariah Kapustin Apr 28 '18 at 17:05
  • 2
    @DimChtz What do you mean by "Forget it"? – MBo Apr 28 '18 at 17:06
  • Are intermediate operations allowed using doubles/floats? – Ripi2 Apr 28 '18 at 17:52

2 Answers2

0

Any point inside the triangle with vertices (x1, y1), (x2, y2) and (x3, y3) can be represented by ((αx1 + βx2 + γx3), (αy1 + βy2 + γy3)) such that

α + β + γ = 1;

Since you're given the point (x, y), you get two more equations:

(αx1 + βx2 + γx3) = x

(αy1 + βy2 + γy3) = y

You've to check whether such (α, β, γ) exist. If yes, the point lies inside the triangle else outside. Use any standard method to check this.

EDIT: I assume by inside the triangle you mean on the perimeter too. If you want to it to be exclusively inside, then use a similar idea for line and check if it has a solution.

Laschet Jain
  • 734
  • 1
  • 8
  • 24
0

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.