mapbox / mapbox-unity-sdk

Mapbox Unity SDK - https://www.mapbox.com/unity/
Other
725 stars 210 forks source link

PointInPolygon buggy if determining if point is nearly in the center of the polygon #1893

Open artoonie opened 1 year ago

artoonie commented 1 year ago

The current algorithm is based on https://stackoverflow.com/a/7123291 However, that algorithm fails when checking a point near the center of the polygon.

Just below that answer is https://stackoverflow.com/a/14998816 This algorithm succeeds.

Demo polygon and point to test:

List<Point2d<float>> polygon = new List<Point2d<float>>{
                new Point2d<float>(40.469151426877744f, -79.97085571289061f),
                new Point2d<float>(40.45164977337427f, -79.92227554321289f),
                new Point2d<float>(40.48756242251301f, -79.90819931030273f),
                new Point2d<float>(40.49330666411266f, -79.9361801147461f),
                new Point2d<float>(40.484298429826644f, -79.9614143371582f),
                new Point2d<float>(40.469151426877744f, -79.97085571289061f),
            };
Point2d<float> testPos = new Point2d<float>(40.48062f, -79.93482f);
PolygonUtils.PointInPolygon(pos, polygon.GetRange(0, 1))

This point is clearly in the polygon, but fails the PointInPolygon test.