标签: computational-geometry

我正在尝试围绕 3d 曲线的每个点渲染圆圈。基本上试图为曲线创建一个管状结构。但如图所示，圆圈的方向是错误的。下面是我在计算 frenet 框架后对圆形对象的模型矩阵的计算。我哪里错了？作为参考，绿线是切线，蓝色是法线，红色是副法线。

Frenet Frame Calculations：

glm::vec3 pointback = curve_points[i-1];
glm::vec3 pointmid = curve_points[i];
glm::vec3 pointforward = curve_points[i+1];

glm::vec3 forward_tangent_vector =  glm::vec3(glm::normalize(pointforward - pointmid)) ;
glm::vec3 backward_tangent_vector = glm::vec3(glm::normalize(pointmid - pointback)) ;

glm::vec3 second_order_tangent = glm::normalize(forward_tangent_vector - backward_tangent_vector);

glm::vec3 binormal = glm::normalize(glm::cross(forward_tangent_vector, second_order_tangent));

glm::vec3 normal = glm::normalize(glm::cross(binormal, forward_tangent_vector));

Model Matrix for Circle calculations

glm::mat3 tbn = glm::mat3(forward_tangent_vector,binormal,normal);

glm::vec3 normal_axis = glm::vec3(0, 1, 0);
//normal_axis = forward_tangent_vector;

glm::vec3 circleNormal = glm::normalize(tbn * normal_axis);
glm::vec3 rotationAxis = glm::cross(normal_axis, circleNormal); …

给定一组点，

points = np.random.randn(...) # n 3d points

我想均匀地填充由凸包定义的体积，其中它们位于nx33d 点列表（ np.array of shape ）中。

我可以得到凸包

hull = scipy.spatial.ConvexHull(points)

获得均匀填充该船体体积的点列表的最快方法是什么？

我正在尝试实现几何模板引擎.其中一个部分是采用原型多边形网格,并将实例化与较大对象中的某些点对齐.

因此,问题在于:给定多边形网格中某些(可能是全部)顶点的三维点位置,找到一个缩放旋转,最小化变换顶点和给定点位置之间的差异.如果有帮助的话,我还有一个可以保持固定的中心点.顶点和3d位置之间的对应关系是固定的.

我认为这可以通过求解变换矩阵的系数来完成,但我有点不确定如何构建系统来解决.

一个例子是立方体.原型将是以原点为中心的单位立方体,具有vert索引:

4----5
|\    \
| 6----7
| |    |
0 |  1 |
 \|    |
  2----3

要适合的vert位置的示例:

• v0:1.243,2.163,-3.426
• v1:4.190,-0.408,-0.485
• v2:-1.974,-1.525,-3.426
• v3:0.974,-4.096,-0.485
• v5:1.974,1.525,3.426
• v7:-1.243,-2.163,3.426

因此,考虑到原型和那些点,我如何找到单个比例因子,以及关于x,y和z的旋转,它们将最小化顶点和那些位置之间的距离？最好将该方法推广到任意网格,而不仅仅是一个立方体.

我正在寻找一个算法如下:

给定一组可能重叠的矩形(所有这些都是"未旋转",可以统一表示为(左,上,右,下)连音符等...),它返回一组最小(非旋转)非重叠的矩形,占据相同的区域.

乍一看似乎很简单,但是很容易变得棘手(至少要有效地完成).

这个/ ideas /指针有一些已知的方法吗？

不一定是最小但是启发式小的集合的方法也很有趣,所以产生任何有效输出集的方法也是如此.

我想解析以蓝色显示的以下多边形,从多边形中删除导致凹陷的所有点.

目前,我一直试图做的是:

• 从多边形中取出每个点
• 测试该点以查看它是否属于由该组的其余部分创建的多边形
• 如果为true则删除该点
• 如果错误保持重点

这在大多数情况下都有效,但在前一种情况下,(2,3)和(2,4)处的点都不会被删除.在这两种情况下,其中一个点将被删除,但另一个点将不依赖于传入数组的顺序.

我想知道的是:

1. 有没有办法测试,看看我正在处理的多边形是否恰好有这些情况之一(IE:连续3个故障点？)
   或
2. 有没有更简单的方法来创建凸多边形？

谢谢.

我想创建三角形预定义的多边形.我的要求是我不想在这个多边形内部创建随机点,以便使用Delaunay三角剖分算法对其进行处理.
多边形可以是凹的或凸的.

我完全可以使用Delaunay三角测量,但我不想在多边形内部创建随机点.如果我可以在此多边形内创建尽可能少的点,那将会更好.
我想尽量减少使用三角形的数量.

我怎样才能建立这个？

评论:这更像是一种与语言无关的东西,我想知道如何自己实现这一点.

我一直在向google查询有关kd-trees和图像比较的一些材料,但我无法在使用kd-trees进行图像比较的技术之间建立"链接".首先,我发现一些文章谈论随机kd树的速度提升,然后我被介绍给SIFT.在基本了解了SIFT如何工作之后,我读到了最近邻搜索.

我真正的问题是:如果我有来自SIFT的点网格,那么我为每个图像创建kd树.最近邻搜索如何帮助我比较图像？起初,我认为将图像与树进行比较可以使用一些算法来检查树结构以及每个点距离图像A的距离是来自同一节点和图像B中的点.

如果问题太愚蠢,请提供材料或搜索​​主题.

谢谢!

给定圆的中心点和半径,我如何知道某个点(x,y)是否在圆中？谁知道呢？谢谢.

假设我们有两个不相交的凹二维多边形(A,B).问题是找到一组边对(每对由多边形A的一条边和多边形B的边组成),它们具有以下属性:对中的每个项必须彼此可见.如果没有障碍物(在图片中有三个案例,在这个规则被打破时用红色十字标记),则一个边缘对另一个边缘是可见的.

我知道如何使用光线和边缘顶点在O(n ^ 2)中解决这个问题.但它太慢了.

所有

具有来自CAD（SW）的STEP格式文件，并能够通过Python OCC绑定读取文件：

    importer = aocxchange.step.StepImporter(fname)
    shapes = importer.shapes

    shape = shapes[0]

    # promote up
    if (shape.ShapeType() == OCC.TopAbs.TopAbs_SOLID):
        sol =  OCC.TopoDS.topods.Solid(shape)

我可以显示它，戳它，检查标志等

t = OCC.BRepCheck.BRepCheck_Analyzer(sol)
print(t.IsValid())
print(sol.Checked())
print(sol.Closed())
print(sol.Convex())
print(sol.Free())
print(sol.Infinite())

到目前为止，一切都很好。它确实看起来像是沿着某些复杂路径弯曲的小管。

问题：如何从已有的几何特征中提取几何特征？我真的需要电子管参数及其遵循的路径。用Python和/或C ++编写的任何好的示例都很好