CODEWITHSUNDEEP
algorithmgeometry
horace he
horace he

Reputation: 447

How to determine whether a point is inside a 2D convex polygon in faster than N time

I know the standard ray casting algorithm for finding whether a point is inside any polygon. However, is there a faster method if you limit yourself to just a convex polygon?

Upvotes: 2

Views: 2201

Answers (2)

S0paTa
S0paTa

Reputation: 51

As the answer stated, the algorithm is recursive. On each step you cut off the part of the polygon in which the point cannot be. Here is a C++ code:

#include "stdafx.h"
#include <vector>
#include <iostream>

struct vec2d {
    double x, y;
    vec2d(double _x, double _y) : x(_x), y(_y) {}
};

// Finds the cross product of the vectors: AB x BC
double crossProduct(vec2d pointA, vec2d pointB, vec2d pointC) {
    vec2d vectorAB = vec2d(pointB.x - pointA.x, pointB.y - pointA.y);
    vec2d vectorBC = vec2d(pointC.x - pointB.x, pointC.y - pointB.y);

    return vectorAB.x * vectorBC.y - vectorBC.x * vectorAB.y;
}

// Finds area for the triangle ABC
double S(vec2d A, vec2d B, vec2d C) {
    return crossProduct(A, B, C) / 2;
}

bool isPointInsideTriangle(vec2d A, vec2d B, vec2d C, vec2d point)
{
    return S(A, B, point) >= 0 && S(B, C, point) >= 0 && S(C, A, point) >= 0;
}

bool isPointAboveLine(vec2d A, vec2d B, vec2d point)
{
    return S(A, B, point) >= 0;
}

// O(logN), works only for convex polygons
bool isPointInsidePolygon(std::vector<vec2d> polygon, vec2d point) {
    if (polygon.size() == 3) {
        return isPointInsideTriangle(polygon[0], polygon[1], polygon[2], point);
    }

    if (isPointAboveLine(polygon[0], polygon[polygon.size() / 2], point)) {
        std::vector<vec2d> polygonAbove(polygon.begin() + polygon.size() / 2, polygon.end());
        polygonAbove.emplace(polygonAbove.begin(), polygon[0]);
        return isPointInsidePolygon(polygonAbove, point);
    }
    else {
        std::vector<vec2d> polygonBelow(polygon.begin(), polygon.begin() + polygon.size() / 2 + 1);
        return isPointInsidePolygon(polygonBelow, point);
    }
}

int main()
{
    std::vector<vec2d> convexPolygon;
    convexPolygon.push_back(vec2d(0, 2));
    convexPolygon.push_back(vec2d(2, 0));
    convexPolygon.push_back(vec2d(4, 1));
    convexPolygon.push_back(vec2d(6, 3));
    convexPolygon.push_back(vec2d(6, 4));
    convexPolygon.push_back(vec2d(5, 6));
    convexPolygon.push_back(vec2d(2, 6));
    convexPolygon.push_back(vec2d(1, 4));
    std::cout << isPointInsidePolygon(convexPolygon, vec2d(2, 5));

    return 0;
}

Upvotes: 0

ltjax
ltjax

Reputation: 15997

Yes, you can use binary search. You do this by recursively cutting the polygon into a fraction of its size (i.e. half) and checking on which side you are. For example, you can start by checking whether you are on the positive or negative side on the line going through vertex 0 and vertex n/2. Once you have 3 vertices, you simply test versus the remaining two sides, completing the test versus that triangle.

Here's some pseudo-code, that will hopefully make this easier to understand:

function TestConvexPolygon(point, polygon)
  if polygon.size == 3 then
    return TestTriangle(point, polygon) // constant time

  if (TestLine(point, polygon[0], polygon[polygon.size/2]) > 0)
    return TestConvexPolygon(point, new polygon from polygon.size/2 to polygon.size-1 and 0)
  else
    return TestConvexPolygon(point, new polygon from 0 to polygon.size/2)

Another way to visualize the idea is that you can view the polygon as a triangle-fan. You then start by testing your point versus the median interior edge. That will eliminate half of the possible triangles from the fan. Since half a triangle fan is still a triangle fan, you can do this recursively until you only have one triangle left in your fan, which you then test explicitly.

A real implementation needs some index juggling, but is otherwise easy and robust.

Upvotes: 7

Related Questions