精华内容
下载资源
问答
  • 计算当前四边形是否为凸四边形

    千次阅读 2017-04-07 16:09:34
    下面算法为计算四边形是否为凸四边形,算法摘自gimp。

           发现自己的evernote保存了很多黑科技小算法,都忘记是什么时候摘录的。因为以前上学时做过图形学相关工作,下面算法为计算四边形是否为凸四边形,算法摘自gimp(https://www.gimp.org/)。关于gimp大家可以自行去查阅,也可以翻翻gimp的源码。编程水平提高,不是一味的多写代码就可以,还要时不时的看看高质量的开源代码,分析他们的代码组织方式,命名方式,逻辑调用方式,相信自己的水平也会跟着提高。下面是相关c代码:

    bool gimp_transform_polygon_is_convex(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4)
    {
    	double z1, z2, z3, z4;
    
    	z1 = ((x2 - x1) * (y4 - y1) - (x4 - x1) * (y2 - y1));
    	z2 = ((x4 - x1) * (y3 - y1) - (x3 - x1) * (y4 - y1));
    	z3 = ((x4 - x2) * (y3 - y2) - (x3 - x2) * (y4 - y2));
    	z4 = ((x3 - x2) * (y1 - y2) - (x1 - x2) * (y3 - y2));
    
    	return (z1 * z2 > 0) && (z3 * z4 > 0);
    }
    
    int main()
    {
    	double x1 = 10.0, y1 = 10.0;
    	double x2 = 50.0, y2 = 10.0;
    	double x3 = 10.0, y3 = 50.0;
    	double x4 = 35.0, y4 = 30.0;
    	bool result = gimp_transform_polygon_is_convex(x1, y1, x2, y2, x3, y3, x4, y4);
    
    	printf("result: %d\n", result);
    	system("pause");
    	return 0;
    }
           上面示例中,当x4小于等于30时,比如取值29,result输出为0,即非凸四边形。当x4大于30时,比如上面的取值35,result输出为1,即凸四边形。




    展开全文
  • 3.3 凸四边形逆映射

    2018-06-29 16:28:00
    一旦在一个多边形中找到了一个交点,就可以执行许多... 本节将介绍在凸四边形中获取点位置的算法,因为这种形状在各种应用中经常使用。通过算法计算参数值(u,v)。这个坐标对表示点相对于四条边的位置,作为从0到1的...

      一旦在一个多边形中找到了一个交点,就可以执行许多其他操作。如果多边形被分配了颜色模式,则必须检索交点处的颜色。类似的操作必须对其他纹理映射过程执行,比如bump映射。如果多边形是曲面上的一条路径,则必须从顶点的不同法线推导出精确法线。

      本节将介绍在凸四边形中获取点位置的算法,因为这种形状在各种应用中经常使用。通过算法计算参数值(u,v)。这个坐标对表示点相对于四条边的位置,作为从0到1的坐标轴对。问题如图9所示。

        

     

      注意,映射本身也可以用作内外测试。如果点在四边形之外,计算出的(u,v)对将落在(0…1,0…1)范围之外。

      从四边形的平面上的一个交点开始。

        

      用四个点来定义凸四边形:

        

      

       这些点定义u和v的轴,例如(P00,P10)定义了v=0时的u轴。平面的法线(不需要规范化)称为Pn。

      推导过程是相当复杂的,因此不包含在本讨论中。在[15]中有完整内容。插值必须计算许多因素。这些因素分为两类:点平面相关和平面相关。那些与平面有关的可以(而且应该)提前计算并传递给算法,除非它们是其他的限制因素,比如内存空间。这些平面相关的因素分别为:

        

      基本思想是为u定义一个函数,描述垂直平面(由u和四边形的坐标轴定义)与坐标系原点的距离:

        

      (E2)中计算的因子用于表示这个平面相关方程。 给定ri,包含这一点的垂直平面的距离为:

        

      设D(u) = Dr(u),解u,化简:

        

      这只是一个二次方程,它的解是直截了当的,因此不会被显示出来。为了获得更高的效率,一些其他因素对于每一个四边形和存储都值得一次计算。注意,只有当Du2!=0时才可以计算这些值。这些因素是:

        

      用(E2)和(E6)中的九个因子可以计算出u的值。 该解决方案有两种形式,取决于u轴是否平行。 通过以下条件确定轴是否平行:

         

        

        

      这两个中最多只有一个值位于范围(0 ... 1)内,那是有用的值。 如果最终的u值不在(0..1)中,则该点在四边形之外。 一个快速测试是测试Ka是否小于判别式(德尔塔)。 如果不是,则计算u0,否则为u1。 然后检查最终的u值,看它是否小于1.不是如果u0和u1都在有效范围内,那么四边形不是凸的。

       值v可以用类似的方式计算。 (E2)的相应因子是:

        

      (E7)至(E9)的相应方程式是通过用v代替u并用Nb代替Nc形成的。

      依赖于点平面的过程本身所需的计算是按照u或v值,8个加法/减法,7个乘法,1个平方根和4个比较。

    三角形逆映射

      逆映射也可以应用于三角形。 一种技术是将三角形传递给算法,将最后一个顶点加倍,以便为例程提供四点支持。 例如,如果标准程序按照P00,P10,P11,P01的顺序接受四边形的点,则P01再次发送三角形的最后点P11。 在这种情况下,(u,v)的映射将如图10所示,u轴定义为平行。

      当要映射的点位于加倍的顶点时会发生特殊情况。 在这个顶点,一个参数的所有值收敛。 在例子中,在图10中的P11处,所有的u值都是正确的。 由于这个奇点没有正确的答案,我们可以选择将其视为多边形之外的无效点,或者可以将其指定为任意值(零点可能是候选)。 通过检查方程(E8)中的除数是否等于零来测试这种特殊情况。

        

     

    转载于:https://www.cnblogs.com/TooYoungTsukasa/p/9244103.html

    展开全文
  • 凸四边形的最小外接矩形

    千次阅读 2019-02-26 09:09:58
    已知凸四边形的四条边及对角线长度,求具有最小面积的外接矩形的面积。 思路: 1 最初上来,没好的想法只能遍历,绕某个点转360度,求解析解; 2 发现不对,再遍历四个点; 3 绕重心旋转,遍历求最优近似解; 4...

    问题简单描述:

    已知凸四边形的四条边及对角线长度,求具有最小面积的外接矩形的面积。

    思路:

    1 最初上来,没好的想法只能遍历,绕某个点转360度,求解析解;

    2 发现不对,再遍历四个点;

    3 绕重心旋转,遍历求最优近似解;

    4 发现opencv有对应的函数minAreaRect,看源码或者调用

    5 发现有证明,某条边必在矩形上,化为只需求四次最优解;对每个需分析两个底角的钝角锐角情况,有三种情况。

    最终实现:

    第四种。解析实现。

    可推广到任意多个点的最小外接矩形。

    展开全文
  • 已知四边形(凸四边形)的四个点A、B、C、D(按逆时针顺序)的坐标,求点P是否在ABCD所围成的四边形内,可以通过向量叉乘的方法实现。        原文来自:...

           已知四边形(凸四边形)的四个点A、B、C、D(按逆时针顺序)的坐标,求点P是否在ABCD所围成的四边形内,可以通过向量叉乘的方法实现。

           原文来自:http://www.dewen.io/q/5805/Android

    先提供一种简单情景(假定四边形是一个凸四边形)的解决方法:

           原理:凸多边形内部的点都在凸多边形的边所在的向量的同一侧(前提是计算边所在的向量时采用的是同一个方向,同为顺时针或者同为逆时针),利用叉积求解。
           假设四边形四个顶点依次为A(x1,y1),B(x2,y2),C(x3,y3),D(x4,y4),待判断的点为P(x,y),如果点P在四边形内部,则向量AB * AP(注意:1.这是求叉积;2.AB、AP均为向量,也就等于(x2-x1) * (y-y1)-(y2-y1) * (x-x1))的值与BC*BP、CD * CP、DA * DP的值同号(若有等于零的情况,则表示P在边上,可以根据自己的喜好把它当做是内部或者外部),即四个值同为正或者同为负,则点P在ABCD内部,否则在外部。
           如果是凹四边形还要做一些其他处理,就是找到导致四边形为凹的那个顶点,也是借助于叉积(可以参考我的博客:http://tristan-xi.org/?p=113 (可惜博客已失效),只需记录中间哪个点所求的向量叉积与其它几点异号即可),然后把四边形分成两个三角形(三角形肯定是凸的了),再按照上面的方法计算叉积,即可解决。
           总结:叉积是判断多边形凹凸性以及点是否在凸多边形内部的利器。

           向量AB:(B.x - A.x , B.y - A.y);

           向量AP:(P.x - A.x , P.y - A.y);

           向量叉乘: ABxAP = (B.x - A.x) * (P.y - A.y) - (B.y - A.y) * (P.x - A.x);

    1. private boolean isPointInRect(int x, int y) {
    2. final Point A = mLBPoint;
    3. final Point B = mLTPoint;
    4. final Point C = mRTPoint;
    5. final Point D = mRBPoint;
    6. final int a = (B.x - A.x)*(y - A.y) - (B.y - A.y)*(x - A.x);
    7. final int b = (C.x - B.x)*(y - B.y) - (C.y - B.y)*(x - B.x);
    8. final int c = (D.x - C.x)*(y - C.y) - (D.y - C.y)*(x - C.x);
    9. final int d = (A.x - D.x)*(y - D.y) - (A.y - D.y)*(x - D.x);
    10. if((a > 0 && b > 0 && c > 0 && d > 0) || (a < 0 && b < 0 && c < 0 && d < 0)) {
    11. return true;
    12. }
    13. // AB X AP = (b.x - a.x, b.y - a.y) x (p.x - a.x, p.y - a.y) = (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x);
    14. // BC X BP = (c.x - b.x, c.y - b.y) x (p.x - b.x, p.y - b.y) = (c.x - b.x) * (p.y - b.y) - (c.y - b.y) * (p.x - b.x);
    15. return false;
    16. }

    转载自:https://blog.csdn.net/laukaka/article/details/45168439

    展开全文
  • moon game(凸四边形

    2016-07-28 20:37:06
    题意:给出n个点,求能够成的凸四边形的个数,题目已给出任意三个点不会在一条线上。链接:http://acm.fzu.edu.cn/problem.php?pid=2148思路:凹四边形任意三个点构成的三边形的面积一定有一个等于其余三个之和。...
  • 题目大意:给你一堆的点,然后判断最多能组成多少个凸四边形 解题思路:因为最多有30个点,所以直接暴力搜索就可以了 所学知识点: 如何判断凸四边形,在这种有坐标的情况下当然是用对角线相交来做了  如何...
  • 题意:T组样例,每组给定N个点 求可以构成的凸四边形的个数 思路:暴力枚举4个点:对于每4个点, 看看构成的是不是凹四边形,对于凹四边形 看下图 假设凹进去的那个点是a 则 S△abc +S△abd +S△acd=S△bcd 所以...
  • 题目大意:给出n个点,计算能组成的凸四边形个数 题目分析:朴素方法是枚举四个点,n^4的复杂度,而这个题目的n给到了700,显然是不行的,既然点的个数比较大,正难则反,我们考虑组合数学,首先n个点能组成C(n,4)...
  •  凸四边形中三个定点形成一个三角形 S ,第四个点必在这个三角形外,所以用第四个点与其他三个点相连,会形成三个三角形,如果这三个三角形的面积和与三角形 S 的面积相等则不是凸四边形;  如下图:  
  • HDU3629(凸四边形的个数) HDU3629计算几何 题目描述:给你n个点(4~700),问你能够成多少个不同的凸四边形。 解题报告: 暴力的话C(700,4)必然超时,发现,任何一个凹...
  • 1.实现可移动的凸四边形view package com.viking.qynet; import android.content.Context; import android.graphics.Canvas; import android.graphics.Paint; import android.support.annotation.Nullable; import...
  • 如果一个点在这个凸四边形内,那么按照顺时针方向,该点一定在每条边的右侧。可使用矢量叉积来看:该方法只适用于凸多边形。 矢量叉积:  计算矢量叉积是与直线和线段相关算法的核心部分。设矢量P = ( x1, y1...
  • https://vjudge.net/problem/FZU-2148 题目的大致意思就是给你n个点。让你计算这个点可以构成的凸四边形的个数。
  • 题意:给n个点,求图中凸四边形的数量。 解法:n 代码:#include #include using namespace std; struct point { int x,y; } points[40]; int abs(int k){if(k) return -k;return k;} int mult(point a,point...
  • 题意:给了n个点的坐标,问能有几个凸四边形 分析:数据规模小,直接暴力枚举,每次四个点判断是否会是凹四边形,条件是有一个点在另外三个点的内部,那么问题转换成判断一个点d是否在三角形abc内  易得S (abd) +...
  • 点在凸四边形内部

    2019-06-25 13:51:03
    一开始考虑,点在四边形内的几何体现是在四条直线的范围内,所以综合直线的五种形式,两点式比较合适建模。但这种有一点比较麻烦,就是直线的方向需要判断哪边是在四边形内部,需要额外的计算过程。 直线的五种形式 ...
  • 题意 : 给你n个点,判断能形成多少个凸四边形。 思路 :如果形成凹四边形的话,说明一个点在另外三个点连成的三角形内部,这样,只要判断这个内部的点与另外三个点中每两个点相连组成的三个三角形的面积和要与另外...
  • 数学原理 相邻两边的 bool gimp_transform_polygon_is_convex(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) { double z1, z2, z3, z4; z1 = ((x2 - x1) * (y4 -...
  • 题意:给n个点,无三点共线,求凸四边形个数。 对应凸四边形,有着一个 凹四边形,其实凹四边形,就相当于一个三角形,内部包含了一个点,则这样就可以构成一个凹四边形。 内部包含x个点,则x个凹四边形。 则题目...
  • 常会遇到判断一个质点是不是在四边形之内的问题。这是一个小方法,供参考。
  • 判断凸四边形_外积

    2019-08-12 22:18:16
    两个向量的外积定义: a = (x1, y1) b = (x2, y2) a ✖️ b = x1y2-x2y1 ... 具体参见上面博客。...夹角的性质,可以用来解决判别多边形,一个点在多边形内等问题。 例如:判别多边形: 向量每...
  • 凸四边形上 有8个点, 4个顶点 , 和 每2个顶点的中点。经过这8个点的每一条线段,将四边形分成2份, 求这两份面积最近的面积。  分析: 枚举, 每条线段, 计算 一边面积 S(较小), 另一边 面积 s1 = sum - S , ...

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 301
精华内容 120
关键字:

凸四边形