Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Faster point in convex polygon check #8

Open
Huite opened this issue Jul 27, 2023 · 0 comments
Open

Faster point in convex polygon check #8

Huite opened this issue Jul 27, 2023 · 0 comments

Comments

@Huite
Copy link
Collaborator

Huite commented Jul 27, 2023

Checking for separating planes instead of relying on Jordan ray theorem, something like this:

@nb.njit(inline="always")
def point_in_convex_polygon(p: Point, poly: FloatArray) -> bool:
    """Half-plane check."""
    positive = False 
    negative = False 
    length = len(poly)
    v0 = as_point(poly[-1])
    for i in range (length):
        v1 = as_point(poly[i])
        U = to_vector(p, v0)
        W = to_vector(v0, v1)
        if cross_product(U, W) > 0:
            positive = True
        else:
            negative = True
            
        if positive and negative:
            return False
        
        v0 = v1

    return True


@nb.njit(inline="always")
def point_in_convex_polygon_or_on_edge(p: Point, poly: FloatArray) -> bool:
    """Half-plane check."""
    positive = False 
    negative = False 
    length = len(poly)
    v0 = as_point(poly[-1])
    for i in range(length):
        v1 = as_point(poly[i])
        U = to_vector(p, v0)
        V = to_vector(p, v1)
        W = to_vector(v0, v1)
        
        twice_area = abs(cross_product(U, V))
        if twice_area < TOLERANCE_ON_EDGE:
            # Project the point onto W.
            W = to_vector(v0, v1)
            if W.x != 0.0:
                t = (p.x - v0.x) / W.x
            elif W.y != 0.0:
                t = (p.y - v0.y) / W.y
            else:
                # The vector has a length of zero. Skip.
                continue
            if 0 <= t <= 1:
                # Now it's on the edge.
                return True

        if cross_product(U, W) > 0:
            positive = True
        else:
            negative = True
            
        if positive and negative:
            return False

        v0 = v1
        U = V

    return True

This seems to be approximately two times faster than the current check. However, it's obviously less robust (cannot deal with concave polygons). Annoyingly (and expectedly), it reports different results for edge cases such as a point located on a vertex.
Given only moderate speed-up and less robustness, it's probably best to stick to the current implementation (also given status quo bias...).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant