how to implement point in polygon to the search

[xushaomin]

how to implement point in polygon to the search!

[davidmoten]

Search on the bounding box of the polygon then refine the returned results. If the polygon is a weird shape you might even choose to cover it with multiple bounding boxes to search more efficiently.

[DusonWang]

@xushaomin
public boolean searchPoint(Point point) {

    if (CollectionUtils.isEmpty(corner)) {
        return false;
    }

    float x = point.x();
    float y = point.y();
    int points = corner.size();
    int hits = 0;
    float lastX = corner.get(points - 1).getPolyX();
    float lastY = corner.get(points - 1).getPolyY();
    float curX, curY;

    for (int i = 0; i < points; lastX = curX, lastY = curY, i++) {
        curX = corner.get(i).getPolyX();
        curY = corner.get(i).getPolyY();
        if (x == curX && y == curY) {
            return true;
        }

        if (curY == lastY) {
            continue;
        }

        float leftX;
        if (curX < lastX) {
            if (x >= lastX) {
                continue;
            }
            leftX = curX;
        } else {
            if (x >= curX) {
                continue;
            }
            leftX = lastX;
        }
        float test1, test2;
        if (curY < lastY) {
            if (y < curY || y >= lastY) {
                continue;
            }
            if (x < leftX) {
                hits++;
                continue;
            }
            test1 = x - curX;
            test2 = y - curY;
        } else {
            if (y < lastY || y >= curY) {
                continue;
            }
            if (x < leftX) {
                hits++;
                continue;
            }
            test1 = x - lastX;
            test2 = y - lastY;
        }

        if (test1 < (test2 / (lastY - curY) * (lastX - curX))) {
            hits++;
        }
    }
    return (hits & 1) != 0;
}