精华内容
下载资源
问答
  • 1. 线段的两个端点都在多边形内。 2.线段和多边形的所有边都不内交(交点在线段端点是可以的,但是在多边形顶点是不可以的)。 转载于:https://my.oschina.net/1024bits/blog/783118

    1. 线段的两个端点都在多边形内。

    2.线段和多边形的所有边都不内交(交点在线段端点是可以的,但是在多边形顶点是不可以的)。

    转载于:https://my.oschina.net/1024bits/blog/783118

    展开全文
  • 判断线段是否在多边形内:  线段在多边形内的一个必要条件是线段的两个端点都在多边形内,但由于多边形可能为凹,所以这不能成为判断的充分条件。  如果线段和多边形的某条边内交(两线段内交是指两线段相交且...

    判断线段是否在多边形内:

      线段在多边形内的一个必要条件是线段的两个端点都在多边形内,但由于多边形可能为凹,所以这不能成为判断的充分条件。

      如果线段和多边形的某条边内交(两线段内交是指两线段相交且交点不在两线段的端点),

      因为多边形的边的左右两侧分属多边形内外不同部分,所以线段一定会有一部分在多边形外(见图a)。

      于是我们得到线段在多边形内的第二个必要条件:线段和多边形的所有边都不内交。

      线段和多边形交于线段的两端点并不会影响线段是否在多边形内;

      但是如果多边形的某个顶点和线段相交,还必须判断两相邻交点之间的线段是否包含于多边形内部(反例见图b)。

        

      因此我们可以先求出所有和线段相交的多边形的顶点,

      然后按照X-Y坐标排序(X坐标小的排在前面,对于X坐标相同的点,Y坐标小的排在前面,这种排序准则也是为了保证水平和垂直情况的判断正确)

      这样相邻的两个点就是在线段上相邻的两交点,如果任意相邻两点中点也在多边形内,则该线段一定在多边形内。

      对应的算法如下:

    if 线端PQ的端点不都在多边形内 
          then return false;
        点集pointSet初始化为空;
        for 多边形的每条边s
          do if 线段的某个端点在s上
               then 将该端点加入pointSet;
             else if s的某个端点在线段PQ上
               then 将该端点加入pointSet;
             else if s和线段PQ相交 // 这时候已经可以肯定是内交了
               then return false;
        将pointSet中的点按照X-Y坐标排序;
        for pointSet中每两个相邻点 pointSet[i] , pointSet[ i+1]
          do if pointSet[i] , pointSet[ i+1] 的中点不在多边形中
               then return false;
        return true;


    Very Beautiful!



    转载于:https://www.cnblogs.com/o8le/archive/2011/11/15/2250076.html

    展开全文
  • 判断点(P)是否在多边形中,可以先以点p向左引一条射线(L),我们知道,从射线L左端的无穷远处开始一直到点P的过程中,当遇到多边形的第一个交点时L进入了多边形,当遇到第二个交点时,L穿出了多边形。。。。。。...

    昨天小学了一点计算几何学的内容,想把它记下来,以便以后翻阅。

    1.判断点是否在多边形中

    先说一下思路:

    判断点(P)是否在多边形中,可以先以点p向左引一条射线(L),我们知道,从射线L左端的无穷远处开始一直到点P的过程中,当遇到多边形的第一个交点时L进入了多边形,当遇到第二个交点时,L穿出了多边形。。。。。。。。。可知,规律如下,当在遇到P点之前L与多边形的交点为偶数个时,说明p点不在多边形内,当在遇到p点之前L与多边形得交点为奇数个时,说明P点在多边形内。

    但是,这个规律并不具有普遍性,还有几种特殊情况不满足此规律,需要额外考虑:

    (1)当点P在多边形的某条边上时,可以直接判断其在多边形中。

    (2)对于多边形的水平边不作考虑。

    (3)对于多边形的顶点与L相交,则需要判断该顶点是否为顶点所在的边的那个纵坐标较大的顶点,如果是较大的那个顶点与L相交则计数,否则忽略。

    伪代码如下:

    ........fun()
    {
         int count=0;
         //以P为端点从右向左引一条射线L 
         for(多边形的每一条边S)//遍历多边形的每一条边 
         {
              if(P在边S上)
              {
                   return ture; 
              } 
              if(S不是水平的)
              {
                    if(S的一个端点在L上)
                    {
                          if(该端点是S的较大端点)
                          {
                                count++; 
                          }                    
                    }               
                    else if(S与L相交)
                    {
                          count++;
                    } 
              } 
         } 
         if(count%2==0)
         {
               return false;
         }
         else
         {
               return true;
         }
    }

    2.判断线段是否在多边形内

    思路:(1)首先,要判断一条线段是否在多边形内,先要判断线段的两个端点是否在多边形内。如果两个端点不全在多边形内,那么,线段肯定是不在多边形内的。

            (2)其次,如果线段和多边形的某条边内交(两线段内交是指两线段相交且交点不在两线段的端点),则线段肯定不在多边形内。

            (3)如果多边形的某个顶点和线段相交,则必须判断两相交交点之间的线段是否包含于多边形内。

    伪代码:

    if(线段PQ的端点不都在多边形内)
    {
         return false;                              
    } 
    点集pointSet初始化为空;
    for(多边形的每一条边S)
    {
         if(线段的某个端点在S上)
         {
               将该端点加入pointSet;                       
         }                      
         else if(S的某个端点在线段PQ上)
         {
               将该端点加入pointSet;     
         } 
         else if(线段PQ与S相交)
         {
              return false;//此时可以判断是内交了     
         } 
    } 
    将pointSet中的点按照X-Y坐标排序;
    for(pointSet中每两个相邻点pointSet[i],pointSet[i+1])
    {
         if(pointSet[i],pointSet[i+1]的中点不在多边形中)
         {
              return false;                                               
         }                                                    
    } 
    return true;
    

    转载于:https://www.cnblogs.com/zhangshu/archive/2011/08/08/2130694.html

    展开全文
  • 判断平面内点是否在多边形内有多种算法,其中射线法是其中比较好理解的一种,而且能够支持凹多边形的情况。该算法的思路很简单,就是从目标点出发引一条射线,看这条射线和多边形所有边的交点数目。如果有奇数个交点...

    转自https://www.cnblogs.com/charlee44/p/10704156.html

     

    1. 算法思路

    判断平面内点是否在多边形内有多种算法,其中射线法是其中比较好理解的一种,而且能够支持凹多边形的情况。该算法的思路很简单,就是从目标点出发引一条射线,看这条射线和多边形所有边的交点数目。如果有奇数个交点,则说明在内部,如果有偶数个交点,则说明在外部。如下图所示:

    算法步骤如下:

    1. 已知点point(x,y)和多边形Polygon的点有序集合(x1,y1;x2,y2;….xn,yn;);
    2. 以point为起点,以无穷远为终点作平行于X轴的射线line(x,y; -∞,y);循环取得多边形的每一条边side(xi,yi;xi+1,yi+1):
      1). 判断point(x,y)是否在side上,如果是,则返回true。
      2). 判断line与side是否有交点,如果有则count++。
    3. 判断交点的总数count,如果为奇数则返回true,偶数则返回false。

    2. 具体实现

    在具体的实现过程中,其实还有一个极端情况需要注意:当射线line经过的是多边形的顶点时,判断就会出现异常情况。针对这个问题,可以规定线段的两个端点,相对于另一个端点在上面的顶点称为上端点,下面是下端点。如果射线经过上端点,count加1,如果经过下端点,则count不必加1。具体实现如下:

    #include<iostream>
    #include <cmath>
    #include <vector>
    #include <algorithm>
    
    #define EPSILON 0.000001
    
    using namespace std;
    
    //二维double矢量
    struct  Vec2d
    {
    	double x, y;
    
    	Vec2d()
    	{
    		x = 0.0;
    		y = 0.0;
    	}
    	Vec2d(double dx, double dy)
    	{
    		x = dx;
    		y = dy;
    	}
    	void Set(double dx, double dy)
    	{
    		x = dx;
    		y = dy;
    	}
    };
    
    //判断点在线段上
    bool IsPointOnLine(double px0, double py0, double px1, double py1, double px2, double py2)
    {
    	bool flag = false;
    	double d1 = (px1 - px0) * (py2 - py0) - (px2 - px0) * (py1 - py0);
    	if ((abs(d1) < EPSILON) && ((px0 - px1) * (px0 - px2) <= 0) && ((py0 - py1) * (py0 - py2) <= 0))
    	{
    		flag = true;
    	}
    	return flag;
    }
    
    //判断两线段相交
    bool IsIntersect(double px1, double py1, double px2, double py2, double px3, double py3, double px4, double py4)
    {
    	bool flag = false;
    	double d = (px2 - px1) * (py4 - py3) - (py2 - py1) * (px4 - px3);
    	if (d != 0)
    	{
    		double r = ((py1 - py3) * (px4 - px3) - (px1 - px3) * (py4 - py3)) / d;
    		double s = ((py1 - py3) * (px2 - px1) - (px1 - px3) * (py2 - py1)) / d;
    		if ((r >= 0) && (r <= 1) && (s >= 0) && (s <= 1))
    		{
    			flag = true;
    		}
    	}
    	return flag;
    }
    
    //判断点在多边形内
    bool Point_In_Polygon_2D(double x, double y, const vector<Vec2d> &POL)
    {	
    	bool isInside = false;
    	int count = 0;
    	
    	//
    	double minX = DBL_MAX;
    	for (int i = 0; i < POL.size(); i++)
    	{
    		minX = std::min(minX, POL[i].x);
    	}
    
    	//
    	double px = x;
    	double py = y;
    	double linePoint1x = x;
    	double linePoint1y = y;
    	double linePoint2x = minX -10;			//取最小的X值还小的值作为射线的终点
    	double linePoint2y = y;
    
    	//遍历每一条边
    	for (int i = 0; i < POL.size() - 1; i++)
    	{	
    		double cx1 = POL[i].x;
    		double cy1 = POL[i].y;
    		double cx2 = POL[i + 1].x;
    		double cy2 = POL[i + 1].y;
    				
    		if (IsPointOnLine(px, py, cx1, cy1, cx2, cy2))
    		{
    			return true;
    		}
    
    		if (fabs(cy2 - cy1) < EPSILON)   //平行则不相交
    		{
    			continue;
    		}
    
    		if (IsPointOnLine(cx1, cy1, linePoint1x, linePoint1y, linePoint2x, linePoint2y))
    		{
    			if (cy1 > cy2)			//只保证上端点+1
    			{
    				count++;
    			}
    		}
    		else if (IsPointOnLine(cx2, cy2, linePoint1x, linePoint1y, linePoint2x, linePoint2y))
    		{
    			if (cy2 > cy1)			//只保证上端点+1
    			{
    				count++;
    			}
    		}
    		else if (IsIntersect(cx1, cy1, cx2, cy2, linePoint1x, linePoint1y, linePoint2x, linePoint2y))   //已经排除平行的情况
    		{
    			count++;
    		}
    	}
    	
    	if (count % 2 == 1)
    	{
    		isInside = true;
    	}
    
    	return isInside;
    }
    
    
    int main()
    {	
    	//定义一个多边形(六边形)
    	vector<Vec2d> POL;	
    	POL.push_back(Vec2d(268.28, 784.75));
    	POL.push_back(Vec2d(153.98, 600.60));
    	POL.push_back(Vec2d(274.63, 336.02));
    	POL.push_back(Vec2d(623.88, 401.64));
    	POL.push_back(Vec2d(676.80, 634.47));
    	POL.push_back(Vec2d(530.75, 822.85));
    	POL.push_back(Vec2d(268.28, 784.75));				//将起始点放入尾部,方便遍历每一条边
    		
    	//
    	if (Point_In_Polygon_2D(407.98, 579.43, POL))
    	{
    		cout << "点(407.98, 579.43)在多边形内" << endl;
    	}
    	else
    	{
    		cout << "点(407.98, 579.43)在多边形外" << endl;
    	}
    
    	//
    	if (Point_In_Polygon_2D(678.92, 482.07, POL))
    	{
    		cout << "点(678.92, 482.07)在多边形内" << endl;
    	}
    	else
    	{
    		cout << "点(678.92, 482.07)在多边形外" << endl;
    	}
    
    	return 0;
    }

    运行结果如下:

    3. 改进空间

    1. 很多情况下在使用该算法之前,需要一个快速检测的功能:当点不在多边形的外包矩形的时候,那么点一定不在多边形内。
    2. 判断点在线上函数IsPointOnLine()和判断线段相交函数IsIntersect()这里并不是最优算法,可以改成向量计算,效率应该更高。
    展开全文
  • 判断是否在多边形内

    千次阅读 2013-09-23 02:10:20
    有一个n边形,顶点为p1,p2,...,pn;给定一个已知点p,判断p在此多边形内还是外。 预备知识: 两线段相交的定义,如果一条线段的两端分别处在另一条...3,把所有交点相加,如果是奇数则说明在多边形内,否则在多边形
  • 简单的说就是判断一个圆(给你圆心坐标和半径)是否在一个凸多边形内(你要判断这个多边形是否为凸包) 题意明白了,下面就是计算几何的基本模板了 1:首先我们要判断多边形是否为凸多边形(凸包); 2:...
  • 这题分为判断线段与4边是否有交点,如果没有判断两点是否在矩形就可以了。我用的方法是射线法。 #include #include #include #include using namespace std; typedef double PointType; struct p
  • 运用射线法计算点是否在多边形内。红点是要计算的点,通过该点引一条水平线,计算多边形各边与该水平线的交点(蓝点),如果红点两侧的射线与多边形各边的交点数都是奇数,那么红点在多边形内,反之不在。计算红点...
  • - 判定多边形的凹凸性判断是否在多边形内部 判断点是否在凸多边形内 1,原理 假设凸多边形顶点,按照顺时针顺序构成顶点数组verts:Point[],依次取两个顶点构成线段序列。 若点落在凸多边形内,则必有:该点在所有...
  • 射线法: //计算向量叉乘  var crossMul=function(v1,v2){ ... return v1.x*v2.y-v1.y*v2.x;...//判断两条线段是否相交  var checkCross=function(p1,p2,p3,p4){  var v1={x:p1.x-p3.x,y:p1.y-p3.y},  
  • Qt 判断是否在多边形内

    千次阅读 2017-03-17 14:30:11
    这里不用考虑线段的斜率,不会出现0作除数的bug,因为端点y值与目标点y值相等的时候,会认为端点上面,参考程序中的>=y bool DataConvert::isInsidePoly(const QPointF &iPoint,const QPolygonF &iMyPoly) ...
  • c# winform 中实现计算任意多边形面积,包括 凹多边形线段有交叉的多边形等。具体形式如下: 目标:计算红色区域的面积 实现的方法: 1、首先能够鼠标点击事件、鼠标移动事件、和paint事件中实现多边形的...
  • 不知道给出的点是顺时针还是逆时针,所以用判断是否在多边形内的模板,不用是否在凸多边形内的模板 POJ 1584 A Round Peg in a Ground Hole(判断凸多边形,点到线段距离,点在多边形内) #include <iostream...
  • 首先想到的一个解法是从这个点做一条射线,计算它跟多边形边界的交点个数,如果交点个数为奇数,那么点在多边形内部,否则点在多边形外。 注解:射线穿越顶点情况的解释 射线经过顶点:如何判断射线穿过线段?...
  • 首先判断要检测的点是否在边上 然后再判断射线是否经过一个线段的端点,如果经过低端点不计数,经过高端点计数 #include #include #include #include #include using namespace std; const double eps = 1e...
  • 1 //判断射线与也线段是否相交, 相交返回1,不相交返回0,边上返回-1 2 int IsIntersectant( CPoint ptStart, CPoint ptEnd, CPoint pd ) 3 { 4 double tempx = 0; 5 double tempy = 0; 6 //记录多边形边的端点...
  • 假若有一疑问点P(x,y),要判斯它是否在多边形内,可从该疑问点向左引水平扫描线(即射线)。 计算此线段与区域边界的相交次数c。如果c为奇数,认为疑问点在多边形内;为偶数,则疑问点在多边形外。 /** *射线法判断...
  • 射线法判断是否在多边形内(C#)

    千次阅读 2009-07-27 10:07:00
    //解题思想用射线法 //该题思想是向由点P向x正方向发射一个射线,穿过多边形线段上的个数为奇数则在多边形内,偶数则在多边形外 //具体方法是:点的Y值大于等于多边形上某个线段的最小值且小于该线段上的最大值,...
  • HDU1154求线段在多边形内长度

    千次阅读 2012-11-26 20:14:29
    /****************************************************************** 题意: ...排序后,判断每一段线段是否在多边形内判断中点是否在多边形内),求和。 *************************************

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 164
精华内容 65
关键字:

判断线段是否在多边形内