Checking if point is in triangle - problems with precision

gwyllo

Checking if point is in triangle - problems with precision

in Contributed Library Questions • 2 years ago

Hi all,

I am trying to move agents from within one triangle to another in 2d. I am currently achieving this by looping through the triangles edges, checking for an intersection, and moving to the corrosponding edge on the new triangle. I then perform a containment check to see whether the agent should move in one of 2 directions.

However, I am getting some problems when my agent is very close to the triangles corner. Ideally I want to test for containment within the triangle by placing my agent on an edge of the triangle, and then moving it in each of the two possible vectors by an infinitesimally small amount to test containment, to avoid the possibility of the movement causing the agent to 'skip around the corner' of the triangle. But when I try scaling the vectors like so, the isInTriangle method doesnt return true. Any ideas?

     vel = N.copy();
     vel.rotate(angleA);

     //check to see if velocity pushes away from face
// - this is where things break, I cannot scale the vel
//vector to less than around 0.1 of a unit or things break.
//but ideally this is tiny, like 0.0001
     Vec2D push =loc.add(vel.scale(0.1));

     Vec2D a = onFace.a.to2DXY();
     Vec2D b = onFace.b.to2DXY();
     Vec2D c = onFace.c.to2DXY();

     if(push.isInTriangle(a,b,c)){
     }else{
       //reverse vector relative to edge
       vel = N.copy();
       vel.rotate(angleB);
     }

Here is a terrible sketch of the problem:

Thanks in advance.

Replies(3)

23947sdhfs

Re: Checking if point is in triangle - problems with precision

2 years ago

Here are a couple of references that discuss this ( 1) ( 2). One solution seems to be filtering for errors and - when they are likely - redoing using exact geometric computation. Would be great to hear what experienced people can recommend in this exact case.

...

davbol

Re: Checking if point is in triangle - problems with precision

2 years ago

Hmm, would like to help, but..

You didn't post the code for your vector class, particularly the isInTriangle() method, so how could anyone here possibly help??

Or is that someone else's lib? Either way, do you/they know/describe what method is used for the point-in-triangle test? There are several common methods (split tri into three around point, sum of areas == tri area? split tri into three around point, sum angles around point == 360? point's cross-product against three oriented line segs, on same side of all three? barycentric coords of point on 0..1? etc) with advanages/dis. Some need an "epsilon" or "error term" or "fudge factor" to remain stable, might be too big for your use? And/or is "inside" rigorously defined? What about a point exactly colinear with one of the edges (or with two edges, exactly at a vertex)? Would that be considered "inside" or "outside", and is that perhaps a source of confusion? And what does to2DXY() do? Are you working with 3D faces and projecting them to 2D for the point-in-tri test? If so, are you sure the projection is working as expected? Is there a Matrix class or equivalent to debug as well? How about your vector's add() scale() copy() rotate() (rotating by a variable "angleB" that you also didn't provide code for) methods, are those all working properly?

Far too many unknowns and possible sources for tiny errors to accumulate, impossible to say where problem lies.

gwyllo

Re: Re: Checking if point is in triangle - problems with precision

2 years ago

Hi davbol, apologies for the ambiguity I should have mentioned that all of these are toxiclibs Vec2D methods.I guess I am wondering if anybody knows a way to increase the precision of these methods, in particular the isInTriangle() one. If this is not possible I am going to have to write my own function for checking the containment within three points using a more precise collection of variables. Thank you very much for describing some algorithms for checking containment - these seem to be fairly straight forward to implement and I might give them a try using java doubles.

I am fairly confident everything else is o.k as it should be simple vector math. The case of coincidence shouldn't ever arise as the agent is spawned on the edge and then moved off it with the vel vector, and vel can never be parallel to the edge or this particular containment function wouldn't be called in the first place. I can post the rest of the code if someone thinks it would help, but there is quite a lot of it.

Thanks again.

Top Reply