如何在Python语言中快速得到线性规划的可行解？
目标：计算两个凸多面体的交集。 我使用scipy.spatial.HalfspaceIntersection来执行此操作。下图显示了生成的交叉点： 我的问题：确定初始可行点。 您看，scipy.spatial.HalfspaceIntersection的当前Python实现需要将interior_point作为参数传递。 interior_point : ndarray o
..
computational-geometry相关内容
给定初始接触点，如何计算在圆周上包含这些点的圆的半径？
我实现了一个绘制弧线的UIView。我让它与设定的框架一起工作，但我想让它这样当用户开始绘制圆弧时，我可以快速计算出给定初始接触点的圆弧的半径。 假设我收集了5个初始点，我如何计算这条线开始创建的圆弧的半径？ 推荐答案 您可以通过三个非共线的点构建一个圆。计算三个决定因素的值： D = |x1 y1 1| |x2 y2 1| |x3 y3 1|
..
在MATLAB中计算闭合曲线(或多边形)的曲率
考虑以下几点 x = [1.34, 0.92, 0.68, 0.25, -0.06, -0.34, -0.49, -0.72, -0.79, -0.94, -1.35, -0.35, 0.54, 0.68, 0.84, 1.20, 1.23, 1.32, 1.34]; y = [0.30, 0.43, 0.90, 1.40, 1.13, 1.08, 1.14, 1.23, 0.52, 0.2
..
由散乱的三维点集计算凹多面体的体积
我有20到30个随机生成的3D点作为定义多面体的顶点。我尝试过使用DelaunayTri(points)来枚举面，并使用叉积的行列式来计算和求和四面体的体积，但我不确定它是否适用于非凸多面体。 另一种可能的方法是将凹多面体划分为凸多面体(通过检测凸壳内部的点)，但我无法找到这种不相交划分的算法。 还有，怎么会画出这样一个凹陷的船体呢？ 推荐答案 感谢Mike Garrity
..
给定周长内封闭的最大点数
给定一些点的坐标数组和固定周长的绳索，我如何计算这条绳索可以包含的最大点数？(我指的是除蛮力以外的算法) 例如：给定[[0,1],[0,0],[1,1],[1,0],[100,100]]和长度为4的绳索，则此绳索可以包含前4个点。 推荐答案 刚找到此链接：The minimum perimeter convex hull of a subset of a point set
..
在给定点集中选择最远点的子集
想象一下，给你3维空间中n个点组成的集合S。任意两点之间的距离是简单的欧几里德距离。您希望从该集合中选择k个点的子集Q，以使它们彼此最远。换言之，不存在k个点的其他子集Q‘，使得Q中所有成对距离的最小值小于Q’中的最小值。 如果n约为1600万，k约为300，我们如何有效地执行此操作？ 我的猜测是，这可能是NP难的，所以我们只想关注近似。我能想到的一个想法是使用多维缩放来对一条线上的这
..
如何计算R中基于曼哈顿距离的Voronoi镶嵌
我正在尝试使用R中的曼哈顿距离计算2D中的Voronoi镶嵌。 理想情况下这是一个获取一组二维点并输出划分空间的多边形列表的函数。我不确定Voronoi镶嵌的标准表示是什么。 当然，使用欧几里得度量有很多方法可以做到这一点(像deldir和qhull这样的包使这一点变得非常简单)，但我还没有找到一种方法来实现曼哈顿距离。使用sos%sfindFn('voronoi')进行搜索也没有结果。
..
用OpenCascade，如何快速进行2个形状的碰撞检测？
用OpenCascade如何进行两个形状的碰撞检测？可能有几种方法。一种是计算它们的交集，并检查交集结果。另一种方法是计算它们的最小距离。哪条路更快？或者有没有更快的方法？非常感谢。 推荐答案 在BREP数据结构上计算最小距离是一项相当昂贵的操作。OCC确实提供了碰撞检测的商业选项[1]。其他选项可能是使用ODE或Bullight在表示BRep的网格上执行碰撞检测。这是我们在Pytho
..
三个球体与SymPy相交(三边测量)
有没有办法用SymPy求三个球体相交(三边测量)的解？sympy.geometry没有球体对象，所以直接的方法是不可行的。如Trilateration and the Intersection of Three Spheres所示，SymPy能否求解非线性方程组？ 推荐答案 是。有不同的方法，但例如： In [21]: x, y, z = symbols('x, y, z', r
..
将圆插入几何数据类型
我即将开始第一次使用几何或地理数据类型，因为我们的开发基线是 2008R2(！)我正在努力寻找如何存储一个圆圈的表示.我们目前有圆心的纬度和经度以及半径，例如:- [Lat] [float] NOT NULL,[长] [浮点] 非空，[半径] [十进制](9, 4) 非空， 有谁知道使用 STGeomFromText 方法存储它的等效方法，即使用哪种众所周知的文本 (WKT) 表示?我查看了圆
..
给定与已知坐标的 N 个点的距离，确定点在 3D 空间中的位置
我正在尝试确定点 p 的 (x,y,z) 坐标.我所拥有的是与已知坐标的 4 个不同点 m1、m2、m3、m4 的距离. 详细说明:我所拥有的是4个点(m1，m2，m3，m4)的坐标，它们不在同一个平面上: m1: (x1,y1,z1),m2: (x2,y2,z2),m3: (x3,y3,z3),m4: (x4,y4,z4) 欧几里得距离形成m1->p, m2->p, m3->p 和m4
..
具有信号强度的 2D 平面中的三边测量
StackOverflow 的第一个问题，请温柔. 在给定一定幅度或“信号强度"的情况下，我试图找到二维笛卡尔平面上三个不同点的中心点的方程(然后是算法).这些信号强度都是相互关联的，但不必将其与圆的“半径"混为一谈. 关于三边测量的维基百科条目:http://en.wikipedia.org/wiki/Trilateration 我也查看了这个帖子，但它与我需要的有点不同使用3
..
如何计算沿线的镜像点?
在二维平面中，我有一个点和一条线.沿着这条线如何得到镜像点? 解决方案 假设直线的方程是ax + by + c = 0.现在想象一条垂直于它的线，可以用 -bx + ay + d = 0 表示(两条垂直线的斜率乘积为-1).现在的问题是找到d.把点的坐标放在第二行，就很容易得到d的值了. 第二部分是，在第二条线上找到一个与第一条线的第一个点等距的点.为此，您可以找到两条线的交点.计算
..
多边形内多边形内多边形
我有许多简单的多边形，它们彼此不相交，但有些多边形可能嵌入到其他多边形中. 例如: +--------------------------------------------+|||+----------------+ +--------+ ||||/||||+--------+ |/|||||||/+----(2)-+ ||||||/||||+----(3)-+ |/|+---+ |||
..
给定不规则多边形的顶点列表，如何创建内部三角形以有效地构建平面 3D 网格?
我正在使用 Unity，但解决方案应该是通用的.我将通过鼠标点击获得用户输入，它定义了一个封闭的不规则多边形的顶点列表.这些顶点将定义平面 3D 网格的外边缘. 要在 Unity 中按程序生成网格，我必须指定所有顶点以及它们如何连接以形成三角形. 所以，对于凸多边形，这很简单，我只需制作顶点为 1、2、3 和 1、3、4 等的三角形，形成孔雀尾巴. 但是对于凹多边形，它就不是那么
..
N 个矩形的交集
我正在寻找解决这个问题的算法: 给定笛卡尔坐标上的 N 个矩形，找出这些矩形的交点是否为空.每个矩形可以位于任何方向(不必使其边缘平行于 Ox 和 Oy) 您对解决这个问题有什么建议吗?:) 我可以考虑测试每个矩形对的交集.但是，它是 O(N*N) 并且非常慢:( 解决方案 观察1:给定一个多边形A和一个矩形B，交点A∩B可以用4个半平面的交点计算出B的每条边对应的半平面.
..
如何确定德劳内三角形是内部三角形还是外部三角形?
我正在编写一个程序，该程序需要实现中轴提取，其中 Delaunay 三角剖分是其中的一个步骤.外部中轴是不需要的，因此打算移除相应的外部三角形.幸运的是，我遇到了 一个页面附上很多图，也暗示了一种确定内外德劳内三角形的方法(《基于折线周长》)，不过只是一个提示，没有详细解释.有人知道算法吗? 编辑:我忘了提到初始点是从封闭多边形的边界采样的，我的目的是确定每个德劳内三角形是否在多边形内.
..
可以与单条直线相交的最大可能矩形数
我发现了这个挑战问题，说明如下: 假设在 XY 平面上有 n 个矩形.编写一个程序，计算在该平面上绘制的单条直线所能穿过的矩形的最大可能数量. 我已经头脑风暴了很长时间，但找不到任何解决方案.也许在某个阶段，我们使用了动态编程步骤，但不知道如何开始. 解决方案 这是一个 O(n^2 log n) 解决方案的草图. 首先，预赛与其他答案共享.当我们有一条线穿过一些矩形时，我
..
扩展凸多边形的填充
我有一个 N 个点的凸多边形 P1.这个多边形可以是任何形状或比例(只要它仍然是凸面的). 我需要使用原始多边形几何体计算另一个多边形 P2，但“扩展"了给定数量的单位.扩展凸多边形的算法可能是什么? 解决方案 要扩展一个凸多边形，请画一条平行于每条边和给定数量单位的线.然后使用新线的交点作为扩展多边形的顶点.最后的 javascript/canvas 遵循这个功能分解:
..
在表面上嵌套最大数量的形状
在工业中，您经常需要计算最有效地使用材料的问题，无论是织物、木材、金属等.所以起点是给定尺寸的 X 数量的形状，由多边形和/或曲线，目标是给定尺寸的另一个多边形. 我假设许多当前的 CAM 套件都实现了这一点，但是没有使用它们或其内部的经验，使用哪种计算算法来找到最有效的空间使用?谁能给我指点讨论这个话题的书或其他参考资料? 解决方案 在 Andrew 在他的回答中指出了我正确的方向
..