确定线段里面的多边形 [英] determine if line segment is inside polygon
问题描述
假设我们有凸多边形顶点
suppose we have convex polygon with vertices
(v0,v1,....vn)
我的目的是确定是否为给定的点 P（X，Y）任何线段连接这点与多边形的任何顶点是多边形内部或甚至提供两个点
my aim is to determine if for given point p(x,y) any line segment connecting this point and any vertices of polygon is inside polygon or even for given two point
p(x0,y0) `p(x1,y1)`
线段连接这两个点是多边形内部？ 我已搜查这个很多网站，但我仍然感到困惑，一般来说，我认为，我们必须比较顶点坐标，并通过规定一定的坐标，其中一点是小于或大于到另一点的坐标，我们就可以决定任何线段的位置，但我不知道如何正确是这样的，请帮我
line segment connecting these two point is inside polygon? i have searched many sites about this ,but i am still confused,generally i think we have to compare coordinates of vertices and by determing coordinates of which point is less or greater to another point's coordinates,we could determine location of any line segment,but i am not sure how correct is this,please help me
推荐答案
假设点 P 和凸多边形 N 顶点 V_1 到 V_n （N> 2）。
Assume a point P and a convex polygon with n vertices V_1 to V_n (n > 2).
由角相对其排序多边形的顶点到所选顶点，使得它们在顺时针或逆时针的顺序。多边形的边，然后 V_1 - ＆GT; V_2，V_2 - ＆GT; V_3，...，V_（正 - 1） - ＆GT; V_n，V_n - ＆GT; V_1 。
Sort the vertices of the polygon by their angle relative to a selected vertex, so that they are in clock-wise or counter-clockwise order. The edges of the polygon are then V_1 -> V_2, V_2 -> V_3, ..., V_(n-1) -> V_n, V_n -> V_1.
现在，每一个边缘，检查交叉产品的价值（V_（I + 1） - V_I）×（P - V-I）。现在 P 是多边形内IIF所有值都> = 0或所有的值是＆LT; = 0
Now, for every edge, check the value of the cross product (V_(i+1) - V_i) x (P - V_i). Now P is inside the polygon iif all the values are >= 0 or all the values are <= 0.
有在顶部$ C的好教程$ CR 以其中多边形不必是凸的更一般的问题。他们所做的就是从测试点发出射线检查多少边相交。
There's a good tutorial on TopCoder for the more general problem where the polygon doesn't have to be convex. What they do is send a ray from the test point and check how many edges it intersects.
注意：这里所用的叉积定义为（U1，U2）×（V1，V2）：=（U1 - V2）*（U2 - V1）
NOTE: The cross product used here is defined as (u1, u2) x (v1, v2) := (u1 - v2)*(u2 - v1)
这篇关于确定线段里面的多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
