确定线段内多边形

假设我们有个顶点确定线段内多边形

(v0,v1,....vn)

我的目的是确定凸多边形如果给定的点p(x,y)任何线段连接这点与多边形的任何顶点是多边形内部，甚至给定两点

p(x0,y0) `p(x1,y1)`

连接这两点的线段是在多边形内吗？我已经搜索了很多关于这个网站，但我仍然困惑，一般我认为我们必须比较顶点的坐标，并通过确定哪个点的坐标是较少或较大的另一个点的坐标，我们可以确定任何线段的位置，但我不知道如何正确是这样的，请帮我

来源

2012-08-31 dato datuashvili

你有一种语言？ – psubsee2003

你的意思是编程语言，它没关系，但确定C++ –

多边形是凸的吗？这将通过检查具有所有边缘的点的共线性使得任务几乎微不足道。对于一个普通的多边形，你可以使用某种扫描线算法 –

假设一个点P和凸多边形顶点n到V_1V_n（N> 2）。

按照它们相对于选定顶点的角度对多边形的顶点进行排序，以便它们按顺时针或逆时针顺序排列。多边形的边缘然后是V_1 -> V_2, V_2 -> V_3, ..., V_(n-1) -> V_n, V_n -> V_1。

现在，对于每个边缘，检查交叉产品(V_(i+1) - V_i) x (P - V_i)的值。现在P是多边形内IIF所有值都> = 0或所有值都< = 0

有一个很好的tutorial on TopCoder为更普遍的问题，其中多边形不一定是凸。他们所做的是从测试点发出一束光线，并检查它相交的边缘数。

注：这里所用的叉积定义为(u1, u2) x (v1, v2) := (u1 - v2)*(u2 - v1)

来源

2012-08-31 21:49:01

对不起，如何对多边形的边进行排序？ –

如果按顺时针或逆时针顺序给出顶点，则这已经为您完成了。如果不是，则可以采用一个顶点并通过它们与所选顶点之间的差异矢量的角度来排序其余顶点。 –

所以这意味着我必须计算两个顶点之间的角度然后排序？或者如何？ –

如果您的多边形是凸的，你添加一个新的起点，以它目前的多边形之外，就是要检查是否点它位于多边形的外部或内部，生成的多边形将凸出。实际上，这意味着上述格雷厄姆扫描不会失败，并且添加的点在多边形之外。

但是更快更好的方法是将点投影到多边形边缘的法线上。这依赖于分离平面定理。如果该点与该多边形的边缘之间存在一条线，则该线位于该外部。对于多边形的每个边缘取正常值。将点投影到该边的法线上。对所有法线执行此操作，并检查该点是否在该投影轴的多边形的最大和最小投影内。如果情况总是如此，则该点位于多边形内。如果失败，您可以停止，因为它是在一个分离的平面之外。

这将使算法运行在线性时间而不是O（n log n），因为您不必根据角度对顶点进行排序。当你有大量的顶点时，这是理想的。

来源

2017-06-28 13:51:31

确定线段内多边形

回答

相关问题