多边形被给定为Vector2I物品(2维,整数坐标)的列表。 如何测试一个给定的点在内部? 所有实现我在网络上找到失败的一些琐碎的反例。 这似乎真的是很难写一个正确实施。 语言并不重要,因为我将它移植自己。
Answer 1:
如果是凸起的,以检查它一个微不足道的方式是,该点上的所有段的相同侧铺设(如果遍历以相同的顺序)。
可以检查容易地与叉积(因为它正比于段和点,那些具有正号会躺在右侧和那些具有负号在左侧之间所形成的角的余弦)。
这里是在Python代码:
RIGHT = "RIGHT"
LEFT = "LEFT"
def inside_convex_polygon(point, vertices):
previous_side = None
n_vertices = len(vertices)
for n in xrange(n_vertices):
a, b = vertices[n], vertices[(n+1)%n_vertices]
affine_segment = v_sub(b, a)
affine_point = v_sub(point, a)
current_side = get_side(affine_segment, affine_point)
if current_side is None:
return False #outside or over an edge
elif previous_side is None: #first segment
previous_side = current_side
elif previous_side != current_side:
return False
return True
def get_side(a, b):
x = x_product(a, b)
if x < 0:
return LEFT
elif x > 0:
return RIGHT
else:
return None
def v_sub(a, b):
return (a[0]-b[0], a[1]-b[1])
def x_product(a, b):
return a[0]*b[1]-a[1]*b[0]
Answer 2:
光线投射或绕线方法是最常见的为这个问题。 见维基百科文章的详细信息。
此外,检查出这个网页为C中的证据充分的解决方案
Answer 3:
如果多边形是凸的,则在C#,以下实现“ 测试,如果总是在同一侧 ”的方法,并且至多运行在O(的多边形点N):
public static bool IsInConvexPolygon(Point testPoint, List<Point> polygon)
{
//Check if a triangle or higher n-gon
Debug.Assert(polygon.Length >= 3);
//n>2 Keep track of cross product sign changes
var pos = 0;
var neg = 0;
for (var i = 0; i < polygon.Count; i++)
{
//If point is in the polygon
if (polygon[i] == testPoint)
return true;
//Form a segment between the i'th point
var x1 = polygon[i].X;
var y1 = polygon[i].Y;
//And the i+1'th, or if i is the last, with the first point
var i2 = i < polygon.Count - 1 ? i + 1 : 0;
var x2 = polygon[i2].X;
var y2 = polygon[i2].Y;
var x = testPoint.X;
var y = testPoint.Y;
//Compute the cross product
var d = (x - x1)*(y2 - y1) - (y - y1)*(x2 - x1);
if (d > 0) pos++;
if (d < 0) neg++;
//If the sign changes, then point is outside
if (pos > 0 && neg > 0)
return false;
}
//If no change in direction, then on same side of all segments, and thus inside
return true;
}
Answer 4:
在OpenCV中的pointPolygonTest功能“确定点是否是轮廓内部,外部,或位于边缘”: http://docs.opencv.org/modules/imgproc/doc/structural_analysis_and_shape_descriptors.html?highlight=pointpolygontest#pointpolygontest
Answer 5:
FORTRAN的回答几乎是为我工作,除了我发现我有翻译的多边形,这样你正在测试的点是一样的起源。 下面是我写的,使这项工作的JavaScript的:
function Vec2(x, y) {
return [x, y]
}
Vec2.nsub = function (v1, v2) {
return Vec2(v1[0]-v2[0], v1[1]-v2[1])
}
// aka the "scalar cross product"
Vec2.perpdot = function (v1, v2) {
return v1[0]*v2[1] - v1[1]*v2[0]
}
// Determine if a point is inside a polygon.
//
// point - A Vec2 (2-element Array).
// polyVerts - Array of Vec2's (2-element Arrays). The vertices that make
// up the polygon, in clockwise order around the polygon.
//
function coordsAreInside(point, polyVerts) {
var i, len, v1, v2, edge, x
// First translate the polygon so that `point` is the origin. Then, for each
// edge, get the angle between two vectors: 1) the edge vector and 2) the
// vector of the first vertex of the edge. If all of the angles are the same
// sign (which is negative since they will be counter-clockwise) then the
// point is inside the polygon; otherwise, the point is outside.
for (i = 0, len = polyVerts.length; i < len; i++) {
v1 = Vec2.nsub(polyVerts[i], point)
v2 = Vec2.nsub(polyVerts[i+1 > len-1 ? 0 : i+1], point)
edge = Vec2.nsub(v1, v2)
// Note that we could also do this by using the normal + dot product
x = Vec2.perpdot(edge, v1)
// If the point lies directly on an edge then count it as in the polygon
if (x < 0) { return false }
}
return true
}
Answer 6:
我知道的方法是类似的东西。
你选择一个点的地方也可能是远离几何多边形之外。 然后你画从这个点线。 我的意思是你创建与这两个点的直线方程。
然后在这个多边形的每一行,你检查,如果他们相交。
它们相交的行数和给你这里面与否。
如果是奇数:内
如果是连:外
Answer 7:
或从写的书看man - 几何页
具体这个页面 ,他论述了为什么缠绕规则通常比线交叉更好。
编辑-抱歉,这并不是Jospeh奥罗克谁写的优秀图书用C计算几何 ,这是保罗·伯克但仍然是一个非常非常好的几何算法源。
文章来源: How to test if a point is inside of a convex polygon in 2D integer coordinates?