`Utils.isPointInPoly` should include boundary

[rob-myers]

When Pathfinding.findPath outputs navigable points, I'd expect every point to be a valid place to start another navpath.

This fails reasonably often for my programmatically constructed meshes. It can be fixed by patching Utils.isPointInPoly:

• replace pt.z < poly[j].z by pt.z <= poly[j].z.
• replace pt.z < poly[i].z by pt.z <= poly[i].z.

As far as I can tell, isPointInPoly is used to test point-in-triangle via the crossing number method. The link mentions that:

A standard convention is to say that a point on a left or bottom edge is inside, and a point on a right or top edge is outside. This way, if two distinct polygons share a common boundary segment, then a point on that segment will be in one polygon or the other, but not both at the same time. This avoids a number of problems that might occur, especially in computer graphics displays.

But including the boundary produces no problem in our use case. If two triangles "contain" the point, the one corresponding to the earlier node will always be picked.

[rob-myers]

So, my suggestion actually breaks the pathfinding. It produces extra invalid edges in the underlying directed graph.

I will try making the navmesh 2-sided and report back.

---

Update: Both Pathfinding.getGroup and Pathfinding.findPath depend on Utils.isPointInPoly. I believe findPath should actually use a point-in-polygon test which permits points on the boundary.

In my use-case I already know points are inside the navpoly, so I removed the (buggy) requirement from findPath that points are inside.

[donmccurdy]

I haven't run into this issue before, is there something about your usage that makes paths especially likely to start or end on triangle boundaries? It sounds like the ideal fix for isPointInPoly might be to have an optional flag for including the boundary?