精华内容
下载资源
问答
  • 向量法计算多边形面积

    千次阅读 2019-10-22 09:59:53
    三角形面积为两边向量叉积除以2。  这是Java代码,目前是第3版,已经尽可能优化了,相比初版有25%的性能提升。 /** * 平面多边形面积算法3,用原点为基点(不需要从图形边线上取点)<br/> * 多计算一...

      计算多边形面积的方法为将多边形分解成多个三角形,然后把这些三角形的面积相加。三角形面积为两边向量叉积除以2。

      这是Java代码,目前是第3版 ,已经尽可能优化了,相比初版有25%的性能提升。

    	/**
    	 * 平面多边形面积算法3,用原点为基点(不需要从图形边线上取点)<br/>
    	 * 多计算一条线段,但减少了每一步的两次减法(起于原点的向量等于节点的坐标),使误差减小,每一步的计算量减少。
    	 * 
    	 * @return 正方向(x轴向y轴旋转方向)圈成的面积(如果有反方向的圈,则面积会被抵消,导致结果小于直观观测的面积或为负数)
    	 */
    	private static final double getPolygonAreaMethodC(double... points) {
    		if (points.length < 6) {
    			// 无法构成多边形
    			return 0;
    		}
    		final int pointArrayLength = points.length & (~1);
    		// final int pointCount = pointArrayLength / 2;
    
    		double area = 0.0;
    
    		double dx1, dy1;
    		double dx2, dy2;
    
    		// 从原点到该点的向量
    		dx1 = points[pointArrayLength - 2];
    		dy1 = points[pointArrayLength - 1];
    		for (int i = 0; i < pointArrayLength;) {
    			// 从原点到该点的向量
    			dx2 = points[i++];
    			dy2 = points[i++];
    
    			// 三角形的面积2倍,平行四边形面积。为提高性能,不在循环中进行面积减半
    			final double subArea = dx1 * dy2 - dx2 * dy1;// 由jvm进行智能内联,分出这一步不会影响性能
    			area += subArea;
    
    			// 向量传递
    			dx1 = dx2;
    			dy1 = dy2;
    		}
    
    		// 最后统一除以2,提高性能
    		return area / 2;
    	}

      除了可以用来计算面积,还可以进行分布式计算π。把半径R的圆分解成很多边的多边形,每台计算机只计算其中的一部分。然后将每台计算机算出的面积相加得到面积S。π=S/(R^2)。这只是一种用法,事实上并不建议用此方法计算π。最好的办法仍然是可迭代的,所以分布式计算π并没有优势。

      下面是C++的版本,也是初版,作为参考。

            /**
    	 * 平面多边形面积
    	 *
    	 * @return
    	 */
    double getPolygonArea(double *points, int length) {
        if (length < 6) {
            // 无法构成多边形
            return 0;
        }
        double area = 0.0;
        double x0 = points[0], y0 = points[1];
    
        double dx1, dy1;
        double dx2, dy2;
    
        dx1 = points[2] - x0;
        dy1 = points[3] - y0;
        for (int i = 4; i < length - 1; i += 2) {
            dx2 = points[i] - x0;
            dy2 = points[i + 1] - y0;
    
            double subArea = (dx1 * dy2 - dx2 * dy1) / 2.0;
            area += subArea;
    
            dx1 = dx2;
            dy1 = dy2;
        }
        return area;
    }

    Java并发版本(有依赖项,不可直接使用)。

    依赖项1:ParallelTask.parallelFor其实是线程池。第一个参数0代表WorkSteal线程池。第二个参数代表Lambda执行的次数,一般取CPU核心数。Lambda的参数threadOrder代表此Lambda所在线程启动的顺序。静态的方法parallelFor代表内部生成线程池,并在返回之前关闭和等待线程池任务结束。ParallelTask是一个实现了十几种动态与静态parallelFor的大文件,不方便上传。

    依赖项2:StaticSystemUtils.getCPUCoreCount就是Runtime.avaliableProcesses()。StaticSystemUtils是一个获取系统信息的大文件,不方便上传。

    依赖项3:StaticMathUtils.sum就是一个求和函数。StaticMathUtils是一个包含数十种算术方法,几千行的大文件,不方便上传。

    	/**
    	 * 平面多边形面积算法3,用原点为基点(不需要从图形边线上取点)<br/>
    	 * 多计算一条线段,但减少了每一步的两次减法(起于原点的向量等于节点的坐标),使误差减小,每一步的计算量减少。
    	 * 
    	 * @return 正方向(x轴向y轴旋转方向)圈成的面积(如果有反方向的圈,则面积会被抵消,导致结果小于直观观测的面积或为负数)
    	 */
    	public static final double getPolygonAreaParallel(double... points) {
    		if (points.length < 6) {
    			// 无法构成多边形
    			return 0;
    		}
    		final int pointArrayLength = points.length & (~1);
    		final int pointCount = pointArrayLength / 2;
    
    		double area = 0.0;
    
    		final int taskCount = Math.min(StaticSystemUtils.getCPUCoreCount(), pointCount);
    		final double[] eachArea = new double[taskCount];
    		ParallelTask.parallelFor(0, taskCount, threadOrder -> {
    			final int from = (int) ((long) threadOrder * pointArrayLength / taskCount) & (~1);
    			final int to = (int) ((long) (threadOrder + 1) * pointArrayLength / taskCount) & (~1);
    
    			double threadArea = 0.0;
    
    			double dx1, dy1;
    			double dx2, dy2;
    
    			// 从原点到该点的向量
    			if (threadOrder == 0) {
    				dx1 = points[pointArrayLength - 2];
    				dy1 = points[pointArrayLength - 1];
    			} else {
    				dx1 = points[from - 2];
    				dy1 = points[from - 1];
    			}
    			for (int i = from; i < to;) {
    				// 从原点到该点的向量
    				dx2 = points[i++];
    				dy2 = points[i++];
    
    				// 三角形的面积2倍,平行四边形面积。为提高性能,不在循环中进行面积减半
    				final double subArea = dx1 * dy2 - dx2 * dy1;// 由jvm进行智能内联,分出这一步不会影响性能
    				threadArea += subArea;
    
    				// 向量传递
    				dx1 = dx2;
    				dy1 = dy2;
    			}
    
    			eachArea[threadOrder] = threadArea;
    		});
    
    		area = StaticMathUtils.sum(eachArea);
    
    		// 最后统一除以2,提高性能
    		return area / 2;
    
    	}

     

    展开全文
  • 二维向量叉乘,得到的新的向量是长度为原来两向量的组成的平行四边形的面积,方向为右手法则确定出来的方向。需要用三维中的行列式来求证二维向量如下:(可设j为(0,0,1),由a,b出来的向量为(0...

    全篇基于平面多边形
    先看http://www.cnblogs.com/TenosDoIt/p/4047211.html
    本文主要目的是说明 多边形 顶点 的 顺时针逆时针 方向 对求面积的 便利性。
    二维向量叉乘,得到的新的向量是长度为原来两向量的组成的平行四边形的面积,方向为右手法则确定出来的方向。需要用三维中的行列式来求证二维向量如下:

    (可设j为(0,0,1),由a,b求出来的向量为(0,0,x1*y2-x2*y1))

    也就是说二维平面上,已知两点A(x1,y1)和B(x2,y2),与原点O组成的三角形面积为  |x1*y2-x2*y1|/2 。


    (叉乘不同于点乘,点乘公式为a•b = |a||b|cosθ ,点乘的结果是一个标量,等于向量大小与夹角的cos值的乘积。设a为(x1,y1,z1) ,b 为(x2,y2,z2), 则a*b = x1*x2+y1*y2+z1*z2)

     

    从上面的公式可以发现,向量乘积的前后顺序是z值的。向量法求平面多边形面积 与 取点的方向有关系。如果是顺时针方向,求取的面积(多边形 每条边的顶点与原点组成向量的叉积的z值 的和)值是负的,如果是逆时针方向,求取的面积值是正的。一种理解就是根据向量叉积的“右手法则”,顺时针z是向下的,逆时针z是向上的,多多边形顺时针方向取点或逆时针取点决定了累积起来的z的总的方向。注意这个规律与取的参考点(O点)是没有关系的,即使取多边形内部的点或者取多边形线上的点,都满足这个规律。可以参看下面的例子,然后自行扩展。
      (为了方便计算多边形选用直角三角形)

    假设向量为(x,y,z)  A(3,6,0) B(3,2,0) C(7,3,0)  O(0,0,0) 三角形面积为4*4/2 =  8
    再结合博客链接中的知识:逆时针取多边行顶点 ((OAxOB).z+(OBxOC).z+(OCxOA).z)/2 = ((3*2-6*3)+(3*3-2*7)+(7*6-3*3))/2 = 8 ,等于多边形ABC的面积;而顺时针取多边形顶点((OBxOA).z+(OAxOC).z+(OCxOB).z)/2 = ((6*3-3*2)+(2*7-3*3)+(3*3-7*6))/2 = -8 等于多变形ABC面积的负值。可以用递归法推测正确性。往多边行扩展,因为可以将多边形拆分成多个三角形,辅助的边的叉积的z值项 在最后在总的求和时 是都会被相互抵消的。实际最终的有效的求和累积项 都是 实边的顶点 与 原点 组成向量的叉乘 z值的累加。

    向量法求面积可以无差错的拓展到凹多边形。

    static int calcAreaOfPolygon2D(const int* verts, const int nverts)//来自于recast,注意这里是int类型,代码是特殊用途,主要用作参考
    {
    	int area = 0;
    	for (int i = 0, j = nverts-1; i < nverts; j=i++)
    	{
    		const int* vi = &verts[i*4];
    		const int* vj = &verts[j*4];
    		area += vi[0] * vj[2] - vj[0] * vi[2];
    	}
    	return (area+1) / 2;
    }
    


    另外面积法判断点是否在多边形内,只对凸多边形有效,并且还必须对上面的z值 取绝对值 才能让结果有效。

     

    点在多边形内,最好的办法有两个:
    1、判断合适的过点的射线与多边形的交点个数,这个链接讲解比较容易理解且最高效简洁。
    2、边与点的夹角和。
    可参考https://blog.csdn.net/gkingzheng/article/details/81836308

    展开全文
  • 下面就写一下如何用向量法求多边形面积向量面积 上图说明了如何利用向量求得三角形的面积,下面介绍一下所谓的右手法则: 如图,2个三角形ABC,唯一的区别在于上面的三角形...

    首先看一道hdoj的算法题:hdoj-2036-改革春风吹满地

    该题题意就是逆时针给出点的坐标,求这个多边形的面积。下面就写一下如何用向量积法求多边形面积。

    向量积法与面积




    上图说明了如何利用向量求得三角形的面积,下面介绍一下所谓的右手法则:



    如图,2个三角形ABC,唯一的区别在于上面的三角形ABC的标识是逆时针,而下面的三角形标识是顺时针。如果利用向量叉积,由于乘的是向量的绝对值,所以AB与AC在上或者在下是没有区别的。但是如果不使用绝对值,而是写成行列式的形式,就要考虑方向的问题了。所以简单(不负责任)地说,所谓右手法则就是:当逆时针(右手大拇指朝向)方向排列点的时候组成的向量求的的结果是正数,反之是负数。(上面并不是标准解答,关于定义可参考wikipedia)那么以上2个三角形转化为行列式的时候就是下图:



    根据行列式的性质,我们也能知道两者的值是相反的。
    既然如此,我们在得到逆时针序的3点坐标的情况下,利用行列式即可得到面积。例:



    核心代码为:

    int S = (0.5)*(x1*y2+x2*y3+x3*y1-x3*y2-x2*y1-x1*y3);

    N边形划分为三角形




    如上图,任何一个N边形都能划分为N-3个三角形,那么根据上面的公式,我们逆时针获取点,就像下图一样,令单个三角形的面积和累加即可得到N边形的面积。



    因为右手定则,一定要逆时针。而该题输入要求就正好是逆时针输入。并且可以看出:A点恒不变,另两个点是移动状态,那么我们就可以写出代码:

    int beginx, beginy, lastx, lasty, x, y;
    double ans;
    cin >> beginx >> beginy >> lastx >> lasty >> x >> y;
    ans = (double)(0.5)*(beginx*lasty + lastx*y + x*beginy - x*lasty - lastx*beginy - beginx*y);

    以上代码可以得到第一个三角形ABC的面积,下面进入循环:


    n -= 3;
    while (n--) {
    	cin >> x >> y;
    	ans += (double)(0.5)*(beginx*lasty + lastx*y + x*beginy - x*lasty - lastx*beginy - beginx*y);
    	lastx = x;
    	lasty = y;
    }

    最终即可得到解ans。

    凹边形面积


    我们上面的例子都是凸边形,对于凹边形而言我们仍然可以得到正解,就是因为有右手定则。



    如上图的凹边形,我们仍然按照逆时针顺序来求解,第一个三角形ABC,得到实际上是包括虚线在内的整体面积,那么第二个三角形ACD,可以看到是顺时针了,绝对值是有虚线的ACD面积,那么因为是顺时针,用行列式求出的值是负数。两个行列式值相加,正好是大三角形(包括虚线)ABC面积减去小三角形ACD的面积。得到的仍然是凹边形的面积。

    C++代码


    已AC

    #include<iostream>
    
    
    using namespace std;
    
    
    int main() {
        int n;
        while (cin >> n) {
            if (n == 0) break;
            int beginx, beginy, lastx, lasty, x, y;
            double ans;
            cin >> beginx >> beginy >> lastx >> lasty >> x >> y;
            ans = (double)(0.5)*(beginx*lasty + lastx*y + x*beginy - x*lasty - lastx*beginy - beginx*y);
            lastx = x;
            lasty = y;
            n -= 3;
            while (n--) {
                cin >> x >> y;
                ans += (double)(0.5)*(beginx*lasty + lastx*y + x*beginy - x*lasty - lastx*beginy - beginx*y);
                lastx = x;
                lasty = y;
            }
            printf("%.1lf\n", ans);
        }
    
    
        system("pause");
        return 0;
    }


    展开全文
  • 题目链接: ... 1305 - Area of a Parallelogram ...A parallelogram is a quadrilateral with...涨姿势了:平行四边形的面积可以用两相邻向量求,公式就是 x1 * y2 - x2 * y1 这里有个详细的链接: 点击打开链接

    题目链接:点击打开链接

    1305 - Area of a Parallelogram
    Time Limit: 1 second(s)Memory Limit: 32 MB

    A parallelogram is a quadrilateral with two pairs of parallel sides. See the picture below:

    Fig: a parallelogram

    Now you are given the co ordinates of A, B and C, you have to find the coordinates of D and the area of the parallelogram. The orientation of ABCD should be same as in the picture.

    Input

    Input starts with an integer T (≤ 1000), denoting the number of test cases.

    Each case starts with a line containing six integers Ax, Ay, Bx, By, Cx, Cy where (Ax, Ay) denotes the coordinate of A(Bx, By) denotes the coordinate of B and (Cx, Cy) denotes the coordinate of C. Value of any coordinate lies in the range [-1000, 1000]. And you can assume that A, B and C will not be collinear.

    Output

    For each case, print the case number and three integers where the first two should be the coordinate of D and the third one should be the area of the parallelogram.

    Sample Input

    Output for Sample Input

    3

    0 0 10 0 10 10

    0 0 10 0 10 -20

    -12 -10 21 21 1 40

    Case 1: 0 10 100

    Case 2: 0 -20 200

    Case 3: -32 9 1247



    题解:点到直线的距离公式啊,有木有

    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    double ax,ay,bx,by,cx,cy;
    int main()
    {
    	int t,text=0;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%lf %lf %lf %lf %lf %lf",&ax,&ay,&bx,&by,&cx,&cy);
    		double midx=(ax+cx)/2;
    		double midy=(ay+cy)/2;
    		double dx=midx*2-bx;
    		double dy=midy*2-by;
    //		double base=sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
    		double height=(ax-bx)*dy-(ax-bx)*ay+(by-ay)*dx+(ay-by)*ax;
    		double ans=abs(height);
    		printf("Case %d: %.lf %.lf %.lf\n",++text,dx,dy,ans);
    	}
    	return 0;
    }

    涨姿势了:平行四边形的面积可以用两相邻向量求,公式就是 x1 * y2 - x2 * y1

    这里有个详细的链接:点击打开链接

    展开全文
  • 高中数学|数列求和的几种策略点击上方蓝字关注“公众号”向量公式之用平面向量求三角形面积在学习向量时,我们能体会到向量的表达形式的多样化和直观性,而这些特点使解题更加简洁,可以省略大量繁琐的过程。...
  • 向量积计算三角形面积

    万次阅读 2020-02-09 17:57:33
    向量积:数学中又称外积、叉积,物理中称矢积、叉乘,是一种在向量空间中向量的二元运算。 向量积可以被定义为: ...所以三角形ABC的面积,根据向量积的意义,可得三角形ABC的面积S: a×b=(ay...
  • 简单理解利用向量叉积(行列式)三角形面积

    万次阅读 多人点赞 2020-04-19 21:07:07
    已知三个顶点坐标,若要求三点围成的三角形的面积,对计算机而言,我认为这个公式是最方便的:
  • 向量OA(x1,y1),OB(x2,y2) 平面叉积坐标表达式:S=x1*y2-x2*y1;要取绝对值哦; 若为ping'xing'si
  • 给你三个点,表示一个三角形的三个顶点,现你的任务是出该三角形的面积 输入 每行是一组测试数据,有6个整数x1,y1,x2,y2,x3,y3分别表示三个点的横纵坐标。(坐标值都在0到10000之间) 输入0 0 0 0 0 0表示输入...
  • 向量叉乘计算多边形面积

    千次阅读 2020-05-16 21:51:32
    三角形面积可以用向量积来计算:S = 1 / 2 * ab x ac =1 / 2 * |ab| * |ac| * sin @(x表示叉乘,@表示ab和ac两边之间的夹角) 为什么要乘1/2呢? 因为ab x ac 出来的是ab和ac为边的四边形的面积。 多边形可以拆成多...
  • 原文地址 利用向量积(叉积)计算三角形的面积和多边形的面积向量的数量积和向量积: (1)向量的数量积 (1)向量向量积 ...两个向量a和b的叉积(向量积)可以被...三角形ABC的面积,根据向量积的意义,...
  • 1.向量法: 向量的叉乘在定义上有:两个向量进行叉乘得到的是一个向量,方向垂直于这两个向量构成的平面,大小等于这两个向量组成的平行四边形的面积。 这样就可以通过先向量AB(x2-x1,y2-y1),AC(x3-x1,y3-x3...
  • 值:空间向量法向量

    千次阅读 2017-08-19 19:48:03
    空间向量法向量计算方法。
  • 本人第一次不是用向量法来做,把直接n边形分成n-2个三角形,最终总是过不了,一查资料才知道,多边形分凹凸多边形,凹多边形使用直接分割法,不太好做。 下面先给大家分享错误代码:(只适用与凸多边形) /* 把n...
  • } 二、凹多边形的面积,需要用到向量,也称叉积 向量三角形面积公式:S = | 向量a * 向量b | * 1/2 即 S = 1 / 2 * | 向量a | * | 向量b | * sin(θ) (θ ∈ 0° ~ 180°) 1. 因为用向量积(叉积)...
  • 向量法计算体积的关键是把立体分解成锥体。 立体必须是由一系列有限平面多边形封闭而成的,可以使用多边形,但一定要是平面多边形。必须密封,如果不密封就会导致体积误差。 可取任意点为基准点(事实上二维空间...
  • 向量法计算平面与直线的交点

    千次阅读 2019-11-13 16:00:37
     已知有平面上三个点(ABC)坐标,直线上两个点(DE)坐标,平面ABC与直线DE的交点坐标。  解: /** * 平面与直线的交点 * * @param plantA * @param plantB * @param plantC * @param lineD ...
  • 题意:给你一个凸多边形,其中三个顶点围成的最小三角形面积 数据相当大 暴力GG ... 前置技能(向量叉乘求面积):https://www.cnblogs.com/xiexinxinlove/p/3708147.html #include<cstdio> #...
  • 利用向量求点到线的最短距离

    千次阅读 2020-02-20 16:24:03
    利用向量积(叉积)计算三角形的面积和多边形的面积向量的数量积和向量积: (1)向量的数量积 (1)向量向量积 两个向量a和b的叉积(向量积)可以被定义为: 在这里θ表示两向量之间的角夹角(0° ≤ ...
  • 如果两个向量能够构成平行四边形,其面积可表示为 area= |(x1*y2-X2*y1)|; 以下转载详细解析 原文链接:http://blog.csdn.net/zhangxaochen/article/details/80270031. 想了一下首先想到的是高中解析几何知识。...
  • Meshlab计算点云法向量求三角网格

    千次阅读 热门讨论 2018-05-27 17:20:17
    最近在看曲面重建,感觉... 今天主要给大家演示一下如何对点云obj模型进行法向量取和曲面重建。1.在meshlab中导入一个obj模型,此模型是我重采样后导出的模型(没显示特征点),所以除了点信息(V),任何...
  • 问题:假设我们世界空间中有一个任意三角形,且已知三角形各个顶点ABC的坐标,三角形的外心P和外心所在的法向量n,如下图: 如果依稀还记得初中几何,就知道一个平面三角形外心计算规则:三角形任意两边的中垂线...
  • struct Point{//两个点相减是向量,二维向量叉乘是平行四边形面积 int x,y; Point(int _x = 0, int _y = 0) :x(_x), y(_y) {} Point operator -(const Point &amp;p)const { return Point(x - p.x, y - p.y)...
  • 采用相关系数选择耕地面积的影响因子,通过粒子群优化算法对最小二乘支持向量机参数进行优化,最后建立耕地面积与影响因子之间复杂的非线性关系模型。采用湖南省耕地面积数据对模型性能进行验证,结果表明,相对于...
  • 向量叉乘 a=(x1,y1)b=(x2,y2)a=(x_1,y_1)\quad b=(x_2,y_2)a=(x1​,y1​)b=(x2​,y2​) ...二维叉乘的数值概念为以两个向量为边所围成的平行四边形面积 集合概念为a→与b→\overrightarrow{a}与\ov
  • 线性代数:切线空间和法向量变换

    千次阅读 2018-11-28 14:15:37
     首先切线是为了计算顶点法向量,顶点法向量这个参数是相当重要的,光照计算,反射计算,光线追踪都需要这个顶点法向量,这个很容易理解吧。  一般情况下,一个美术人员(或者咱码农亲自上阵)在3dmax or maya...
  • 梯度向量与梯度下降

    万次阅读 多人点赞 2017-10-27 15:37:16
    要掌握“梯度下降”,就需要先搞清楚什么是“梯度”,本文将从这些基本概念:方向导数(directional derivative)与偏导数、梯度(gradient)、梯度向量(gradient vector)等出发,带您领略
  • 向量及平面方程

    千次阅读 2019-03-03 17:26:18
    向量及平面方程 定理1:向量a != 0,向量b//a的充要条件是:存在唯一实数k,使b=ka; 向量r的坐标分解式:r=xi+yj+zk,其中xi,yj,zk称为r沿三个坐标轴的分向量向量r=(x,y,z),模长|r|=根号下(x2+y2+z^2) ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,844
精华内容 5,937
关键字:

向量法求面积