精华内容
下载资源
问答
  • 在上述博客中,我分别对平滑滤波、边缘检测、直线检测了一定程度了解,那么最终目的我们是需要解决实际问题,那么今天就试着完成一个简单综合训练,来在巩固前面所学知识同时,学到...算出这两平行线之间...

          在上述博客中,我分别对平滑滤波、边缘检测、直线检测做了一定程度的了解,那么最终的目的我们是需要解决实际问题,那么今天就试着完成一个简单的综合训练,来在巩固前面所学知识的同时,学到新的东西!

          题目如下:
                                                    

        1.分别检测两线段的长度;

        2.算出这两平行线之间的距离。

        题目参考:http://www.opencvchina.com/thread-854-1-2.html

     

    先看第一问,要求直线的距离。很容易联想到上一回所说的霍夫变换中的PHTT方法,返回的是直线的方向以及范围,说的具体一点,实际上返回的就是检测到的直线的两端点。我们不妨用霍夫变换直接试试。具体步骤:

                              将图像转换成灰度图像->霍夫变换->将检测直线的端点(绿色圆圈)标记出来

    得到下面的结果:

     可以看到,我们检测到了很多条直线,如图有很多直线的端点,尤其是直线端点处,被检测到了多个端点(可以看得出有重叠效果)。其实也不难理解,这条直线在像素上来说是有厚度的,所以难免被检测到多条直线,这样的话就带来了问题,我们无法确定到底哪个是真正直线的两端点,于是就不能够得到线段的长度!那么我们在使用霍夫变换前需要做一些处理。-----------图像细化。

     

    图像细化实际上就是图像骨架化,把图像核心的骨架留下,其他的赘余点删除,对于这个图来说就是把这条直线的厚度消除,得到一条单像素厚度的直线段。实际上,图像细化在图像处理、模式识别中使用的非常广发,也是非常关键的过程,这里我们介绍一种比较经典实用的图像细化方法----Zhang并行快速算法:

                 具体实现方法、步骤如下:

                 首先定义如下的8领域(注意顺序不能变):
                                                                      

                其中P1是我们讨论的像素点,首先前提条件是P1是前景点!若要删除该点,需要满足一下条件:

     过程1:

                 (1)2 <= N(P1) <= 6,N(x)为x的8领域中黑点(背景点)的个数;

                 (2)A(P1) = 1,A(x)为P2-P8之间按序前后分别为0、1的对数;

                 (3)P2*P4*P6 = 0;

                 (4)P4*P6*P8 = 0.

    满足上述四个条件,可将P1点去除;

    过程2:

                 (1)2 <= N(P1) <= 6,N(x)为x的8领域中黑点(背景点)的个数;

                 (2)A(P1) = 1,A(x)为P2-P8之间按序前后分别为0、1的对数;

                 (3)P2*P4*P8 = 0;

                 (4)P2*P6*P8 = 0.

    满足上述四个条件,可将P1点去除;

    以上即为Zhang并行算法的主要步骤,需要反复运行直到无法得到可删除点为止。对于图像细化,这里只做一个简单的了解,很多理论知识以及高级的算法我后续会再进行分析。

    给出关键代码函数如下:

     

    //寻找按序的前后分别是0、1的对数函数
    int Findn(IplImage* img, int i, int j)
    {
     CvScalar s1 = cvGet2D(img, i, j);
     CvScalar s2 = cvGet2D(img, i - 1, j);
     CvScalar s3 = cvGet2D(img, i - 1, j + 1);
     CvScalar s4 = cvGet2D(img, i, j + 1);
     CvScalar s5 = cvGet2D(img, i + 1, j + 1);
     CvScalar s6 = cvGet2D(img, i + 1, j);
     CvScalar s7 = cvGet2D(img, i + 1, j - 1);
     CvScalar s8 = cvGet2D(img, i, j - 1);
     CvScalar s9 = cvGet2D(img, i - 1, j - 1);
     int a = s1.val[0];
     int b = s2.val[0];
     int c = s3.val[0];
     int d = s4.val[0];
     int e = s5.val[0];
     int f = s6.val[0];
     int g = s7.val[0];
     int h = s8.val[0];
     int l = s9.val[0];

     int find[] = { a, b, c, d, e, f, g, h, l };//按8领域顺序定义数组,方便操作
     int n = 0;
     for (int x = 2; x < 9; ++x)
     {
      if (find[x] == 0 && find[x + 1] == 255)
      {
       n = n + 1;
      }
     }
     return n;
    }

    //这是细化直线的功能函数
    IplImage* ThinImage(IplImage* img, int k) //确保输入的是二值图像
    {
     int condition = 0;//满足的条件个数
     int mark = 0;//成功的标志位
     int firstN = 0;//第一个条件黑点的个数
     CvScalar s;
     for (int n = 0; n < k; ++n)
     {
      for (int i = 1; i < img->height - 1; ++i)
      {
       for (int j = 1; j < img->width - 1;++j)
       {//开始过程1的寻找
        condition = 0;//初始化条件满足数
             //cout << "1" << endl;
        s = cvGet2D(img, i, j);
        if (s.val[0] == 255)//如果这是前景点,即边缘
        {
         //cout << "2" << endl;
         //*************************第一过程****************************
         //*************************step1****************************
         firstN = 0;
         for (int ii = -1; ii < 1; ++ii)
         {
          for (int jj = -1; jj < 1; ++jj)
          {
           s = cvGet2D(img, i + ii, j + jj);
           if (s.val[0] == 255)
           {
            firstN = firstN + 1;
           }
          }
         }
         if (firstN < 3 || firstN > 7)
         {
          continue;
         }
         else
         {
          condition = condition + 1;
         }
         //****************************************************************
         //*************************step2*********************************
         if (Findn(img, i, j) != 1)
         {
          continue;
         }
         else
         {
          condition = condition + 1;
         }
         //****************************************************************
         //*************************step3*********************************
         CvScalar s1 = cvGet2D(img, i - 1, j);
         CvScalar s2 = cvGet2D(img, i, j + 1);
         CvScalar s3 = cvGet2D(img, i + 1, j);
         CvScalar s4 = cvGet2D(img, i, j - 1);
         int a = s1.val[0];//2
         int b = s2.val[0];//4
         int c = s3.val[0];//6
         int d = s4.val[0];//8

         if (a * b * c != 0)
         {
          continue;
         }
         else
         {
          condition = condition + 1;
         }
         //*********************************************************************
         //******************************step4**********************************
         if (b * c * d != 0)
         {
          continue;
         }
         else
         {
          condition = condition + 1;
         }
         //*********************************************************************
         //第一过程的结果操作
         if (condition == 4)
         {
          mark = 1;
          //((char *)(img->imageData + img->widthStep * (i)))[j] = 0;
          CvScalar p;
          p.val[0] = 0;
          cvSet2D(img, i, j, p);
          //cout << "11111111111111111111111111111111111" << endl;
         }
        }
       }
      }

      //****************************过程2**************************
      for (int i = 1; i < img->height - 1; ++i)
      {
       for (int j = 1; j < img->width - 1;++j)
       {//开始过程1的寻找
        condition = 0;//初始化条件满足数
             //cout << "1" << endl;
        s = cvGet2D(img, i, j);
        if (s.val[0] == 255)//如果这是前景点,即边缘
        {
         //cout << "2" << endl;
         //*************************第一过程****************************
         //*************************step1****************************
         firstN = 0;
         for (int ii = -1; ii < 1; ++ii)
         {
          for (int jj = -1; jj < 1; ++jj)
          {
           s = cvGet2D(img, i + ii, j + jj);
           if (s.val[0] == 255)
           {
            firstN = firstN + 1;
           }
          }
         }
         if (firstN < 3 || firstN > 7)
         {
          continue;
         }
         else
         {
          condition = condition + 1;
         }
         //****************************************************************
         //*************************step2*********************************
         if (Findn(img, i, j) != 1)
         {
          continue;
         }
         else
         {
          condition = condition + 1;
         }
         //****************************************************************
         //*************************step3*********************************
         CvScalar s1 = cvGet2D(img, i - 1, j);
         CvScalar s2 = cvGet2D(img, i, j + 1);
         CvScalar s3 = cvGet2D(img, i + 1, j);
         CvScalar s4 = cvGet2D(img, i, j - 1);
         int a = s1.val[0];//2
         int b = s2.val[0];//4
         int c = s3.val[0];//6
         int d = s4.val[0];//8

         if (a * b * d != 0)
         {
          continue;
         }
         else
         {
          condition = condition + 1;
         }
         //*********************************************************************
         //******************************step4**********************************
         if (a * c * d != 0)
         {
          continue;
         }
         else
         {
          condition = condition + 1;
         }
         //*********************************************************************
         //第一过程的结果操作
         if (condition == 4)
         {
          mark = 1;
          //((char *)(img->imageData + img->widthStep * (i)))[j] = 0;
          CvScalar p;
          p.val[0] = 0;
          cvSet2D(img, i, j, p);
          //cout << "222222222222222222222222" << endl;
         }
        }
       }
      }
      //cout << " end " << endl;
     }

     return img;

    }
     以上即为图像骨架化的编程实现,让我们看一看效果吧:

     可以看到,直线已经骨架化成功了,那么接下来,我们再使用霍夫变换检测线段。使用PPHT方法,得到线段的方向以及范围信息,并将检测的直线端点标记出来,代码如下:

    CvMemStorage* storageline = cvCreateMemStorage(0);
     CvSeq* lines;
     lines = cvHoughLines2(binaryline, storageline, CV_HOUGH_PROBABILISTIC, 1, CV_PI / 300, 100, 10, 1000);
     int n = 0;
     CvPoint* point;
     double temp[8];
     for (int i = 0; i < lines->total; ++i)
     {
      point = (CvPoint*)cvGetSeqElem(lines, i);
      temp[i * 4] = point[0].x;
      temp[i * 4 + 1] = point[0].y;
      temp[i * 4 + 2] = point[1].x;
      temp[i * 4 + 3] = point[1].y;
      cvLine(resultline, point[0], point[1], CV_RGB(255, 0, 0));
      cvCircle(resultline, point[0], 3, CV_RGB(0, 255, 0), 1, 8, 3);
      cvCircle(resultline, point[1], 3, CV_RGB(0, 255, 0), 1, 8, 3);
      double distance = sqrt((point[1].x - point[0].x) * (point[1].x - point[0].x) + (point[1].y - point[0].y) * (point[1].y - point[0].y));  
      cout << "the " << i << " line's distance :" << distance << endl;
      ++n;
     }
     cout << n << endl;
     n = 0;

    结果如下:

     成功得到了直线端点坐标的信息,并且输出n = 2,即刚刚好检测到两条直线!nice,这样的话直线长度就很好求了,使用数学方法,计算两坐标之间的距离即可。(结果将在后面显示)

     

    第二问实际上在第一问的基础上,就是一个数学问题。

     
    如图,正是求两平行线距离x。

                                                                       x = |AC|/sin(a)

    于是通过向量求得

                                                             cos = (AB·AC)/|AB||AC|
                                                              sin = sqrt(i - cos^2)

    于是便可求得x。

    按照如此思路,编程求得上述两问的结果:

     
     

    展开全文
  • 折线平行线的计算方法

    千次阅读 2017-10-10 07:57:09
    给定一个简单多边形,多边形按照顺时针或者逆时针数许排列 内部等距离缩小或者外部放大多边形,...平行于L1和L2,平行线间距是L,并且位于多边形内部两条边,交于Qi 我们要计算出Qi坐标 如图, P

    给定一个简单多边形,多边形按照顺时针或者逆时针的数许排列

    内部等距离缩小或者外部放大的多边形,实际上是由距离一系列平行已知多边形的边,并且距离为L的线段所构成的。


    外围的是原多边形,内侧是新的多边形

    算法构造

    多边形的相邻两条边,L1和L2,交于Pi点

    做平行于L1和L2,平行线间距是L的,并且位于多边形内部的两条边,交于Qi

    我们要计算出Qi的坐标

    如图,


    PiQi向量,显然是等于平行四边形的两个相邻边的向量v1和v2的和的

    而v1和v2向量的方向,就是组成多边形的边的方向,可以用顶点差来表示

    v1和v2向量的长度是相同的,等于平行线间距L与两个线段夹角的sin值的除法。

    即: Qi = Pi + (v1 + v2)

        Qi = Pi + L / sinθ * ( Normalize(v2) + Normalize(v1))

        Sin θ = |v1 × v2 | /|v1|/|v2|

    计算步骤:

    ⑴、获取多边形顶点数组PList;

    ⑵、计算DPList[Vi+1-Vi];

    ⑶、单位化NormalizeDPList,得到NDP[DPi];(用同一个数组存储)

    ⑷、Sinα = Dp(i+1) X DP(i);

    ⑸、Qi = Pi + d/sinα (NDPi+1-NDPi)

    ⑹、这样一次性可以把所有顶点计算完。

    注意,交换Qi表达式当中NDPi+1-NDPi的顺序就可以得到外部多边形顶点数组。

    用Swift实现的代码如下,在playground可直接运行


    import Foundation


    class Point2D  {

        var x:Double =0

        var y:Double =0

        init(_ x:Double,_ y:Double){self.x=x;self.y=y}

        init( point:Point2D){x=point.x;y=point.y}

    }


    //func += (inout left:Point2D, right:Point2D )     { left.x+=right.x;left.y += right.y;}

    func +  (left:Point2D, right:Point2D)->Point2D   {return Point2D(left.x+right.x, left.y+right.y)}

    func -  (left:Point2D, right:Point2D)->Point2D   {return Point2D(left.x-right.x, left.y-right.y)}

    func *  (left:Point2D, right:Point2D)->Double    {return left.x*right.x + left.y*right.y}

    func *  (left:Point2D, value:Double )->Point2D   {return Point2D(left.x*value, left.y*value)}


    // 自定义的向量差乘运算符号,

    infix operator ** {}

    func ** (left:Point2D, right:Point2D)->Double {return left.x*right.y - left.y*right.x}


    var pList   = [Point2D]()  // 原始顶点坐标, 在initPList函数当中初始化赋值

    var dpList  = [Point2D]() // 边向量dpList[i+1]- dpLIst[i] 在 initDPList函数当中计算后赋值

    var ndpList = [Point2D]() // 单位化的边向量, 在initNDPList函数当中计算后肤质,实际使用的时候,完全可以用dpList来保存他们

    var newList = [Point2D]()  // 新的折线顶点,在compute函数当中,赋值


    // 初始化顶点队列

    func initPList(){

        pList  = [ Point2D(0,0),

                   Point2D(0,100),

                   Point2D(100,100),

                   Point2D(50,50),

                   Point2D(100,0),

                 ]

    }


    // 初始化dpList  两顶点间向量差

    func initDPList()->Void{

        print("计算dpList")

        var index  : Int

        for index=0; index<pList.count; ++index{

            dpList.append(pList[index==pList.count-1 ? 0: index+1]-pList[index]);

            print("dpList[\(index)]=(\(dpList[index].x),\(dpList[index].y))")

        }

    }


    // 初始化ndpList,单位化两顶点向量差

    func initNDPList()->Void{

        print("开始计算ndpList")

        var index=0;

        for ; index<dpList.count; ++index {

            ndpList.append(dpList[index] * ( 1.0 /sqrt(dpList[index]*dpList[index])));

            print("ndpList[\(index)]=(\(ndpList[index].x),\(ndpList[index].y))")

        }

    }


    // 计算新顶点, 注意参数为负是向内收缩, 为正是向外扩张

    func computeLine(dist:Double)->Void{

        print("开始计算新顶点")

        var index = 0

        let count = pList.count;

        for ; index<count; ++index {

            var point:Point2D

            let startIndex = index==0 ? count-1 : index-1

            let endIndex   = index

            

            let sina =ndpList[startIndex] **ndpList[endIndex]

            let length = dist / sina

            let vector =ndpList[endIndex] -ndpList[startIndex]

            point = pList[index] + vector*length

            newList.append(point);

            print("newList[\(index)] = (\(point.x),\(point.y))")

        }

    }


    // 整个算法的调用顺序

    func run()->Void {

        initPList();

        initDPList()

        initNDPList()

        computeLine(-5)  // 负数为内缩, 正数为外扩。 需要注意算法本身并没有检测内缩多少后折线会自相交,那不是本代码的示范意图

    }


    run()


    展开全文
  • 在这道题之前过一次扫描线,这次首先就往扫描线上想了。最开始想法非常傻,就是记录当前坐标...其实我们应该这样,对于每一个线段树上区间,我们去记录他纵坐标范围,平行线的序号范围,覆盖两次以上长度...

    在这道题之前做过一次扫描线,这次首先就往扫描线上想了。最开始的想法非常傻,就是记录当前坐标长度范围内被覆盖的层数,以及最近一次被覆盖层数由1变成2的位置。每次覆盖的层数要减一了,就去查询,更新什么的。啊呀,太傻了!写着写着就写不下去了,本想把这一发代码贴出来教大家看了笑一笑,结果又弄丢了。

    其实我们应该这样,对于每一个线段树上的区间,我们去记录他的纵坐标范围,平行线的序号范围,覆盖两次以上的长度,覆盖一次以上的长度,还有覆盖的次数。这个覆盖的次数就很有讲究,update的时候,我们只在更新的区间和当前区间一模一样的时候才去动它,这么一来后面计算长度的操作,就要这样:当覆盖的数大于等于2的时候,说明这个区间真的全都被覆盖了两次及以上,所以记录覆盖长度的那两个量就都等于区间的长度。当覆盖的数等于一的时候,覆盖超过一次的长度没什么悬念,就是区间的长度。覆盖超过两次的长度,就得看它两个子区间被覆盖了超过一次的长度,其实就是这两者的和。为什么这么做,写题的时候还纳闷了好一会儿,道理是这样的,覆盖数得是把这个区间完全覆盖了的矩形才能计进去的,而今做这一步运算的时候,肯定要么正在计数的线段没有把整个线段树的区间都覆盖,要么它两个子区间还没更新。所以计算覆盖了两次及以上的长度,自然就是子区间覆盖了一次的长度之和。我们也不用担心这么一来会在以后的查询中查询到相当于懒标记尚未到达处的子区间,因为没有更新过的子区间,查询的时候那也更用不到哇!

    然后,如果这一次发现区间的覆盖数是0,那么如果这个区间对应的纵坐标范围只是1,那就没什么好说的了,反正又没有子区间,什么覆盖数都是0。否则的话,就只能老老实实继承子区间对应数值之和了。

    再整个离散化,就挺好的了。关于一开始那个记录最近一次被覆盖层数由1变成2的位置的蠢想法,就是没有充分理解扫描线的妙处,只要一个竖线一个竖线地扫下来,扫一次加一次面积,就能把答案算出来了。

     for (int i=2; i<cnt; i++)
            {
                //9cout<<"i="<<i<<endl;
                ans+=tree[1].sum*(line[i].x-line[i-1].x);
                tmp.update(1,line[i]);
            }
    struct segment_tree{
        void build(int l,int r,int rt)
        {
            tree[rt].l=l;
            tree[rt].r=r;
            tree[rt].sum=0;
            tree[rt].one=0;
            tree[rt].lf=y[l];
            tree[rt].rf=y[r];
            if (l+1==r)
            {
                return;
            }
            int mid=l+r>>1;
            build(l,mid,rt*2);
            build(mid,r,rt*2+1);
        }
        void update(int rt,Line e)
        {
            if (tree[rt].lf==e.d && tree[rt].rf==e.u)
            {
                tree[rt].c+=e.flag;
                query(rt);
                return;
            }
            if (e.u<=tree[rt*2].rf) update(rt*2,e);
            else if (e.d>=tree[rt*2+1].lf) update(rt*2+1,e);
            else
            {
                Line tmp=e;
                tmp.u=tree[rt*2].rf;
                update(rt*2,tmp);
                tmp=e;
                tmp.d=tree[rt*2+1].lf;
                update(rt*2+1,tmp);
            }
            query(rt);
        }
        void query(int rt)
        {
            if (tree[rt].c>=2)
            {
                tree[rt].sum=tree[rt].rf-tree[rt].lf;
                tree[rt].one=tree[rt].rf-tree[rt].lf;
                return;
            }
            else if (tree[rt].c==1)
            {
                tree[rt].one=tree[rt].rf-tree[rt].lf;
                //cout<<"rtl="<<tree[rt*2].lf<<" rtr="<<tree[rt*2].rf<<" one="<<tree[rt*2].one<<endl;
                //cout<<"2rtl="<<tree[rt*2+1].lf<<" 2rtr="<<tree[rt*2+1].rf<<" one="<<tree[rt*2+1].one<<endl;
                if (tree[rt].l+1==tree[rt].r) tree[rt].sum=0;
                else tree[rt].sum=tree[rt*2].one+tree[rt*2+1].one;
                //cout<<"rtl="<<tree[rt].lf<<" rtr="<<tree[rt].rf<<" sum="<<tree[rt].sum<<endl;
            }else
            {
                if (tree[rt].l+1==tree[rt].r)
                {
                    tree[rt].one=0; tree[rt].sum=0;
                }else
                {
                    tree[rt].one=tree[rt*2].one+tree[rt*2+1].one;
                    tree[rt].sum=tree[rt*2].sum+tree[rt*2+1].sum;
                }
            }
        }
    };

     

    展开全文
  • 其次, 我们求是一个框框(范围)内东西, 特别是有扫描线,且能够出入,所以想到线段树 (有点牵强...主要是因为我们做的就是线段树题目... 想想怎么实现,怎么题 因为是一个框框,它框住某点位置有多个,...

    题意

    T组数据,每次给你n个点,含点权

    给你一个矩形,只能底边平行x轴放置

    求矩形内点权和的最大值

    T≤10,n≤1e5

    分析

    首先,看到n和xy的范围,想到离散化
    其次, 我们求的是一个框框(范围)内的东西, 特别是有扫描线,且能够出入,所以想到线段树
    (有点牵强...主要是因为我们做的就是线段树题目...
    想想怎么实现,怎么做题
    因为是一个框框,它框住某点的位置有多个,这样不好维护线段树,所以
    我们把每个点(i,j)作为左下角,向右向上延生至(i+w-1,j+h-1),这个矩形加上(i,j)的贡献(即亮度 )(注:不包括边框)
    不考虑横坐标,它能影响到的矩形为:y到y+h的点所代表的所有矩形。
    考虑上横坐标,用扫描线,及时删除不在当前横坐标能覆盖的星星。

    参考代码&分析

    https://www.luogu.org/blog/HotoChino/solution-p1502

    错误代码(留坑代填(wtm做了一下午....还是没有找到错误

    #include<cstdio>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    #define MAX 10000+9
    
    int n,w,h;
    int mx[MAX<<3], day[MAX<<1], addv[MAX<<2];//Discrete Array y 离散化y数组 
    //线段树四倍,扫描线两倍 
    struct seg{//平行于y轴的扫描线 
        int x, y1, y2, l;
        seg(int x=0, int y1=0, int y2=0, int l=0) : x(x), y1(y1), y2(y2), l(l) {} 
        bool operator < (const seg& xxx) const {
            return x < xxx.x;//从左向右, 按顺序扫, 所以需要排序 
        }
    } s[MAX<<1];
    struct node{
        int x, y, l;
        bool operator < (const node& xxx) const {
            return x < xxx.x ;
        }
    }a[MAX];
    
    void push_up(int o) { mx[o] = max(mx[o<<1], mx[o<<1|1]); }
    void pushtag(int o, int l, int r, int v) { addv[o] += v, mx[o] += v;};
    void push_down(int o, int l, int r) {
        if(addv[o] == 0) return ;
        addv[o<<1] += addv[o];
        mx[o<<1] += addv[o];
        addv[o<<1|1] += addv[o];
        mx[o<<1|1] += addv[o];
        addv[o] = 0;
    }
    void optdate(int o, int l, int r, int ql, int qr, int v) {
        if(ql <= l && r <= qr) { pushtag(o, l, r, v); return ;}
        push_down(o, l, r);
        int mid = (l+r)>>1;
        if(ql <= mid) optdate(o<<1, l, mid, ql, qr, v);
        if(qr > mid) optdate(o<<1|1, mid+1, r, ql, qr, v);
        push_up(o);
    }
    
    int main() {
        int T;
        scanf("%d",&T);
        while(T--) {
            scanf("%d%d%d", &n, &w, &h);
            memset(mx, 0, sizeof(mx));
            memset(day, 0, sizeof(day));
            int x,y,l;
            for(int i = 1; i <= n; i++) {
                scanf("%d%d%d",&x,&y,&l);//亮度l 
                s[i] = seg(x, y, y+h-1, l);
                day[i] = y;
                s[i+n] = seg(x+w-1, y, y+h-1, -l);//-l表示出 
                day[i+n] = y+h-1;
            }
            n <<= 1;//两倍 
            sort(day+1, day+1+n);
            int tot = 1;
            for(int i = 2; i <= n; i++) if(day[i] != day[tot]) day[++tot] = day[i];
            /*unique的使用: 
            sort(day+1,day+1+n);//排序 
            int tot=unique(day+1,day+1+n)-day-1;//去重 */
            sort(s+1,s+1+n);//根据横坐标排序 
            //build();刚开始就是空的 
            int ans = 0;
            for(int i = 1; i <= n; i++) {
                int l = lower_bound(day+1, day+1+tot, s[i].y1 ) - day;//二分查找边界 
                int r = lower_bound(day+1, day+1+tot, s[i].y2 ) - day;//找到y1和y2,求出区间最大值 
                if(l > r) swap(l, r);
                optdate(1, 1, tot, l, r, s[i].l );//下次再扫到右边界时就会在原区间加上-l,即删除; //
                ans = max(ans, mx[1]);
            }
            printf("%d\n",ans);
        }
        
    }

    转载于:https://www.cnblogs.com/tyner/p/11251690.html

    展开全文
  • 现在有平面直角坐标系xoy, 有n个平行于x轴y轴矩形, 给出这些矩形左上角和右下角坐标, 让你求出这些矩形组成图形中被至少两个矩形覆盖部分总面积. 解题思路 如果你还没有过这道题, 推荐点击链接先看...
  • 天真小卡总是希望能够在晚上能看到最多最亮星星,但是窗子大小是固定,边也必须和地面平行。 这时小卡使用了超能力(透视术)知道了墙后面每个星星位置和亮度,但是小卡发动超能力后就很疲劳,只好拜托你...
  • 注意把每个点x,y坐标加10001,因为线段树节点下标不能为负和0,(当然用离散化就不用这样处理了),每加进来一条线段,就对相应的线段cover值加1,然后求出当前已经被覆盖区间总长度L,然后:把这次求出 ...
  • 线段的交点计算

    2017-08-08 14:18:00
    两条线段求交设有两线段AB和CD,其端点坐标分别为和,它们所在直线参数方程分别为:若两线段相交,则交点参数值,应满足:即因此,若行列式表示两线段AB和CD重合或平行。一般为它们不相交来处理。如果,则可求出交点...
  • POJ 1151 - Atlantis 线段树+扫描线..

    千次阅读 2013-07-26 11:37:56
    离散化: 将所有x轴坐标存在一个数组里..排序.当进入一条线段时..通过二分方式确定其左右点对应离散值...  扫描线..... 线段树: 本题用于动态维护扫描线在往上走时..x哪些区域是有合法面积..
  • 思路:这个数据范围瞎暴力就过了,但我们是有文化人,下面讲讲利用扫描线线段简单O(NlogN)做法。 先讲扫描线。我们先只考虑横着边,竖着等会儿一样就是了。我们假设有一条横着直线(这条就是扫描线...
  • 题目来源:http://poj.org/problem?id=1151题意在二维坐标系上,给出多个矩形左下以及右上坐标,求出所有矩形构成图形面积。思路第一次接触扫描线。...相应,在这道题里,假设以和x轴平行的作为扫描线
  • 三等分一个线段(tripartition(AB)) 输入:线段 AB 输出:将 AB 等分的两个点,H、G 从 B 发出一条(任意一条)与 AB 不重合的射线 BC...过 E AF 的平行线,交AB 于 H 过 D AF(EH)的平行线,交 AB 于 G。
  • 成比例,正相似,经常要作平行线。圆外若有一切线,切点圆心把线连。如果两圆内外切,经过切点作切线。两圆相交于两点,一般作它公共弦。是直径,成半圆,想直角把线连。作等角,添个圆,证明题目少困难。辅助线,...
  • 扫描线这个算法,就是从左到右拿一根平行于y轴的线去扫描,遇到线段后进行处理,入边和出边。统计答案要注意。线段树负责维护其实是一个线段覆盖问题,我每个节点表示是一条线段,即a[l]a[r+1],所以我建树...
  • 【初中数学】102条初中几何辅导线规律线、角、相交线、平行线 规律1 如果平面上有n(n≥2)个点,其中任何三点都不在同一直线上,那么每两点画一条直线,一共可以画出n(n-1)条。 规律2 平面上n条直线最多可...
  •  题意:给出n条平行于Y轴的线段(y', y'', x),然后3条一组,问有多少组可见线段组。“可见”定义为,两条线段能由一条水平先连接但不交于其它的线段。“可见线段组”定义为该组内3条线段两两可见。  ...
  • 平行线思路则是为了构造一个等腰三角形,通常是为了转移线段关系。双角平分线夹角公式记住这个结论,在选择题、填空题里可以直接使用,快人一步。在解答题里能给你一个思路,让你知道这两个角是有一定关系。常见...
  •  在介绍尺规作图等分圆面积时,我提到了利用尺规作图将线段AB任意等分问题。在初中课本上,这个问题标准做法如下: 1. 过A点向另一方向射线l; 2. 从A点开始,用圆规在射线l上... 那么,这些平行线与AB
  • 本篇博客在上一篇博客基础上...这类问题应该引入扫描线,下面来讲讲扫描线的概念。 扫描线在并行面积并中应用 首先得定义扫描线 ,扫描线就是一条设想的线,它可以是从水平方向上下扫描,也可以从竖直方向左
  • 后来发现其实只需要对接口进行一下相交查询就简单多了,因为只需要考虑能不能通过每个截口就可以了,而且这样做的好处还有没有平行线和重叠线情况,因为所有截口都是垂直于x轴,换一种想法海阔太空...
  • 和intersection求交点部分,但是不能处理两条直线平行的情况,需要提前判断两条线是否平行。最后用了floyd算法来进行相连拓展。其实这里证明floyd可行性是一个比较复杂过程,但是我们可以联想前面求最短路时候,...
  • HDOJ-1542 Atlantis 扫描线

    2019-07-03 13:31:52
    扫描线算法的核心思想在于使用线段树对扫描线线段的长度进行维护。因此,如果平行于x轴扫描线,那么就需要以所有的端点的x坐标为端点,以这些端点组成的线段为线段树叶子节点存储的对象,从而对扫描线的长度进行...
  • 贝塞尔曲线 多点画

    2018-01-24 14:50:00
    1。这里利用的是三阶贝塞尔曲线,所以需要计算出两个控制点,因为贝塞尔曲线是两点之间的连线,...怎么计算这两个点呢,现在假设这条曲线上有三个点,A为上一个点,B为当前点,C为B后面的点,连接AC,AC的平行线...
  • 有感觉是扫描线,可是做的不多不会操作啊 = =. 假设我们用平行于y轴的线段去扫描,那么需要就是对y坐标进行离散化. 将所有平行于x轴的线段,拆成两个点,(x1,y),(x2,y).,竖线段不变.然后进行离散化,全部按照x...
  • 盗版必究!建议自己完,再看视频.2020福建厦门市质检第25题在平面直角坐标系中,点...(2)若P,Q是第一象限一对泛对称点,过点P作PA⊥x轴于点A,过点Q作QB⊥y轴于点B,线段PA,QB交于点C,连接AB,PQ,判断直线A...
  • 单说求交点个数问题,我方法就是扫描线+线段树/树状数组,但是树状数组不太了解,那就用树状数组吧! 1e9数据肯定先离散化 我把横线(平行于x轴)当做枚举对象,那些竖线(平行于y轴)就记录他们...
  • 布线规则.txt

    2019-05-23 10:11:36
    电磁抗干扰原则涉及知识点比较多,例如铜膜线的拐弯处应为圆角或斜角(因为高频时直角或者尖角拐弯会影响电气性能)双面板两面导线应互相垂直、斜交或者弯曲走线,尽量避免平行走线,减小寄生耦合等。...
  • 利用叉积运算很容易算出来,我们可以先判断是否是平行的,只需将每一段线段向量化,再与另一个 向量叉积运算,若为0即平行或重合,判断是否重合,只需找其中一个向量与该向量一端与另一向量 一端组成...

空空如也

空空如也

1 2 3 4
收藏数 76
精华内容 30
关键字:

做线段的平行线