首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

在多边形内找到轴对齐的矩形

在多边形内找到轴对齐的矩形是一个计算几何问题。为了解决这个问题,我们可以使用以下步骤:

  1. 首先,找到多边形的最小包围矩形,即与多边形顶点重合的矩形。
  2. 然后,在最小包围矩形内找到轴对齐的矩形。

以下是一个简单的算法:

  1. 计算多边形的最小包围矩形。
  2. 对于包围矩形的每条边,计算其与多边形的交点。
  3. 对于每个交点,计算其与包围矩形的交点。
  4. 根据交点的位置,确定轴对齐矩形的边长。

在这个算法中,我们需要使用一些几何计算工具,例如点到线的距离计算、线段相交计算等。这些计算可以使用一些常见的几何库来实现,例如OpenCV、Shapely等。

以下是一个使用Python和Shapely库实现的示例代码:

代码语言:python
复制
import shapely.geometry as sg

# 定义多边形的顶点
polygon_vertices = [(0, 0), (0, 10), (5, 15), (10, 10), (10, 0)]

# 创建多边形和包围矩形
polygon = sg.Polygon(polygon_vertices)
min_rect = polygon.minimum_rotated_rectangle

# 计算包围矩形的边和角度
min_rect_vertices = list(min_rect.exterior.coords)
min_rect_edges = [(min_rect_vertices[i], min_rect_vertices[(i+1)%len(min_rect_vertices)]) for i in range(len(min_rect_vertices))]
min_rect_angle = min_rect.angle

# 计算包围矩形的交点
intersection_points = []
for edge in min_rect_edges:
    for polygon_edge in polygon_edges:
        intersection = sg.intersection(sg.LineString(edge), sg.LineString(polygon_edge))
        if not intersection.is_empty:
            intersection_points.append(intersection.xy[0][0], intersection.xy[1][0])

# 计算轴对齐矩形的边长
# ...

需要注意的是,这个算法只是一个简单的示例,实际应用中可能需要更复杂的算法来处理更复杂的多边形和交点计算。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

2022-10-09:我们给出了一个(对齐)二维矩形列表 rectangles 。 对于 rectangle = ,其

2022-10-09:我们给出了一个(对齐)二维矩形列表 rectangles 。...对于 rectanglei = x1, y1, x2, y2,其中(x1,y1)是矩形 i 左下角坐标(xi1, yi1) 是该矩形 左下角 坐标, (xi2, yi2) 是该矩形 右上角 坐标。...计算平面中所有 rectangles 所覆盖 总面积 。任何被两个或多个矩形覆盖区域应只计算 一次 。返回 总面积 。因为答案可能太大,返回 10^9 + 7 模 。...一个矩形两个事件。这道题用了树结构,对于rust有点复杂,用了Rc>数据类型。力扣850上测试,rust语言占用内存最低,go语言占用内存略高于rust,但运行速度最快。...// x2 y2 右上角点坐标 // 解释一下y1为啥要+1 // 比如y1 = 3, y2 = 7 // 实际处理时候

25310

关于包围盒,你需要知道那些事

实际上包围形状图形某些情况下会使用多边形(凸包、凹包)或是圆形或是其他,不仅限于矩形更泛用叫法应该是 “包围体”(bounding volume)。...AABB 包围盒全称为 axis-aligned bounding box,对齐包围盒。 它是一个矩形,且它边是和轴线(比如 x 和 y 对齐。...该包围盒也是矩形,但是因为有旋转,边不一定和轴线对齐,但能 更紧凑地包围目标图形。 包围盒需要补充一个旋转属性。...分离定理专门用来进行凸多边形之间碰撞检测,矩形也是凸多边形,所以可以用。...此时我们需要是上图这种包围多边形,勉强叫做有 transform box 吧。 因为是线性形变,包围多边形是平行四边形,依旧是凸多边形,所以还是可以分离定理 算法来计算碰撞。

17010

ODTK:来自NVIDIA旋转框物体检测工具箱

现实世界中,有些目标不能被描述为一个简单矩形,需要更多参数。添加角度参数有助于描述其位置和轮廓,比对齐框更精确。 ? 图3,ODTK检测旋转框例子。...,分类和对齐包围框之外还有一个额外分割头。...图4,对齐锚框(蓝色),旋转锚框(红色和蓝色),旋转角度:-π/6, 0和π/6 旋转框IOU计算 ? 图5,两个旋转矩形重叠区域为多边形。...你必须把函数封装起来以确保w和h是正,并且theta-pi/2到pi/2或者-pi到pi范围。...图8,对齐模型(左)和旋转框模型(右)推断框(红色)和gt框(绿色) 图8显示了ISPRS波茨坦数据集上训练对齐和旋转框模型例子,这些例子是从使用ResNet18主干COCO数据集上预训练对齐模型上进行微调

2.8K30

判断点是否多边形Python实现及小应用(射线法)

判断一个点是否多边形是处理空间数据时经常面对需求,例如GIS软件中点选功能、根据多边形边界筛选出位于多边形点、求交集、筛选不在多边形点等等。...判断一个点是否多边形内有几种不同思路,相应方法有: 射线法:从判断点向某个统一方向作射线,依交点个数奇偶判断; 转角法:按照多边形顶点逆时针顺序,根据顶点和判断点连线方向正负(设定角度逆时针为正...射线法原理及实现 射线法就是以判断点开始,向右(或向左)水平方向作一射线,计算该射线与多边形每条边交点个数,如果交点个数为奇数,则点位于多边形,偶数则在多边形外。...,y1]],[[w1,t1],……[wk,tk]]] 三维数组 #可以先判断点是否在外包矩形 #if not isPoiWithinBox(poi,mbr=[[0,0],[180,90...= [float(line[pindex[0]]), float(line[pindex][1])] if isPoiWithinPoly(point, polygon): #多边形

9.4K40

图形编辑器开发:基于相交策略选中图形

分离(Separating Axis Theorem,简称SAT),它思想是: 如果能找到一条直线将两个图形分开,那说明这两个图形不相交。 如图: 具体做法是做投影。...(通过降维,将大问题拆分成小问题) 我们会对两个凸多边形做投影,投影到线称为 “分离”。 分离基本选择是两个图形每条边对应法向量。...当发现投影产生两条线段没有相交,那找到了那条那条分割两图形直线,证明两个凸多边形不相交。 否则继续,如果都没找到,说明相交。 下图是以一个图形蓝边法向量作为分离,进行投影示意图。...我们判断选区矩形和图形 AABB 包围盒是否相交时,其实就已经完成了 基于选区矩形对应所有分离 投影上是否相交比较。 接下来我们只要再对图形边对应分离轴线投影,去对比就好了。...---- 相关阅读, 几何算法:判断两条线段是否相交 图形编辑器开发:颜色 hex 标准化 图形编辑器开发:一些会用到简单几何算法 几何算法:矩形碰撞和包含检测算法 容器显示图片五种方案

15730

计算几何算法概览

判断线段、折线、多边形是否矩形中 判断矩形是否矩形中 判断圆是否矩形中 判断点是否多边形中 判断线段是否多边形 判断折线是否多边形 判断多边形是否多边形 判断矩形是否多边形...判断圆是否多边形 判断点是否 判断线段、折线、矩形多边形是否 判断圆是否 计算点到线段最近点 计算点到折线、矩形多边形最近点 计算点到圆最近距离及交点坐标...判断线段是否多边形:   线段多边形一个必要条件是线段两个端点都在多边形,但由于多边形可能为凹,所以这不能成为判断充分条件。...判断矩形是否多边形:   将矩形转化为多边形,然后再判断是否多边形。   判断圆是否多边形:   只要计算圆心到多边形每条边最短距离,如果该距离大于等于圆半径则该圆多边形。...判断线段、折线、矩形多边形是否:   因为圆是凸集,所以只要判断是否每个顶点都在圆即可。   判断圆是否:   设两圆为O1,O2,半径分别为r1, r2,要判断O2是否O1

1.5K40

OpenCV - 绘图

我们常常会想要画一幅图片,或者某个其他地方得来图片上画些东西。为了实现这个目标,OpenCV提供了一大批可以供我们画直线、矩形、圆等图形函数。本文记录相关内容。...内容列表 序号 函数 描述 1 cv2.circle() 画一个简单圆 2 cv2.clipLine() 判断一条直线是否在给定矩形 3 cv2.ellipse() 画一个椭圆(可以倾斜,或者只有部分圆弧...canvas, center, radius, color, thickness, lineType, shift) PIS(canvas) 2. cv2.clipLine() 判断一条直线是否在给定矩形...函数使用 cv2.clipLine(imgRect, pt1, pt2) 点都是 (x, y) 格式,rect 为 (x, y, w, h) 格式 只有当直线完全指定矩形范围之外时,函数...这个函数比 cv2.fi11Po1y() 速度快很多,因为它使用了更简单算法。需要注意是cv2.fillConvexPoly() 使用算法多边形有自交点时不能正确工作。

1.4K20

机器视觉算法(第11期)----OpenCV中绘图与注释

绘图 我们常常会想要画一幅图像或者某些图片上画一些东西,为了实现这个目标,OpenCV提供了一大批可以供我们画直线,矩形,圆等图形函数。...一般情况下,绘图函数可以在任意深度图像上工作,但是通常情况下只对前前三个通道有作用,大多数绘图函数都支持操作对象颜色,宽度,线型和亚像素对齐等参数。...8 int shift = 0 // Bits of radius to treat as fraction ); 1.2. cv::clipLine() 该函数用来判断点pt1和点pt2连接直线是否一个矩形范围...下面第一种函数形式,是使用了一个Rect,只有当直线完全指定矩形范围外时候,该函数才会返回false;第二种形式是用了一个Size,该Size表示矩形范围是从(0,0)开始,如下: bool...,可以处理包括有自交点多边形在内普通多边形

1.2K20

AutoCAD工程制图 常见命令与注意事项全总结(120例)

12.捕捉对象里有垂足捕捉点。 13.修剪时先剪前面的再剪后面的。 14.矩形画法:矩形+@长度,宽度。先指定一点再公式套入。 15.旋转选定目标后要回车一次,角度可以输入正负,正为顺时针。...33.椭圆命令:EL 34.中心点画椭圆(点击面板上椭圆按钮,只需输入长,短一半,要先指定中心点位置) 35.顶点画椭圆(输入el,确定顶点(也可以在下方面板点击中心点绘制),再输入长长,短一半...39.多边形命令:POL 40.看标注:点到点(多边形),边到边(外切多边形)。 41.利用命令绘制多边形时,无需指定中心点(必须顺时针点端点)。...59.特性快捷(ctrl+1)也可以加载线性下面找到。 60.比例1以上是放大,比例1以下是缩小。...4 93.制作半球:坡切或者利用大正方体su。先从球心画一条线定位。 94.绘制长方形时,@后数据分别是与X,Y对应。 95.拉伸面可以对实体面进行拉伸操作。

1.2K10

你被追尾了

例如我们想实现一个小球如下盒子移动,移动过程中如果碰到边界就反弹(假定弹性碰撞,无机械能损失). ? 那么我们只需要在小球外接一个正方形,然后判定该正方形和边框是否发生碰撞就行了....= polygon1.getAxes(); axes.push(polygon2.getAxes()); // 遍历所有投影,获取多边形每条投影投影 for(each...这就是上述 getAxes 函数 投影(project) 通过将一个多边形每个顶点与原点(0,0)组成向量,投影某一投影上,然后维护该多边形该投影上所有投影中最大值和最小值,这样即可表示一个多边形某投影投影了...如上图所示,T投影投影为黄色 [Tmin = 0, Tmax], 而 P 投影投影为 蓝色 [Pmin, Pmax]. 至于投影使用向量点积就可以搞定了....我们只需将圆形投射到一条投影上即可,这条就是圆心与多边形顶点中最近一点连线,如图所示: ? 因此,该投影多边形自身投影就组成了全部待检测投影了。

4.6K30

CAD常用基本操作

,所绘矩形只能在第一象限 D 旋转(R):绘制与x正方向呈一定夹角矩形 E 选择矩形命令后其它命令操作:a 倒角(C)与圆角(F):直接绘制倒角或圆角矩形b 标高(E):指定所绘矩形和基准面的垂直距离...1024以上默认为圆 B 边(E):通过指定一条边长度绘制正多边形 C 多边形绘制中默认边与x平行,要进行改变使多边形尖角向上,输入圆半径时应为有缘学习更多+谓ygd3076考证资料或关注桃报:奉献教育...输入大于 0 公差将使有缘学习更多+谓ygd3076考证资料或关注桃报:奉献教育(店铺) 样条曲线指定公差范围通过拟合点(更改所有控制点公差)。...35 标注(直接从菜单栏选择更为简单) A 选择线性和对齐标注后单击右键可直接选择对象进行标注 B 坐标标注:水平为y坐标,垂直为x坐标 C 折弯标注用于标注半径较大圆或者圆弧 D 角度标注点击右键可以通过指定顶点和边来标定角度...38 对齐命令 align(AL) A 指定一对、两对或三对源点和定义点,以对齐选定对象,两点或三点对齐对象会发生相应旋转 B 二点对齐可以设置是否缩放,不缩放时,系统默认第一对源点与定义点重合,而第二源点仅与定义点旋转共线

5.4K50

腾讯地图JavaScript API GL实现文本标记碰撞避让

比较常见一种方式是通过分离定律(SAT:Separating Axis Theorem)来计算,分离定义:两个凸多边形物体,如果能找到一个,使得两个物体投影互不重叠,那么这两个物体就没有发生碰撞...一般不会遍历所有角度,而是检测垂直于多边形每条边,因为在这些上我们可以取到极值。...,首先明确下半径投影概念,可以理解为矩形中心点到一个顶点向量,投影长度。...其实就是,矩形X上最远处交点,数学上意义就是2条检测投影之和。 [1] 两个矩形检测过程中,以其中一个矩形检测为坐标系,投影另外一个矩形检测。...矩形应该是最简单一种,其他凸多边形检测会复杂一些,有兴趣的话可以自己尝试一下。

1.5K40

C++ OpenCV透视变换综合练习

# 实现思路 1 图像灰度图,高斯滤波、二值化 2 形态学开操作,Canny边缘检测 3 查找轮廓,遍历轮廓判断周长大于图像宽度进行多边形拟合 4 判断拟合点大于4个获取到最小旋转矩形 5 通过多边形拟合点计算出离最小旋转矩形最近...4个点 6 找到轮廓最小外接矩形作为透视变换坐标 7 将5、6步骤两个坐标点计算透视变换矩阵 8 透视变换 重点说明 ?...,Y最大为P[0],p[0]围着center顺时针旋转, //旋转角度为负的话即是P[0]左下角,为正P[0]是右下角 //重新排序坐标点 if (rect.angle > 0) {...通过多边形拟合出来点比较多,而使用透视变换也是只要4个点,如果使用最小旋转矩形4个点没有什么效果,如上图中红色是多边形拟合点,蓝色框为最小旋转矩形点,如果用这个点无法实现透视变换效果,所以通过遍历了多边形拟合点...距离计算用是欧几里德距离,然后对比找到最近4个点。

1K20

MFC绘图小实验(2)

(-rect.Width()/2,-rect.Height()/2); //客户区矩形校正 CPen penBlue(PS_SOLID,5,RGB(0,0,255)); //定义5个像素宽蓝色画笔...注意:该例程中用到了三角函数,要包含数学头文件;用到了圆周率π值,需要把它宏定义为PI;由于五边形顶点数组计算值为浮点型数据,存储为CPoint类型时需要进行舍入处理。...P0(-160,20)、P1(-240,100)、P2(-280,0)、P3(-240,-100)、P4(-180,-40)、P5(-140,-100)、P6(-60,40)左侧多边形,水平右移360个像素绘制同样形状多边形...,使用FillPath()函数填充左侧多边形,使用StrokeAndFillPath()函数填充右侧多边形。...Resource View 画板里选中Test resources,右击,弹出菜单里选择引入..., 注意:图片后缀名必须是.bmp ? 效果如下: ?

1.5K30

CTPN、TextBoxes、SegLink、RRPN、FTSN、DMPNet…你都掌握了吗?一文总结OCR必备经典模型(一)

一般来说,获取到文字之前需要首先对文字进行定位,即执行文本检测任务,将图像中文字区域位置检测出来;找到文本所在区域之后,对该区域中文字进行文字识别。...图5 基于旋转文本检测管道 R-Anchor 传统RPNanchor均是与坐标平行矩形,而RRPN中添加了角度信息,将这样锚点叫做R-Anchor。...接着通过仿射变换将子区域转换成平行于坐标矩形,最后通过Max Pooling得到长度固定特征向量。...多边形滑窗 作者提出了倾斜四边形作为anchor box,如图8所示:正方形窗口内增加两个45度矩形窗;矩形增加两个长平行四边形窗口;矩形增加两个高平行四边形窗口。...1)对于GT( ground truth ),首先在它外接矩形框里面均匀采样10000点,然后统计GT多边形里面的点,得到GT面积;2)如果Sliding window外接矩形和GT外界矩形不相交

37730

point inside 点在框内

判断一个点是否一个图形,而且考虑到计算效率,找到人家说几种方法 射线:从判断点向某个统一方向作射线,依交点个数奇偶判断; 转角:按照多边形顶点逆时针顺序,根据顶点和判断点连线方向正负(设定角度逆时针为正...面积和:求判断点与多边形边组成三角形面积和,等于多边形面积则点在多边形内部。...如果是矩形比较简单,直接判断四个点范围,不能推广到多边,考虑到图形凹凸就更复杂,考虑到程序需要直接拿来用罢了, cv2.pointPolygonTest function finds the shortest...两种编程思路来计算这个面积:  方法一:将整个坐标看成一个边长为12正方形,然后均匀这个正方形分成N(N大小取决于划分步长)个点,然后找出N个点中有多少个点是属于阴影部分中,假设这个值为k,则阴影部分面积为...:k/N12^2  方法二:将整个坐标看成一个边长为12正方形,然后(-6,6)中随机出N(N越大越好,至少超过1000)个点,然后找出这N个点中有多少个点在阴 影区域,假设这个值为k,则阴影部分面积为

1.2K30

WPF UNO 测试固定尺寸且水平和垂直对齐设置 Stretch 元素容器布局行为

本文将告诉大家我对 WPF 自定义布局容器和自定义控件进行布局行为测试中一个小点,即测试固定元素尺寸情况下或元素尺寸为有限尺寸情况下,同步设置元素水平和垂直对齐为 Stretch 来测试元素容器布局行为...,从而测试自定义容器给里层元素不同布局空间时,设置了水平和垂直对齐为 Stretch 元素会如何布局 给以上这个自定义容器插入一个元素,设置元素给定尺寸且设置了水平和垂直对齐,如下面代码...,我还给以上 Grid 添加一圈带背景 Border 控件,用来测试布局尺寸空间超过元素所需尺寸时行为,和测试布局尺寸空间小于元素所需尺寸时压缩元素裁剪行为 对 WPF 和跑 WPF 框架之上...当上层容器给定元素可布局尺寸小于元素所需尺寸时,元素行为将和左上对齐时相同 本文以上代码放在github 和 gitee 欢迎访问 可以通过如下方式获取本文源代码,先创建一个空文件夹,接着使用命令行...cd 命令进入此空文件夹,命令行里面输入以下代码,即可获取到本文代码 git init git remote add origin https://gitee.com/lindexi/lindexi_gd.git

15210

凸包多边形最小外切矩形算法

这是很早之前一个项目了, 要计算一个凸包多边形最小外切矩形 . 遇到这种情况肯定是束手无策.. 翻了一些资料之后. 终于完成了....任何一张图片他最终形状是矩形, 那么我们就可以通过 计算不规则多边形最小外切矩形, 然后通过角度摆正 90° , 就能拿到想要图形. 凸多边形最小包围矩形至少有一条边与多边形一条边共线。...obb.c + ( obb.u[1] * obb.e[1] - obb.u[0] * obb.e[0] ); return pts; } 旋转卡尺(旋转卡壳)算法 使用旋转卡尺算法可将计算凸多边形最小包围矩形时间消耗减少很多...取坐标上两极值点构成平行线,旋转两线,当线与多边形一条边重合时,计算构成矩形面积。 继续旋转,直至旋转角度超过 90 度。取最小面积。...x投影最大最小,y投影最大长度(y最小则是重合边上点,长度为0) //以及极值点在pts中下标 Point d = pts[i] - pts[iu]; float dist0

71730

SVG - 基本SVG属性

line - 直线 拥有四中基本属性 x1 属性 x 定义线条开始 y1 属性 y 定义线条开始 x2 属性 x 定义线条结束 y2 属性 y 定义线条结束 demo polyline - 折线 points 属性定义多边形每个点...rect 元素 width 和 height 属性可定义矩形高度和宽度 x 属性定义矩形左侧位置(例如,x="0" 定义矩形到浏览器窗口左侧距离是 0px) y 属性定义矩形顶端位置(例如,...y="0" 定义矩形到浏览器窗口顶端距离是 0px) CSS fill-opacity 属性定义填充颜色透明度(合法范围是:0 - 1) CSS stroke-opacity 属性定义笔触颜色透明度...属性定义多边形每个角 x 和 y 坐标 demo <polygon points = "60,0 120,0 180,60 180,120 120,180 60,180 0,120 0,60" fill

3.9K170
领券