donmccurdy / donmccurdy/three-pathfinding

`Utils.isPointInPoly` should include boundary

Open
#68 2 comments 0 reactions 0 assignees View on GitHub
bug
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.