精华内容
下载资源
问答
  • 平面分割

    千次阅读 2017-01-22 09:39:57
    平面分割 描述 Description 【问题描述】  同一平面内有n(n≤500)条直线,已知其中p(p≥2)条直线相交于同一点,则这n条直线最多能将平面分割成多少个不同的区域? 【输入格式】  两个整数n(n≤500)和p...

    平面分割
    描述 Description
    【问题描述】
      同一平面内有n(n≤500)条直线,已知其中p(p≥2)条直线相交于同一点,则这n条直线最多能将平面分割成多少个不同的区域?
    【输入格式】
      两个整数n(n≤500)和p(2≤p≤n)。
    【输出格式】
      一个正整数,代表最多分割成的区域数目。
    【输入样例】Surface.in
      12 5
    【输出样例】Surface.out
      73

    时间限制 Time Limitation
    各个测试点1s

    这里写图片描述
    如图,首先考虑n-1=p(n,p>=2)的情况。此时分割的空间数为2(n-1)。

    再加上一条直线。
    这里写图片描述
    此时直线每过一条直线,就能多分割出一块空间,共可分割出n块。

    所以得到递推式:f(p)=2*p;
    f(n)=f(n-1)+n;

    #include<iostream>
    
    using namespace std;
    int main()
    {
        int n,m;
        cin>>n>>m;
        int total=2*m;
        for (int i=m+1;i<=n;i++)
        total+=i;
        cout<<total;
    
    }
    展开全文
  • 平面分割问题

    2018-02-01 08:01:47
    (一)直线分割平面问题:n条直线,最多可以把平面分为多少个区域。
    (一)直线分割平面问题:
    n条直线,最多可以把平面分为多少个区域。
    展开全文
  • 平面分割空间

    2016-07-18 17:22:46
    一篇网上找到的分析平面分割空间的很好的文档,分享给个位acmer们看看。
  • 线分割平面与平面分割空间问题

    千次阅读 2016-01-27 14:48:39
    (1) n条直线最多分平面问题 题目大致如:n条直线,最多可以把平面分为多少个区域。 析:可能你以前就见过这题目,这充其量是一道初中的思考题。但一个类型的题目还是从简单的入手,才容易发现规律。当有n-1条直线时,...

    由这一题可以推一类的问题,首先由直线划分区域到折线划分区域,再延伸到封闭图形划分区域,
    最后在推广为平面划分空间的问题。

    (1) n条直线最多分平面问题

    题目:n条直线,最多可以把平面分为多少个区域。

    解析: 可能你以前就见过这题目,这充其量是一道初中的思考题。
    但一个类型的题目还是从简单的入手,才容易发现规律。
    当有n-1条直线时,平面最多被分成了f(n-1)个区域。
    则第n条直线要是切成的区域数最多,就必须与每条直线相交且不能有同一交点。
    这样就会得到n-1个交点。这些交点将第n条直线分为2条射线和n-2条线断。
    而每条射线和线断将以有的区域一分为二。这样就多出了2+(n-2)个区域。
    故:f(n)=f(n-1)+n
    f(n-1)=f(n-2)+n-1
    ……
    f(2)=f(1)+2
    因为,f(1)=2
    所以,f(n)=n*(n+1)/2 + 1

    (2) 折线分平面(hdu2050)

    解析:根据直线分平面可知,由交点决定了射线和线段的条数,进而决定了新增的区域数。
    当n-1条折线时,区域数为f(n-1)。为了使增加的区域最多,
    则折线的两边的线段要和n-1条折线的边,即2*(n-1)条线段相交。
    那么新增的线段数为4*(n-1),射线数为2。
    但要注意的是,折线本身相邻的两线段只能增加一个区域。
    故:f(n)=f(n-1)+4*(n-1)+1
    f(n-1)=f(n-2) + 4*(n-2)+1
    ……
    f(2)=f(1) + 4*1 + 1
    因为,f(1)=2
    所以,f(n)=2n^2-n+1

    (3) 封闭图形分平面问题

    三角形划分区域(hdu1249)

    解析:当n-1个三角形时,区域面积数为 f(n-1) 。
    要区域数最多,那么第n个三角形就必须与前n-1个三角形相交。
    则第n个三角形的一条边就被分割成 2*(n-1)-1条线段与两个半条的线段 ,
    即相当于2*(n-1)条线段。则第 n 个三角形被分割成 3*2*(n-1)条线段。
    则增加了 6*(n-1)个面。
    故:f(n)=6*(n-1)+f(n-1)
    f(n-1)=6*(n-2)+f(n-2)
    ……..
    f(2)=6*1+f(1)
    因为,f(1)=2
    所以,f(n)=3*n*(n-1)+2

    圆形划分区域

    题目:设有n条封闭曲线画在平面上,而任何两条封闭曲线恰好相交于两点,
    且任何三条封闭曲线不相交于同一点,问这些封闭曲线把平面分割成的区域个数。

    解析:当n-1个圆时,区域数为f(n-1).那么第n个圆就必须与前n-1个圆相交,
    则第n个圆被分为2(n-1)段线段,增加了2(n-1)个区域。
    故: f(n)=f(n-1)+2*(n-1)
    f(n-1)=f(n-2)+2*(n-2)
    ……
    f(2)=f(1)+2*1
    因为,f(1)=2
    所以,f(n)=n^2-n+2

    (5)平面分割空间问题(hdu1290)

    解析:由二维的分割问题可知,平面分割与线之间的交点有关,即交点决定射线和线段的条数,
    从而决定新增的区域数。
    试想在三维中则是否与平面的交线有关呢?
    当有n-1个平面时,分割的空间数为f(n-1)。
    要有最多的空间数,则第n个平面需与前n-1个平面相交,且不能有共同的交线。
    即最多有n-1 条交线。而这n-1条交线把第n个平面最多分割成g(n-1)个区域。
    (g(n)为(1)中的直线分平面的个数)此平面将原有的空间一分为二,
    则最多增加g(n-1)个空间。
    故:f(n)=f(n-1)+g(n-1) ( ps: g(n)=n(n+1)/2+1 )
    f(n-1)=f(n-2)+g(n-2)
    ……
    f(2)=f(1)+g(1)
    因为,f(1)=g(1)=2
    所以,f(n)=2+(1*2+2*3+3*4+……+(n-1)n)/2+(n-1)
    =[ (1^2+2^2+3^2+4^2+……+n^2) - (1+2+3+……+n ) ]/2 + n+ 1
    =(n^3+5n)/6+1

    (注:以上思路参考网络)

    展开全文
  • ransac是一种很有效的平面分割方法,根据设定的模型不断迭代找出属于模型的点。同时通过设置距离模型阈值可以起到分割多大地面起伏程度的地面。 3.数据 本例中使用的点云数据(test.pcd)请见百度网盘分享。 链接:...

    1.版本要求

    版本: >PCL1.3

    2.简介

    平面分割可用于地面检测,ransac是一种非常有效的平面分割方法,根据设定的平面模型不断迭代找出属于平面的点。同时通过设定模型距离阈值(setDistanceThreshold)可以检测不同起伏程度的地面。

    3.数据

    本例中使用的点云数据(test.pcd)请见百度网盘分享。
    链接:https://pan.baidu.com/s/1CN3sb1lRylfvT67PnRdKiw
    提取码:kz7q

    4.代码

    #include <pcl/point_types.h>
    #include <pcl/io/pcd_io.h>
    #include <pcl/filters/extract_indices.h>
    #include <pcl/segmentation/sac_segmentation.h>
    #include <pcl/visualization/cloud_viewer.h>
    
    int main(int argc, char** argv)
    {
    	pcl::PCDReader reader;
    	pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);
    	pcl::PointCloud<pcl::PointXYZ>::Ptr cloud_plane(new pcl::PointCloud<pcl::PointXYZ>);
    	reader.read("test.pcd", *cloud);  //读取点云
    	
    	pcl::PointIndices::Ptr inliers(new pcl::PointIndices);  //创建平面分割后存储平面点云的索引
    
    	pcl::SACSegmentation<pcl::PointXYZ> seg;  //创建sac分割对象
    	pcl::ModelCoefficients::Ptr coefficients(new pcl::ModelCoefficients);
    	seg.setOptimizeCoefficients(true);
    	seg.setModelType(pcl::SACMODEL_PLANE);  //设置模型为平面
    	seg.setMethodType(pcl::SAC_RANSAC);  //设置分割方法为ransac
    	seg.setMaxIterations(100);  //设置最大迭代次数
    	seg.setDistanceThreshold(0.15);  //设置偏离模型距离阈值
    	seg.setInputCloud(cloud);
    	seg.segment(*inliers, *coefficients);  
    
    	if (inliers->indices.size() == 0)  //检查一下是否有平面分割出来
    	{
    		std::cout << "Could not estimate a planar model for the given dataset." << std::endl;
    	}
    
    	pcl::ExtractIndices<pcl::PointXYZ> extract;  //抽取分割得到的平面点云
    	extract.setInputCloud(cloud);
    	extract.setIndices(inliers);
    	extract.setNegative(false);
    	extract.filter(*cloud_plane);
    	std::cout << "PointCloud representing the planar component: " << cloud_plane->size() << " data points." << std::endl;
    
    
    	pcl::visualization::PCLVisualizer viewer("Cloud Viewer");
    	int v1(0);  //创建左窗口显示原始点云
    	viewer.createViewPort(0, 0, 0.5, 1.0, v1);  //左右窗口大小划分,1:1
    	viewer.setBackgroundColor(0, 0, 0, v1);
    	viewer.addText("Cloud Original", 2, 2, "Cloud Original", v1);  //窗口下的标题
    	pcl::visualization::PointCloudColorHandlerGenericField<pcl::PointXYZ> rgb1(cloud, "z");
    	viewer.addPointCloud<pcl::PointXYZ>(cloud, rgb1, "original cloud", v1);
    	viewer.setPointCloudRenderingProperties(pcl::visualization::PCL_VISUALIZER_POINT_SIZE, 1, "original cloud", v1);
    	viewer.addCoordinateSystem(1.0, "original cloud", v1);
    	int v2(1);  //创建右窗口显示分割后的平面
    	viewer.createViewPort(0.5, 0, 1.0, 1.0, v2);  //左右窗口大小划分,1:1
    	viewer.setBackgroundColor(0, 0, 0, v2);
    	viewer.addText("Cloud Segmentation", 2, 2, "Cloud Segmentation", v2);  //窗口下的标题
    	pcl::visualization::PointCloudColorHandlerGenericField<pcl::PointXYZ> rgb2(cloud_plane, "z");
    	viewer.addPointCloud<pcl::PointXYZ>(cloud_plane, rgb2, "plane cloud", v2);
    	viewer.setPointCloudRenderingProperties(pcl::visualization::PCL_VISUALIZER_POINT_SIZE, 1, "plane cloud", v2);
    	viewer.addCoordinateSystem(1.0, "plane cloud", v2);
    
    	viewer.spin();
    
    	return (0);
    }
    

    5.效果

    在这里插入图片描述

    展开全文
  • 平面分割空间HDU1290

    2017-02-07 13:10:51
    由二维平面分割问题可以得出规律,交点决定所分线段数,所分线段决定增加的平面数, 那么在三维空间,交线是否能给我们启发呢? 答案很显然,可以 n-1个平面将空间分成f(n-1)个部分 再加一个平面,要到达增加的...
  • PCL 点云平面分割总结

    2021-01-28 14:11:25
    首先要引入关于平面分割的头文件 #include <pcl/ModeCoefficients.h> //模型系数相关头文件 #include<pcl/sample_consensus/method_types.h> //模型定义头文件 #include<pcl/sample_consensus/...
  • 平面分割问题汇总

    2014-03-04 10:54:09
    先看n条直线相交最多可把平面分割为几个部分: 设n-1条直线可把平面分割为f(n-1)个部分,则第n条直线需与平面中每一条直线相交才能使得把平面分割的个数达到最多,所以平面中有多增加了n-1个交点,平面又多了n块,f...
  • l(1) n条直线最多分平面问题 题目大致如:n条直线,最多可以把平面分为多少个区域。   析:可能你以前就见过这题目,这充其量是一道初中的思考题。但一个类型的题目还是从简单的入手,才容易发现规律。当有n-1条...
  • 折线分割平面 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 24706 Accepted Submission(s): 16782 Problem Description 我们看到过很多直线...
  • cadence allegro电源层平面分割

    千次阅读 2020-04-04 00:01:27
      allegro的电源层平面分割与AD的原理相同,只不过是关于敷铜和分割线的操作有自己的一套方法。   AD的相关文章可以参考之前的这篇:四层PCB核心板制作8——内电层电源平面分割。 绘制anti etch   allegro和AD...
  • ACM 平面分割问题

    千次阅读 2013-08-13 00:19:27
    (1) n条直线最多分平面问题  题目大致如:n条直线,最多可以把平面分为多少个区域。  析:可能你以前就见过这题目,这充其量是一道初中的思考题。但一个类型的题目还是从简单的入手,才容易发现规律。当有n-1...
  • 这类问题一般都有固定的公式,告诉大家一个技巧:二维的一般是an^2+bn+c, ...题目大致如:n条直线,最多可以把平面分为多少个区域。 析:可能你以前就见过这题目,这充其量是一道初中的思考题。但一
  • 【递推】【规律总结】直线、折线、曲线分割平面、平面分割空间问题
  • (一)直线分割平面问题 直线要想最多分割平面的前提:任意两条直线都要相交,任意三条直线不能交于同一点。 设n条直线最多分割平面为f(n)部分,一条直线分平面为两部分,f(1)=2;f(2)=4;f(3)=7;......,首先要弄明白...
  • HDU1290 平面分割空间

    2015-06-04 16:00:32
    分析:参考直线分割平面,我们知道平面分割与线之间的交点个数有关,即交点决定分割的线段和射线的条数,而线段和射线的条数决定分割的平面数,那么对应于三维空间当中,很容易想到,空间分割理应和平面的交线数有关...
  • 依据点的局部特征设置区域增长法生长准则对建筑物目标进行平面分割并对分割结果进行优化。实验结果表明,该方法不仅能快速有效提取大场景中的建筑物目标进行分割,并且解决了传统区域增长法不稳定的问题,提高了建筑...
  • 平面分割视图,可以随意进行视图切换,并且切换视图不需要删除视图。
  • 折线分割平面

    2014-11-03 12:38:03
    折线分割平面最大值
  • 提出了一种基于空间平面分割和投影变换的光场图像拼接算法。依据光场深度信息对目标场景进行平面拟合和分割,并根据颜色信息利用马尔可夫模型对分割结果进行了优化。利用不同视点间的光流信息求解投影变换矩阵,将...
  • PCB中的平面分割

    2021-01-19 23:43:05
    在 PCB 设计过程中,由于平面分割,可能会导致信号参考平面不连续,对于低低频信号,可能没什么关系,而在高频数字系统中,高频信号以参考平面作返回路径,即回流路径,如果参考?面不连续,信号跨分割,这就会带来...
  • 分割平面题解

    2020-02-23 19:58:52
    设有n条封闭曲线画在平面上,而任何两条封闭曲线恰好相交于两点,且任何三 条封闭曲线不相交于同一点,问这些封闭曲线把平面分割成的区域个数。 输入格式 一个数n(1≤n≤46341) 输出格式 一个数,这些曲线把平面...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 40,779
精华内容 16,311
关键字:

平面分割的方式