donmccurdy / donmccurdy/three-pathfinding
`Utils.isPointInPoly` should include boundary
- Dominant language
- JavaScript
- Stars
- 1.4k
- Forks
- 140
- PR merge metrics
- No merged PRs in 30d
Description
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](http://geomalgorithms.com/a03-_inclusion.html).
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.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.