标签: computational-geometry

我有一个方形网格，其中一些点被标记为网格子部分的中心。我希望能够将网格内的每个位置分配给正确的子部分。例如，如果该区域的子部分以黑点为中心，我希望能够将红点分配给右下角的区域，因为它是最近的黑点。

目前，我通过迭代每个可能的红点，并将其与每个黑点的距离进行比较来做到这一点。然而，网格中黑点的宽度、长度和数量都非常高，所以我想知道是否有更有效的算法。

我的特定数据的格式如下，其中数字只是与给定示例相对应的占位符：

black_dots = [(38, 8), (42, 39), (5, 14), (6, 49)]
grid = [[0 for i in range(0, 50)] for j in range(0, 50)]

作为参考，在示例案例中，我希望能够填充grid整数 1、2、3、4，具体取决于它们是否最接近 black_dots 中的第 1 个、第 2 个、第 3 个或第 4 个条目，最终得到一些结果这将允许我创建类似于下图的东西，其中每个整数对应于一种颜色（保留点以供显示）。

总而言之，有/什么更有效的方法可以做到这一点？

我需要在 0.5 到 1 的对数空间中生成数字。

这段代码实现了：

IN: np.geomspace(.5, 1, num=10) OUT: [0.5, 0.540029869446153, 0.5832645197880583, 0.6299605249474366, 0.6803950000871885, 0.7348672461377994, 0.7937005259840997, 0.8572439828530728, 0.9258747122872905, 1.0]

然而，较小的增量接近 0.5。我希望它们接近 1（因此，向后看，我只是不完全确定正确的术语是什么）。

我已经尝试过了np.geomspace(1, .5, num=10)，但它只是以相反的顺序给了我相同的输出。

我有一个由 1,000 个点组成的多边形。是否可以计算每个点的曲率？该多边形最初仅包含 13 个点：

43748.72 40714.19
43743.99 40716.16
43741.36 40720.19
43740.95 40726.46
43742.67 40729.28
43745.52 40730.97
43748.72 40731.14
43752.86 40729.43
43756.77 40723.24
43757.19 40719.73
43755.27 40716.68
43752.23 40714.76
43748.72 40714.19

然后我使用 smoothr 包中的 smooth 函数进行插值，现在多边形有 1,000 个点，如下所示： 现在我想计算每个点的曲率。但既然这是一个封闭的对象，那么如何实际执行计算呢？

编辑 我终于找到了一个带有突起的电池来测试稳健性。该单元格看起来像：

对应的K值为：

事实上，该图捕获了两个突起，但曲率值能那么高吗？我读了一篇论文，似乎它们的值都在 1 以内： 论文链接：https://www.biorxiv.org/content/10.1101/623793v1.full

假设我们在 2D 空间中有 n 个位于凸位置的点。精确地选择（n，k）个不同的凸k边形（非退化）。是否有任何现有算法可以在 O(n log n) 时间内运行（对于固定 k）来计算包含原点的多边形数量？

我试图在文献中寻找任何此类算法，但只找到了 k=3 的算法。

在我看来,这是一个非常简单的问题,但今天我似乎并没有找到一个合理的答案.我有两个点,即R ^ 3(3D)中属于平面PI的A和B. 我想在PI中找到矢量r,垂直于矢量v = A - B.我知道矢量n,平面PI的法线.在数学上我可以解决vr = 0和vxr = n,但是这个系统在r方面的解决方案涉及一些我认为会带来一些数值不稳定性的划分.你能否为我提出这个问题的数值/计算好的解决方案？

提前致谢,

费德里科

我有一套积分.这组点确定了一个(非凸)多边形,但它没有排序.

由于它没有订购,我不能只是从点到点绘制它的边界.如何以一种我可以遍历此点列表并绘制多边形的方式对其进行排序？

我的第一个想法是使用凸壳,但我的多边形大多数时候是凹的.

我正在与Mathematica连接外部程序.我正在为外部程序创建一个输入文件.它将几何数据从Mathematica生成的图形转换为预定义的格式.这是一个几何示例.

图1

可以在Mathematica中以多种方式描述几何体.一种费力的方法如下.

dat={{1.,-1.,0.},{0.,-1.,0.5},{0.,-1.,-0.5},{1.,-0.3333,0.},{0.,-0.3333,0.5},
{0.,-0.3333,-0.5},{1.,0.3333,0.},{0.,0.3333,0.5},{0.,0.3333,-0.5},{1.,1.,0.},
{0.,1.,0.5},{0.,1.,-0.5},{10.,-1.,0.},{10.,-0.3333,0.},{10.,0.3333,0.},{10.,1.,0.}};

Show[ListPointPlot3D[dat,PlotStyle->{{Red,PointSize[Large]}}],Graphics3D[{Opacity[.8],
Cyan,GraphicsComplex[dat,Polygon[{{1,2,5,4},{1,3,6,4},{2,3,6,5},{4,5,8,7},{4,6,9,7},
{5,6,9,8},{7,8,11,10},{7,9,12,10},{8,9,12,11},{1,2,3},{10,12,11},{1,4,14,13},
{4,7,15,14},{7,10,16,15}}]]}],AspectRatio->GoldenRatio]

这将以GraphicsComplexMMA格式生成所需的3D几何体.

此几何体被描述为我的外部程序的以下输入文件.

# GEOMETRY
# x y z [m]
NODES 16
1. -1. 0.
0. -1. 0.5
0. -1. -0.5
1. -0.3333 0.
0. -0.3333 0.50. -0.3333 -0.5
1. 0.3333 0.
0. 0.3333 0.5
0. 0.3333 -0.5
1. 1. 0.
0. 1. 0.5
0. 1. -0.5
10. -1. 0.
10. -0.3333 0.
10. 0.3333 0.
10. 1. -0.
# type node_id1 node_id2 node_id3 node_id4  elem_id1 elem_id2 …

我正在编写Quick Hull算法,其中包括检查点是否位于三角形内.为此,我创建了以下两个函数,如果该点在内部则返回true,否则返回false.

然而,结果是安静意外的意义上的一些点被正确分类,而一些不是,我无法弄清楚问题.有人可以帮我验证我写的代码是否正确.方法是我使用向量来确定一个点是否与三角形的每个边缘的顶点位于同一侧.代码是:

public boolean ptInside(Point first, Point last, Point mx, Point cur) {
        boolean b1 = pointInside(first, last, mx, cur);
        boolean b2 = pointInside(last, mx, first, cur);
        boolean b3 = pointInside(first, mx, last, cur);
        return b1 && b2 && b3;

    }

    public boolean pointInside(Point first, Point last, Point mx, Point cur) {
        int x1 = last.xCo - first.xCo;
        int y1 = last.yCo - first.yCo;
        int x2 = mx.xCo - first.xCo;
        int y2 = mx.yCo - first.yCo;
        int x3 = …

我很困惑,我想检查一个点是否在一个线段上.我谷歌它,但我基本上收到两个不同的答案.

http://en.wikipedia.org/wiki/Line_segment

和

http://www.softwareandfinance.com/Turbo_C/Check_Point_Lies_line_Segment.html

什么是正确的答案？我希望这个算法(用C语言更好)用于几何应用程序,比如postgis.

我最近一直在做一些图像处理,我正在寻找一种算法来确定完全在非规则形状内的最长线段.换句话说,线段应该是在其端点处难以接触形状的最长线段.

形状可以表示为一组(x,y)坐标或二进制数组.最外层的像素(边缘)已经确定.一个简单的例子是椭圆,解决方案是主轴.更复杂的例子是等边三角形,这将导致两个像素之间的线与两个单独的角紧邻.我的大多数形状都是椭圆形或"蠕虫状"(长而波浪状).

最后,我希望将此作为一种方法,将"蠕虫状"形状划分为它们的片段,使用一系列大致垂直于此线的"切割".我希望这条消息形成的线条比回归确定的线条更适合这项任务.应该注意的是,这些形状是高分辨率的,因此可能包含多达1000个边缘像素,这就是为什么我试图避免简单的迭代/强力方法.

谢谢你的任何建议!

以下是一些可视化: