如果你正在寻找一个java脚本库，有一个javascript谷歌maps v3扩展的Polygon类，以检测是否有一个点驻留在它里面。

var polygon = new google.maps.Polygon([], "#000000", 1, 1, "#336699", 0.3);
var isWithinPolygon = polygon.containsLatLng(40, -90);

谷歌扩展Github

这只适用于凸形状，但是Minkowski Portal Refinement和GJK也是测试一个点是否在多边形中的很好的选择。您使用闵可夫斯基减法从多边形中减去点，然后运行这些算法来查看多边形是否包含原点。

另外，有趣的是，你可以用支持函数更隐式地描述你的形状，它以一个方向向量作为输入，并输出沿该向量的最远点。这可以让你描述任何凸形状..弯曲的，由多边形制成的，或混合的您还可以执行一些操作，将简单支持函数的结果组合起来，以生成更复杂的形状。

更多信息: http://xenocollide.snethen.com/mpr2d.html

此外，game programming gems 7讨论了如何在3d中做到这一点(:

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;
}

简单的解决方案是将多边形划分为三角形，并按这里解释的那样对三角形进行测试

如果你的多边形是凸多边形，可能有更好的方法。把这个多边形看作是无限条线的集合。每一行将空间一分为二。对于每一个点，很容易判断它是在直线的一边还是另一边。如果一个点在所有直线的同一侧，那么它在多边形内。

这大概是一个稍微不那么优化的C代码版本，它来自于这个页面。

我的c++版本使用std::vector<std::pair<double, double>>和两个double作为x和y。逻辑应该与原始C代码完全相同，但我发现我的更容易阅读。我不能为表演说话。

bool point_in_poly(std::vector<std::pair<double, double>>& verts, double point_x, double point_y)
{
    bool in_poly = false;
    auto num_verts = verts.size();
    for (int i = 0, j = num_verts - 1; i < num_verts; j = i++) {
        double x1 = verts[i].first;
        double y1 = verts[i].second;
        double x2 = verts[j].first;
        double y2 = verts[j].second;

        if (((y1 > point_y) != (y2 > point_y)) &&
            (point_x < (x2 - x1) * (point_y - y1) / (y2 - y1) + x1))
            in_poly = !in_poly;
    }
    return in_poly;
}

原始的C代码是

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) {
    if ( ((verty[i]>testy) != (verty[j]>testy)) &&
     (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}

当我还是Michael Stonebraker手下的一名研究员时，我做了一些关于这方面的工作——你知道，就是那位提出了Ingres、PostgreSQL等的教授。

我们意识到最快的方法是首先做一个边界框，因为它非常快。如果它在边界框之外，它就在外面。否则，你就得做更辛苦的工作……

如果你想要一个伟大的算法，看看开源项目PostgreSQL的源代码的地理工作…

我想指出的是，我们从来没有深入了解过左撇子和右撇子(也可以表达为“内”和“外”的问题……

更新

BKB's link provided a good number of reasonable algorithms. I was working on Earth Science problems and therefore needed a solution that works in latitude/longitude, and it has the peculiar problem of handedness - is the area inside the smaller area or the bigger area? The answer is that the "direction" of the verticies matters - it's either left-handed or right handed and in this way you can indicate either area as "inside" any given polygon. As such, my work used solution three enumerated on that page.

此外，我的工作使用单独的函数进行“在线”测试。

.．.因为有人问:我们发现当垂直的数量超过某个数字时，边界盒测试是最好的——如果有必要，在做更长的测试之前做一个非常快速的测试……边界框是通过简单地将最大的x，最小的x，最大的y和最小的y放在一起，组成一个框的四个点来创建的……

另一个提示是:我们在网格空间中进行了所有更复杂的“调光”计算，都是在平面上的正点上进行的，然后重新投影到“真实”的经度/纬度上，从而避免了在经度180线交叉时和处理极地时可能出现的环绕错误。工作好了!