这个问题很有趣。我有另一个可行的想法，不同于这篇文章的其他答案。其原理是利用角度之和来判断目标是在内部还是外部。也就是圈数。

设x为目标点。让数组[0,1，....N]是该区域的所有点。用一条线将目标点与每一个边界点连接起来。如果目标点在这个区域内。所有角的和是360度。如果不是，角度将小于360度。

参考这张图来对这个概念有一个基本的了解:

我的算法假设顺时针是正方向。这是一个潜在的输入:

[[-122.402015, 48.225216], [-117.032049, 48.999931], [-116.919132, 45.995175], [-124.079107, 46.267259], [-124.717175, 48.377557], [-122.92315, 47.047963], [-122.402015, 48.225216]]

下面是实现这个想法的python代码:

def isInside(self, border, target):
degree = 0
for i in range(len(border) - 1):
    a = border[i]
    b = border[i + 1]

    # calculate distance of vector
    A = getDistance(a[0], a[1], b[0], b[1]);
    B = getDistance(target[0], target[1], a[0], a[1])
    C = getDistance(target[0], target[1], b[0], b[1])

    # calculate direction of vector
    ta_x = a[0] - target[0]
    ta_y = a[1] - target[1]
    tb_x = b[0] - target[0]
    tb_y = b[1] - target[1]

    cross = tb_y * ta_x - tb_x * ta_y
    clockwise = cross < 0

    # calculate sum of angles
    if(clockwise):
        degree = degree + math.degrees(math.acos((B * B + C * C - A * A) / (2.0 * B * C)))
    else:
        degree = degree - math.degrees(math.acos((B * B + C * C - A * A) / (2.0 * B * C)))

if(abs(round(degree) - 360) <= 3):
    return True
return False

我知道这是旧的，但这里是一个在Cocoa实现的光线投射算法，如果有人感兴趣的话。不确定这是最有效的方法，但它可能会帮助别人。

- (BOOL)shape:(NSBezierPath *)path containsPoint:(NSPoint)point
{
    NSBezierPath *currentPath = [path bezierPathByFlatteningPath];
    BOOL result;
    float aggregateX = 0; //I use these to calculate the centroid of the shape
    float aggregateY = 0;
    NSPoint firstPoint[1];
    [currentPath elementAtIndex:0 associatedPoints:firstPoint];
    float olderX = firstPoint[0].x;
    float olderY = firstPoint[0].y;
    NSPoint interPoint;
    int noOfIntersections = 0;

    for (int n = 0; n < [currentPath elementCount]; n++) {
        NSPoint points[1];
        [currentPath elementAtIndex:n associatedPoints:points];
        aggregateX += points[0].x;
        aggregateY += points[0].y;
    }

    for (int n = 0; n < [currentPath elementCount]; n++) {
        NSPoint points[1];

        [currentPath elementAtIndex:n associatedPoints:points];
        //line equations in Ax + By = C form
        float _A_FOO = (aggregateY/[currentPath elementCount]) - point.y;  
        float _B_FOO = point.x - (aggregateX/[currentPath elementCount]);
        float _C_FOO = (_A_FOO * point.x) + (_B_FOO * point.y);

        float _A_BAR = olderY - points[0].y;
        float _B_BAR = points[0].x - olderX;
        float _C_BAR = (_A_BAR * olderX) + (_B_BAR * olderY);

        float det = (_A_FOO * _B_BAR) - (_A_BAR * _B_FOO);
        if (det != 0) {
            //intersection points with the edges
            float xIntersectionPoint = ((_B_BAR * _C_FOO) - (_B_FOO * _C_BAR)) / det;
            float yIntersectionPoint = ((_A_FOO * _C_BAR) - (_A_BAR * _C_FOO)) / det;
            interPoint = NSMakePoint(xIntersectionPoint, yIntersectionPoint);
            if (olderX <= points[0].x) {
                //doesn't matter in which direction the ray goes, so I send it right-ward.
                if ((interPoint.x >= olderX && interPoint.x <= points[0].x) && (interPoint.x > point.x)) {  
                    noOfIntersections++;
                }
            } else {
                if ((interPoint.x >= points[0].x && interPoint.x <= olderX) && (interPoint.x > point.x)) {
                     noOfIntersections++;
                } 
            }
        }
        olderX = points[0].x;
        olderY = points[0].y;
    }
    if (noOfIntersections % 2 == 0) {
        result = FALSE;
    } else {
        result = TRUE;
    }
    return result;
}

您可以通过检查将所需点连接到多边形顶点所形成的面积是否与多边形本身的面积相匹配来实现这一点。

或者你可以检查从你的点到每一对连续的多边形顶点到你的检查点的内角之和是否为360，但我有一种感觉，第一种选择更快，因为它不涉及除法，也不计算三角函数的反函数。

我不知道如果你的多边形内部有一个洞会发生什么，但在我看来，主要思想可以适应这种情况

你也可以把问题贴在数学社区里。我打赌他们有一百万种方法

令人惊讶的是之前没有人提出这个问题，但是对于需要数据库的实用主义者来说:MongoDB对Geo查询提供了出色的支持，包括这个查询。

你需要的是:

db.neighborhoods。findOne({geometry: {$geoIntersects: {$geometry: { type: "Point"，坐标:["经度"，"纬度"]}}} })

communities是存储一个或多个标准GeoJson格式多边形的集合。如果查询返回null，则表示不相交，否则为。

这里有详细的记录: https://docs.mongodb.com/manual/tutorial/geospatial-tutorial/

在330个不规则多边形网格中，超过6000个点分类的性能不到一分钟，没有任何优化，包括用各自的多边形更新文档的时间。

Like David Segonds' answer suggests I use an approach of angle summation derived from my concave polygon drawing algorithm. It relies of adding up the approximate angles of subtriangles around the point to obtain a weight. A weight around 1.0 means the point is inside the triangle, a weight around 0.0 means outside, a weight around -1.0 is what happens when inside the polygon but in reverse order (like with one of the halves of a bowtie-shaped tetragon) and a weight of NAN if exactly on an edge. The reason it's not slow is that angles don't need to be estimated accurately at all. Holes can be handled by treating them as separate polygons and subtracting the weights.

typedef struct { double x, y; } xy_t;

xy_t sub_xy(xy_t a, xy_t b)
{
    a.x -= b.x;
    a.y -= b.y;
    return a;
}

double calc_sharp_subtriangle_pixel_weight(xy_t p0, xy_t p1)
{
    xy_t rot, r0, r1;
    double weight;

    // Rotate points (unnormalised)
    rot = sub_xy(p1, p0);
    r0.x = rot.x*p0.y - rot.y*p0.x;
    r0.y = rot.x*p0.x + rot.y*p0.y;
    r1.y = rot.x*p1.x + rot.y*p1.y;

    // Calc weight
    weight = subtriangle_angle_approx(r1.y, r0.x) - subtriangle_angle_approx(r0.y, r0.x);

    return weight;
}

double calc_sharp_polygon_pixel_weight(xy_t p, xy_t *corner, int corner_count)
{
    int i;
    xy_t p0, p1;
    double weight = 0.;

    p0 = sub_xy(corner[corner_count-1], p);
    for (i=0; i < corner_count; i++)
    {
        // Transform corner coordinates
        p1 = sub_xy(corner[i], p);

        // Calculate weight for each subtriangle
        weight += calc_sharp_subtriangle_pixel_weight(p0, p1);
        p0 = p1;
    }

    return weight;
}

因此，对于多边形的每一段，都形成一个子三角形，并计算点，然后旋转每个子三角形以计算其近似角度并添加到权重。

调用subtriangle_angle_approx(y, x)可以替换为atan2(y, x) / (2.*pi)，但是一个非常粗略的近似值就足够精确了:

double subtriangle_angle_approx(double y, double x)
{
    double angle, d;
    int obtuse;

    if (x == 0.)
        return NAN;

    obtuse = fabs(y) > fabs(x);
    if (obtuse)
        swap_double(&y, &x);

    // Core of the approximation, a very loosely approximate atan(y/x) / (2.*pi) over ]-1 , 1[
    d = y / x;
    angle = 0.13185 * d;

    if (obtuse)
        angle = sign(d)*0.25 - angle;

    return angle;
}

我认为这是迄今为止所有答案中最简洁的一个。

例如，假设我们有一个多边形，它带有多边形凹，看起来像这样:

大多边形顶点的二维坐标为

[[139, 483], [227, 792], [482, 849], [523, 670], [352, 330]]

方框顶点的坐标为

[[248, 518], [336, 510], [341, 614], [250, 620]]

空心三角形顶点的坐标为

[[416, 531], [505, 517], [495, 616]]

假设我们想要测试两个点[296,557]和[422,730]，如果它们在红色区域内(不包括边缘)。如果我们定位这两个点，它将是这样的:

显然，[296,557]不在读取区域内，而[422,730]在。

我的解决方案是基于圈数算法。下面是我只使用numpy的4行python代码:

def detect(points, *polygons):
    import numpy as np
    endpoint1 = np.r_[tuple(np.roll(p, 1, 0) for p in polygons)][:, None] - points
    endpoint2 = np.r_[polygons][:, None] - points
    p1, p2 = np.cross(endpoint1, endpoint2), np.einsum('...i,...i', endpoint1, endpoint2)
    return ~((p1.sum(0) < 0) ^ (abs(np.arctan2(p1, p2).sum(0)) > np.pi) | ((p1 == 0) & (p2 <= 0)).any(0))

要测试实现:

points = [[296, 557], [422, 730]]
polygon1 = [[139, 483], [227, 792], [482, 849], [523, 670], [352, 330]]
polygon2 = [[248, 518], [336, 510], [341, 614], [250, 620]]
polygon3 = [[416, 531], [505, 517], [495, 616]]

print(detect(points, polygon1, polygon2, polygon3))

输出:

[False  True]