[performance] How can I determine whether a 2D Point is within a Polygon?

Most of the answers in this question are not handling all corner cases well. Some subtle corner cases like below: ray casting corner cases This is a javascript version with all corner cases well handled.

/** Get relationship between a point and a polygon using ray-casting algorithm
 * @param {{x:number, y:number}} P: point to check
 * @param {{x:number, y:number}[]} polygon: the polygon
 * @returns -1: outside, 0: on edge, 1: inside
 */
function relationPP(P, polygon) {
    const between = (p, a, b) => p >= a && p <= b || p <= a && p >= b
    let inside = false
    for (let i = polygon.length-1, j = 0; j < polygon.length; i = j, j++) {
        const A = polygon[i]
        const B = polygon[j]
        // corner cases
        if (P.x == A.x && P.y == A.y || P.x == B.x && P.y == B.y) return 0
        if (A.y == B.y && P.y == A.y && between(P.x, A.x, B.x)) return 0

        if (between(P.y, A.y, B.y)) { // if P inside the vertical range
            // filter out "ray pass vertex" problem by treating the line a little lower
            if (P.y == A.y && B.y >= A.y || P.y == B.y && A.y >= B.y) continue
            // calc cross product `PA X PB`, P lays on left side of AB if c > 0 
            const c = (A.x - P.x) * (B.y - P.y) - (B.x - P.x) * (A.y - P.y)
            if (c == 0) return 0
            if ((A.y < B.y) == (c > 0)) inside = !inside
        }
    }

    return inside? 1 : -1
}

Examples related to performance

Why is 2 * (i * i) faster than 2 * i * i in Java? What is the difference between spark.sql.shuffle.partitions and spark.default.parallelism? How to check if a key exists in Json Object and get its value Why does C++ code for testing the Collatz conjecture run faster than hand-written assembly? Most efficient way to map function over numpy array The most efficient way to remove first N elements in a list? Fastest way to get the first n elements of a List into an Array Why is "1000000000000000 in range(1000000000000001)" so fast in Python 3? pandas loc vs. iloc vs. at vs. iat? Android Recyclerview vs ListView with Viewholder

Examples related to graphics

How to play or open *.mp3 or *.wav sound file in c++ program? How to use graphics.h in codeblocks? How do I get the height and width of the Android Navigation Bar programmatically? How to Change Font Size in drawString Java How can I produce an effect similar to the iOS 7 blur view? Creating a blurring overlay view Saving images in Python at a very high quality Android: Background Image Size (in Pixel) which Support All Devices How to create a Rectangle object in Java using g.fillRect method Scaling a System.Drawing.Bitmap to a given size while maintaining aspect ratio

Examples related to collision-detection

IOS: verify if a point is inside a rect How do HashTables deal with collisions? JavaScript: Collision detection Circle line-segment collision detection algorithm? Circle-Rectangle collision detection (intersection) Ball to Ball Collision - Detection and Handling Collision Detection between two images in Java How can I determine whether a 2D Point is within a Polygon?

Examples related to polygon

How do CSS triangles work? Polygon Drawing and Getting Coordinates with Google Map API v3 A simple algorithm for polygon intersection How to determine if a list of polygon points are in clockwise order? How can I determine whether a 2D Point is within a Polygon?

Examples related to point-in-polygon

How can I determine whether a 2D Point is within a Polygon?