geometry相关内容

如何确定德劳内三角形是内部三角形还是外部三角形?

我正在编写一个程序,该程序需要实现中轴提取,其中 Delaunay 三角剖分是其中的一个步骤.外部中轴是不需要的,因此打算移除相应的外部三角形.幸运的是,我遇到了 一个页面附上很多图,也暗示了一种确定内外德劳内三角形的方法(《基于折线周长》),不过只是一个提示,没有详细解释.有人知道算法吗? 编辑:我忘了提到初始点是从封闭多边形的边界采样的,我的目的是确定每个德劳内三角形是否在多边形内. ..

确定弯曲、拉长区域的中线

想象一下,我有一个热狗的二维图像.我可以在热狗的两端之间画一条直线.称之为中线.它的特性之一是它是(2D)热狗的转动惯量最小的轴. 现在,如果我将热狗弯曲成弧形,这条中线也会变形. 给定一张弯曲热狗的照片,我如何确定这个弯曲的中线?该算法应该容忍图像中的适量噪声. 解决方案 如果我理解你的问题,你想要一条穿过你的对象的线,其中每个点都在对象的中间,即如果你从对象上的任何点开始中 ..
发布时间:2022-01-14 15:54:37 其他开发

在 OpenGL 中将纹理映射到球体时出现接缝问题

我正在尝试创建几何图形以在 OpenGL 中表示地球.我有一个或多或少的球体(虽然更接近地球的椭圆大地水准面).我绘制了地球表面的纹理(可能是墨卡托投影或类似的东西).纹理的 UV 坐标对应于几何体的纬度和经度.我有两个我无法解决的问题.我正在使用 OpenSceneGraph,但我认为这是一个通用的 OpenGL/3D 编程问题. 有一个非常明显的纹理接缝.我确定会发生这种情况,因为我不知 ..
发布时间:2022-01-14 15:54:23 C/C++开发

检查经度/纬度坐标是否位于嵌入式设备的复杂多边形内?

我需要用户能够在地图上绘制一个复杂的多边形,然后让应用程序检查给定的经度/纬度是否位于该多边形内. 我只能找到使用不补偿地球曲率的简单 x/y 笛卡尔坐标系的算法. 用户在 PC 上绘制多边形,其中点通过无线电传输到嵌入式设备,然后需要检查给定多边形是否位于其当前位置(从 GPS 获取). 由于这是针对嵌入式设备,我无法使用大型库,而是需要算法自己执行检查或使用非常小的库.但我似 ..
发布时间:2022-01-14 15:54:14 其他开发

是否有一种简单快捷的方法来检查多边形是否自相交?

我有一个 System.Windows.Shapes.Polygon 对象,其布局完全由一系列点决定.我需要确定这个多边形是否是自相交的,即多边形的任何边是否在一个不是顶点的点与任何其他边相交. 有没有简单/快速的方法来计算这个? 解决方案 简单、缓慢、低内存占用:将每个段与所有其他段进行比较并检查交叉点.复杂度O(n2). 稍快,中等内存占用(上面的修改版本):将边缘存储 ..
发布时间:2022-01-14 15:54:06 C#/.NET

可以与单条直线相交的最大可能矩形数

我发现了这个挑战问题,说明如下: 假设在 XY 平面上有 n 个矩形.编写一个程序,计算在该平面上绘制的单条直线所能穿过的矩形的最大可能数量. 我已经头脑风暴了很长时间,但找不到任何解决方案.也许在某个阶段,我们使用了动态编程步骤,但不知道如何开始. 解决方案 这是一个 O(n^2 log n) 解决方案的草图. 首先,预赛与其他答案共享.当我们有一条线穿过一些矩形时,我 ..

为什么给 addArcWithCenter 一个 0 度的 startAngle 使它从 90 度开始?

我正在创建一个 CAShapeLayer 以用作 UIView 层的掩码.我正在使用 UIBezierPath 来绘制形状图层.它工作得很好,除了我在画画时得到了一些奇怪的结果.几何图形未按预期运行.我正在尝试在右上角绘制简单的“饼图": #define degreeToRadians(x) ((x) * M_PI/180.0)...//"layer" 指的是 UIView 的根层CAShape ..
发布时间:2022-01-14 15:53:50 移动开发

python opencv - 斑点检测或圆形检测

我在检测圆形区域时遇到问题.我用opencv的HoughCircles函数试过了.然而,即使图像非常相似,函数的参数也必须不同才能检测到圆圈. 我尝试的另一种方法是遍历每个像素并检查当前像素是否为白色.如果是这种情况,则检查该区域中是否存在 blob 对象(到 blob 中心的距离小于阈值).如果有,将像素附加到 blob,如果没有,则创建一个新 blob.这也不能正常工作. 有谁知道 ..
发布时间:2022-01-14 15:53:43 Python

如何找到一条线上的所有网格方块?

我正在尝试在二维网格上实现视线算法.我知道它在概念上需要如何工作,但我想不出如何将它作为一种算法来实现. 基本的想法很简单.在伪代码中: function LineOfSight(point1, point2): boolean正方形 = GetListOfSquaresOnLine(point1, point2)对于正方形中的每个正方形如果 square.IsOpaque 则返回 fal ..
发布时间:2022-01-14 15:53:25 其他开发

给定 3 点,我如何计算法线向量?

给定三个 3D 点(A、B 和 C),我如何计算法线向量?这三个点定义了一个平面,我想要垂直于这个平面的向量. 我可以获得演示此功能的示例 C# 代码吗? 解决方案 这取决于点的顺序.如果从与法线的方向看,这些点是按逆时针顺序指定的,那么计算起来很简单: Dir = (B - A) x (C - A)标准 = Dir/len(Dir) 其中 x 是叉积. 如果您使用的是 O ..
发布时间:2022-01-14 15:53:16 C#/.NET

找到隧道“中心线"?

我有一些由代表隧道的“折线"(每条线只是一个顶点列表)组成的地图文件,我想尝试找到隧道的“中心线"(大致如下所示,以红色显示). 我过去曾使用 Delaunay triangulation 取得过一些成功,但我想避免使用该方法,因为它(通常)不允许轻松/频繁地修改我的地图数据. 关于我如何能够做到这一点的任何想法? 解决方案 一种适用于本地化数据更改的“算法". 评论家的 ..
发布时间:2022-01-14 15:53:09 其他开发

快速计算圆内的点数

给定平面上的一组 n 个点,我想以某种方式比 O(n^2) 更快地预处理这些点(最好是 O(nlog(n))),然后能够回答以下类型的查询“有多少 n 个点位于具有给定中心和半径的圆内?"比 O(n) 快(最好是 O(log(n)). 你能推荐一些我可以用来解决这个问题的数据结构或算法吗? 我知道这类问题通常可以使用 Voronoi 图来解决,但我不知道如何在这里应用它. 解决方 ..
发布时间:2022-01-14 15:53:00 其他开发

扩展凸多边形的填充

我有一个 N 个点的凸多边形 P1.这个多边形可以是任何形状或比例(只要它仍然是凸面的). 我需要使用原始多边形几何体计算另一个多边形 P2,但“扩展"了给定数量的单位.扩展凸多边形的算法可能是什么? 解决方案 要扩展一个凸多边形,请画一条平行于每条边和给定数量单位的线.然后使用新线的交点作为扩展多边形的顶点.最后的 javascript/canvas 遵循这个功能分解: ..

从点创建 OOBB

如何为给定点创建最小的 OOBB?创建 AABB 或球体非常容易,但创建最小 OOBB 时遇到问题. [编辑] 第一个答案没有给我带来好的结果.我没有大量的点云.我的积分很少.我正在做碰撞几何生成.例如,立方体有 36 个点(6 个边,每个三角形 2 个,每个三角形 3 个点).第一篇文章的算法对立方体给出了不好的结果.多维数据集的示例点:http://nopaste.dk/downl ..
发布时间:2022-01-14 15:52:43 C/C++开发

Python 和 OpenCV.如何检测图像中的所有(填充)圆形/圆形对象?

我正在尝试制作一个程序,它可以打开图像,扫描它以查找圆形/圆形并返回坐标,以便我可以使用 cv.Circle 函数在检测到的圆上绘制圆. 我的问题是:如何使用 cv.HoughCircles() 获取图像中检测到的圆的坐标/半径? 使用 this 页面,我发现了如何检测圆圈(这花了我因为我不懂阈值之类的术语,而且 Python 的 OpenCV 文档真的很差,几乎没有),所以要花很多时 ..
发布时间:2022-01-14 15:52:34 Python

优雅/干净(特殊情况)直线网格遍历算法?

我正在清理我的一个旧项目.它必须做的一件事是 - 给定一个笛卡尔网格系统,以及网格上的两个正方形,找到连接这两个正方形中心的一条线将通过的所有正方形的列表. 这里的特殊情况是所有起点和终点都被限制在正方形/单元格的确切中心. 这里有一些示例——带有成对的示例起点和终点.阴影方块是相应函数调用应返回的方块 删除了无效的 ImageShack 链接 - 示例 起点和终点由它们所 ..
发布时间:2022-01-14 15:52:28 其他开发

在扩展的圆形螺旋中迭代二维数组

给定一个 n 由 n 矩阵 M 在行 i 和列 j,我想以圆形螺旋遍历所有相邻值. 这样做的目的是测试一些函数,f,它依赖于 M,找到距离 (i, j) 的半径,其中 >f 返回 True.所以,f 看起来像这样: def f(x, y):"""用 x 和 y 做一些事情,并返回一个布尔值""" 并且会这样调用: R = numpy.zeros(M.shape, dtype=numpy ..
发布时间:2022-01-14 15:52:21 Python

用一个给定半径的圆覆盖最大点数的算法

假设我们有一个平面,上面有一些点.我们还有一个给定半径的圆. 我需要一种算法来确定圆的位置,使其覆盖最大可能的点数.当然,这样的位置很多,所以算法应该返回其中一个. 精度并不重要,算法可能会犯一些小错误. 这是一个示例图片: 输入: int n (n float x[n] 和 float y[n] –具有点的 X 和 Y 坐标的数组; float r –圆的半径. ..
发布时间:2022-01-14 15:52:15 C/C++开发

两个圆的交点面积

给定两个圆圈: C1 at (x1, y1) 与 radius1 C2 at (x2, y2) 与 radius2 你如何计算他们相交的面积?当然,所有标准数学函数(sin、cos 等)都可用. 解决方案 好的,使用 Wolfram 链接和 Misnomer 的提示查看方程 14,我使用我列出的变量和中心之间的距离推导出了以下 Java 解决方案(可以很容易地从中派生出来): ..
发布时间:2022-01-14 15:52:09 其他开发

在表面上嵌套最大数量的形状

在工业中,您经常需要计算最有效地使用材料的问题,无论是织物、木材、金属等.所以起点是给定尺寸的 X 数量的形状,由多边形和/或曲线,目标是给定尺寸的另一个多边形. 我假设许多当前的 CAM 套件都实现了这一点,但是没有使用它们或其内部的经验,使用哪种计算算法来找到最有效的空间使用?谁能给我指点讨论这个话题的书或其他参考资料? 解决方案 在 Andrew 在他的回答中指出了我正确的方向 ..
发布时间:2022-01-14 15:52:01 其他开发