精华内容
下载资源
问答
  • 凸多边形

    2019-01-14 21:12:14
    题目1 : 凸多边形 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 给定一个凸多边形的N个顶点。你需要在凸多边形内找到M个点,使得这M个点也围成一个凸多边形,并且围成的面积尽可能大。 输入 第一...

    题目1 : 凸多边形

    时间限制:10000ms

    单点时限:1000ms

    内存限制:256MB

    描述

    给定一个凸多边形的N个顶点。你需要在凸多边形内找到M个点,使得这M个点也围成一个凸多边形,并且围成的面积尽可能大。

    输入

    第一行包含两个整数N和M,意义如前文所述。

    接下来N行,每行两个整数Ai和Bi,表示按照逆时针顺序排列的凸多边形顶点坐标。

    对于30%的数据,满足N<=5

    对于100%的数据,满足N<=100

    对于100%的数据,满足3<=M<N, |Ai|,|Bi|<=10000

    输出

    输出新凸多边形最大的面积,保留两位小数。

    样例输入

    4 3
    0 0
    1 0
    1 1
    0 1

    样例输出

    0.50大神思路:https://hihocoder.com/discuss/question/5158

    《凸多边形》题目分析
    本题可以用动态规划解决。
    
    week191
    
    如上图所示,我们把凸多边形的N个顶点按顺序编号0~N-1。
    
    f[i][j][k]表示起点是i,最后一个点是j的k边形,面积最大是多少。
    
    转移方程:
    
    f[i][j][k] = max{f[i][l][k-1] + S(i, l, j) | i < l < j}
    
    其中S(i, l, j)是三角形ilj的面积。l是我们枚举的第k-1个点。
    
    复杂度O(N^4)。
    
    另外这道题还有一种"随机乱搞"的做法。
    
    1) 首先随机选择M个点,计算当前M边形的面积。
    
    2) 然后枚举一对点A和B,其中A是选中的点,B不是选中的点。
    
    3) 如果改成选B不选A,能使多边形面积变大,就改选并重新计算面积。
    
    4) 重复枚举一对点的过程,直到无法通过改选使面积增大。
    
    5) 重复若干次随机选择初始M个点的过程。取其中最大能达到的面积。
    
    import java.util.Scanner;
    
    public class Main {
    
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int N = scanner.nextInt();
            int M = scanner.nextInt();
            int[][] p = new int[N][2];
            for (int i = 0; i < N; i++) {
            	p[i][0] = scanner.nextInt();
            	p[i][1] = scanner.nextInt();
            }
            System.out.printf("%.2f", maxArea(p, N, M));
            scanner.close();
        }
        
        private static double maxArea(int[][] p, int N, int M) {
        	double[][][] dp = new double[N][N][M + 1];
        	for (int k = 3; k <= M; k++) {
        		for (int i = 0; i < N; i++) {
        			for (int j = i + k - 1; j < N; j++) {
        				double smax = 0;
        				for (int l = i + k - 2; l < j; l++) {
        					double s = dp[i][l][k - 1] + area(p[i], p[l], p[j]);
        					smax = Math.max(smax, s);
        				}
        				dp[i][j][k] = smax;
        			}
        		}
        	}
        	double maxArea = 0;
        	for (int i = 0; i < N; i++) {
        		for (int j = i + M - 1; j < N; j++) {
        			maxArea = Math.max(maxArea, dp[i][j][M]);
        		}
        	}
        	return maxArea;
        }
        
        private static double area(int[] a, int[] b, int[] c) {
        	return Math.abs(a[0]*b[1]+b[0]*c[1]+c[0]*a[1]-a[1]*b[0]-b[1]*c[0]-c[1]*a[0]) * 0.5;
        }
        
    }
    

     

    展开全文
  • 计算任意两个凸多边形 的IOU值。(根据两个凸多边形的顶点坐标计算)分别计算每一个凸多边形的面积。利用向量叉乘求面积。计算两个凸多边形的相交面积。两个凸多边形相交区域构成的多边形L,先求出L的各个顶点,然后...

    e1d96c785cf0c5cb8927b01cc9323a88.png

    计算任意两个凸多边形

    的IOU值。(根据两个凸多边形的顶点坐标计算)
    1. 分别计算每一个凸多边形的面积。利用向量叉乘求面积。
    2. 计算两个凸多边形的相交面积。两个凸多边形相交区域构成的多边形L,先求出L的各个顶点,然后再求出面积。L的顶点包括凸多边形
      中的顶点、
      中的顶点以及
      的交点。

    一、计算凸多边形的面积

    我们知道三角形abc的面积可以由1/2absin(θ)求出,其中θ为边a与b的夹角,根据向量叉乘可求出三角形abc的有向面积

    1d7992eb19fff6b83178e44ef7441359.png

    。另外还可根据叉乘的方向判断abc三点的排列顺序。

    d5d03d3adf67ca9f414c703d32dd2b2c.png

    ,表示abc顺时针方向排列;

    a40ace992383d19e5f7f83d8d3fa3800.png

    ,表示abc逆时针排列,这个与向量叉乘的右手法则有关,需要注意到在计算机中表示点时,y轴是向下的,因此叉乘的方向垂直于平面向里为正,向外为负。

    62b580a7208dfb8c9a27e0f8e1eb87b1.png
    图一 向量叉乘,遵循右手法则

    凸多边形面积的求解:可以从某一个顶点出发划分成多个三角形,求出多个三角形的面积相加可得凸多边形的面积。如图所示,凸多边形abcdef的面积为

    97853eda5a81761068809fe766f9443a.png

    二、计算两个凸多边形相交区域构成的凸多边形的面积

    59752584645ece50e561c12b33cbeb93.png
    图二 两个凸多边形K1与K2相交区域构成凸多边形L

    (a)左侧凸多边形

    在右侧凸多边形
    内的顶点

    判断一个点是否在一个凸多边形内部,依旧可以根据向量叉乘计算,如果点在凸多边形的内部,则点与多边形的各个顶点(顺时针方向或逆时针方向依次排列)构成的向量依次进行叉乘得到的方向值是一致的。如果一个点在凸多边形的外部,则点与多边形的各个顶点(顺时针方向或者逆时针方向依次排列)构成的向量中依次进行叉乘必然存在相邻的两个叉乘方向是相反的。

    例如在图三左侧,点在凸多边形的内部,

    be183eb16af0ad47b5f3f79213ce0e0e.png

    的方向一致。在图三右侧,点在凸多边形的外部,存在相邻的两个叉乘方向

    d23d0c5c553f04065edc52ae6217157e.png

    方向相反,以及

    48d8c05eeba85319f7512e3bb54f04ff.png

    的方向相反。

    另外,如果得到叉乘值为0,说明点在凸多边形的某条边上,因此也可以直接判别为内点即可。

    5620361ffcc03458d5c92ba3b07204a8.png
    图三 判断点p在凸多边形abcdef的内部还是外部

    (b)如何得到两个凸多边形相交的交点

    先判断两条线段是否相交。仍然可以根据向量叉乘来判断。

    039d1851a6030cd4c1c412c90d649c05.png
    图四 判断两条线段是否相交

    线段ab与线段cd是否相交,需要判断

    5dfb5c58b0be06ed53a8d23da03954e8.png

    是否相异(相异说明一条线段被另一条线段分成了两段),如果这两组得到的方向均相异,两条线段才是相交的,否则不相交。如果这里得到的叉乘值为0,则不计入交点,因为在计算顶点时,在某条边上的点已经被计算进去,因此此时不需要考虑两条线段是否在一条直线上的情况。

    如果两条线段相交,如何求交点。这里依然可以根据向量的叉乘进行运算:

    283f3ca27bb3c19c904985374352d5e9.png
    图五 求两条线段相交的交点坐标

    如图五所示,求线段ab和线段cd的交点o,其中线段ce与线段ab平行且相等。线段ag垂直于线段cd,线段ef垂直于线段cd,可以看到

    相似,

    69312d99c0d63d91898892168cace7eb.png

    因此

    cd3a15ec6e0bab772dc7b88b507914be.png

    若点o的坐标为

    ,则

    00556ab3c29b8490b19d9c03e773899a.png

    最终,将左侧凸多边形在右侧凸多边形中的顶点、右侧凸多边形在左侧凸多边形中的顶点以及两个凸多边形的交点去重后进行顺时针排序。这里顺时针排序依旧可以根据向量叉乘的方向去排序(当叉乘值小于0时交换点的位置即可,最终以顺时针排序)。继而利用叉乘求出相交区域构成的凸多边形的面积。

    三、标注方式为带旋转角度的矩形。

    如果我们的标注方式是带旋转角度的矩形(中心点坐标

    、长和宽
    、旋转角度θ),那么依然可以根据我们上面讲述的方法求得两个带旋转角度的矩形之间的IOU值。不过需要先求出旋转矩形的四个点的坐标,这里需要依据仿射矩阵进行求解。

    二维仿射变换一般包含平移、缩放、旋转、剪切。

    二维平面上有一个点

    经过某种变换变为
    。变换矩阵为

    aa3c6a71a7a1914a2d3a9cfe0ce22091.png

    ,其中

    表示进行缩放,旋转,对称,剪切等变换。
    表示平移变换。

    我们很容易得知矩形在旋转角度为θ = 0时四个顶点的坐标,可根据仿射变换计算旋转θ(顺时针)后的坐标,变换矩阵为

    145eb27b784e32c9364a7ee2668984db.png

    ,即点

    绕中心点
    旋转θ角度后变为
    ,公式为:

    62bce6541a784cc24eaf8201c5a10822.png

    可以注意到旋转矩阵相当于先移动中心点到原点,进行旋转,再从原点移动到中心点。即

    4133f5744fa430c576ffa7c620700dd7.png
    展开全文
  • 题目链接: ...(凸多边形的定义)注:顶点个数至少为 3 个且不超过 10,000。坐标范围为 -10,000 到 10,000。你可以假定给定的点形成的多边形均为简单多边形(简单多边形的定义)。换句话说,保每...

    682900697c1928039177a87372b6fd36.png

    题目链接: https://leetcode-cn.com/problems/convex-polygon

    难度:中等

    通过率:35.9%

    题目描述:

    给定一个按顺序连接的多边形的顶点,判断该多边形是否为凸多边形。(凸多边形的定义)

    注:

    1. 顶点个数至少为 3 个且不超过 10,000。
    2. 坐标范围为 -10,000 到 10,000。
    3. 你可以假定给定的点形成的多边形均为简单多边形(简单多边形的定义)。换句话说,保
    4. 每个顶点处恰好是两条边的汇合点,并且这些边 互不相交 。

    示例:

    示例 1:

    [[0,0],[0,1],[1,1],[1,0]]
    
    输出: True

    解释:

    f7c8fc27fdcf3f41a8936d9964cbd61f.png

    示例 2:

    [[0,0],[0,10],[10,10],[10,0],[5,5]]
    
    输出: False

    解释:

    cd101e22000719062d69a9cd97d7f38e.png

    思路:

    叉乘判断

    A(x1,y1),B(x2,y2),C(x3,y3)则三角形两边的矢量分别是:

    AB=(x2-x1,y2-y1), AC=(x3-x1,y3-y1)

    ABAC的叉积为:(2*2的行列式) 值为:(x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)

    利用右手法则进行判断:

    如果AB*AC>0,则三角形ABC是逆时针的

    如果AB*AC<0,则三角形ABC是顺时针的

    因为不知道顶点是顺时针输入,还是逆时针输入,所以要记录符号,后面点叉乘如果一样就是凸多边形。

    代码:

    class Solution:
        def isConvex(self, points: List[List[int]]) -> bool:
            def cal_cross_product(A, B, C):
                AB = [B[0] - A[0], B[1] - A[1]]
                AC = [C[0] - A[0], C[1] - A[1]]
                return AB[0] * AC[1] - AB[1] * AC[0]
    
            flag = 0
            n = len(points)
            for i in range(n):
                # cur > 0 表示points是按逆时针输出的;cur < 0,顺时针
                cur = cal_cross_product(points[i], points[(i + 1) % n], points[(i + 2) % n])
                if cur != 0:
                    # 说明异号, 说明有个角大于180度
                    if cur * flag < 0:
                        return False
                    else:
                        flag = cur
            return True
    展开全文
  • 题目是这样子的:有一凸多边形,经过一次裁剪,要证明它最多能够获得一个新增的凸多边形。 如图:裁剪一个非凸多边形一次,能够获得多个新增的多边形(图中为 3 个): 那么一个凸多边形,裁剪一次,能够获得多个...

    前言

    今天上课老师又布置证明作业。。。来记录一下。

    题目是这样子的:有一凸多边形,经过一次裁剪,要证明它最多能够获得一个新增的凸多边形。

    如图:裁剪一个非凸多边形一次,能够获得多个新增的多边形(图中为 3 个):
    在这里插入图片描述

    那么一个凸多边形,裁剪一次,能够获得多个多边形吗?答案是否定的,请看证明。

    引理

    为了证明它,我们引入两个引理:

    1. 在欧氏空间中凸集的定义如下:凸集 {𝑠} 中的两点连线组成的线段都在 {𝑠} 中。
    2. 凸多边形的定义为 “内部为凸集的简单多边形”,所以凸多边形内任意两点的连线 都应该在凸多边形内(或者边上)。

    总之:凸多边形内两点连线必定在凸多边形内部!

    证明

    根据我们的引理【凸多边形内两点连线必定在凸多边形内部】,我们利用反证法来进行证明。

    1. 假设有一凸多边形 𝑠,其内的点组成集合 {𝑠} 。
    2. 经过一次裁剪,得到了两个新增的凸多边形 𝑎 和 𝑏
    3. 我们连接 𝑎 和 𝑏 内的两点,必定存在一条不在 {𝑎,𝑏} 内的直线。

    在这里插入图片描述

    如图:必定存在直线不在集合 {a,b} 内

    1. 又因为 {a,b} 是 {s} 的子集
    2. 这意味着 {s} 中存在两点,他们之间的连线不属于 {s} ,这和凸多边形的定义相悖。
    3. 故知晓 s 不是凸多边形,反证法得证。
    展开全文
  • 题目链接: ...(凸多边形的定义)注:顶点个数至少为 3 个且不超过 10,000。坐标范围为 -10,000 到 10,000。你可以假定给定的点形成的多边形均为简单多边形(简单多边形的定义)。换句话说,保每...
  • 计算任意两个凸多边形 的IOU值。(根据两个凸多边形的顶点坐标计算)分别计算每一个凸多边形的面积。利用向量叉乘求面积。计算两个凸多边形的相交面积。两个凸多边形相交区域构成的多边形L,先求出L的各个顶点,然后...
  • 凸多边形直径】POJ - 2187 - Beauty Contest 题目链接http://poj.org/problem?id=2187 #include<iostream> #include<stdio.h> #include<algorithm> #include<math...
  • 这里的凸的意思是外接凸多边形,非凸指的是按照最外面的点相互连接得到的多边形。如这里白色区域为非凸,外面绿色连线围成的区域为凸。 以下代码生成的为非凸。 points = [(319, 320), (125, 198), (250, 366), ...
  • 2D凸多边形碰撞检测算法(二) - EPA原理有了 GJK 算法的基础,我们很容易就能掌握 EPA 。EPA ,全称 Expanding Polytope Algorithm 。它与 GJK 同样使用闵可夫斯基和,单纯形这两个基础概念与 support 函数,来获得...
  • 如果是凸多边形, 再判断,圆是否在凸多边形内部。 分析: 1) 先判断是否为凸多边形 ,题目给出的顶点是有序的, 即顺时针或是 逆时针。用叉积方向判断。 2) 判断圆在多边形内, 首先判断 圆心是否在多边形...
  • 单调多边形: 单调多边形必须将其与某一条直线对应,即...凸多边形: 任意一条直线L都关于此多边形单调,则称此多边形为凸多边形凸多边形一定可以找到一条直线L(因为任意直线都满足条件),使得其关于直线L单调。 ...
  • 凸多边形凸多边形的交集:c++ 多边形求交集代码(凸多边形凸多边形交集) #include "stdafx.h" #include <iostream> #include <stdlib.h> #include <opencv2\opencv.hpp> using namespace ...
  • 凸多边形重心:https://wenku.baidu.com/view/6c113283ec3a87c24028c426.html (有错) 一句话概括:固定一点 枚举另两点(连续的)构成三角形 求出这个三角形重心 求平均(加权面积) 代码: Point ...
  • 分析:因为是凸多边形,所以只要对每条边求一下叉积即可.设有向量P和Q则它们的叉积PXQ有以下性质:1.PXQ>0 时,则P在Q的顺时针方向;2.PXQ<0 时,则P在Q的逆时针方向;3.PXQ=0 时,则P和Q共线,...
  • 多边形判定是凸多边形还是凹多边形 double left_right(CPoint a, CPoint b, CPoint c) { a.x -= c.x; a.y -= c.y; b.x -= c.x; b.y -= c.y; return a.x*b.y - a.y*b.x; } //返回true为凸多边形,false为凹...
  • 凸多边形最优三角形

    2021-03-24 20:55:45
    (1)凸多边形的三角剖分:将凸多边形分割成互不相交的三角形的弦的集合T。 (2)最优剖分:给定凸多边形P,以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分,使得该三角剖分中诸...
  • 凸多边形、凹多边形、凸包算法

    千次阅读 2020-06-29 22:23:39
    凸多边形: (Convex Polygon)可以有以下三种定义: 1、没有任何一个内角是优角(Reflexive Angle)的多边形。 2、如果把一个多边形的所有边中,有一条边向两方无限延长成为一直线时,其他 3、凸多边形是一个内部为...
  • 469 凸多边形

    2020-10-06 09:11:52
    给定一个按顺序连接的多边形的顶点,判断该多边形是否为凸多边形。(凸多边形的定义) 注: 顶点个数至少为 3 个且不超过 10,000。 坐标范围为 -10,000 到 10,000。 你可以假定给定的点形成的多边形均为简单多边形...
  • 顶角判别法识别多边形的凸凹性,并将凹多边形近似处理为凸多边形
  • 问题描述 当一个简单的多边形及其内部构成一个闭凸集时,则称该简单多边形为一个凸多边形。...凸多边形最优三角剖分问题:给定凸多边形P={V0,V1,V2…Vn-1},以及定义在由凸多边形的边和弦组成的三...
  • 凸多边形顶点排序

    热门讨论 2012-08-14 23:18:05
    知道了凸多边形的顶点,将其排序使得这些点按顺序连接之后能形成一个凸多边形

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,560
精华内容 1,424
关键字:

凸多边形