标签: computational-geometry

List1包含大数(~7 ^ 10)的N维点(N <= 10),List2包含相同或更少数量的N维点(N <= 10).

我的任务是这样的:我想检查List2中哪个点最接近(欧几里德距离)List1中的一个点,对于List1中的每个点,然后对它执行一些操作.我一直在做这个简单的嵌套循环方式,当我在List1中没有超过50个点,但是有7 ^ 10个点,这显然占用了很多时间.

最快的方法是什么？计算几何的任何概念都有帮助吗？

编辑:我有以下内容,我已经从List2中构建了一个kd树,然后我正在对List1中的每个点进行最近邻搜索.正如我最初指出的那样,List1有7 ^ 10个点,因此虽然我节省了每一对的蛮力,欧几里德距离法,但List1中的大量点数导致了大量的时间消耗.有什么方法可以改善这个吗？

给定2D平面中的2个点,这两个点内有多少个格点？

例如,对于A(3,3)和B(-1,-1),输出为5.点为:( - 1,-1),(0,0),(1,1),(2) ,2)和(3,3).

我正在尝试在线平面交叉算法上实现.根据维基百科,我需要飞机上的三个非共线点来做到这一点.

因此,我尝试在C++中实现此算法.有些东西肯定是错的,因为没有任何意义我可以选择任何x和y坐标,它们都适合飞机.如果平面是垂直的并且沿着x轴怎么办？然后y = 1的任何点都不在平面内.

我意识到这个问题已经在StackOverflow上发布了很多,我看到很多解决方案,其中平面由3个点定义.但我只有一个正常和一个位置.在我整理非共线点检测器之前,我无法测试我的线平面交点算法.

现在的问题是,我除了normal.z,而且当normal.z为0时,这显然不起作用.

我正在测试这个平面:Plane*p = new Plane(Color(),Vec3d(0.0,0.0,0.0),Vec3d(0.0,1.0,0.0)); //第二个参数:position,第三个参数:normal

当前代码给出了错误答案:

{0 , 0 , 0} // alright, this is the original
{12.8377 , 17.2728 , -inf} // obviously this is not a non-colinear point on the given plane

这是我的代码:

std::vector<Vec3d>* Plane::getThreeNonColinearPoints() {
    std::vector<Vec3d>* v = new std::vector<Vec3d>();

    v->push_back(Vec3d(position.x, position.y, position.z)); // original position can serve as one of the three non-colinear points.

    srandom(time(NULL));

    double rx, ry, rz, start;

    rx = Plane::fRand(10.0, 20.0);
    ry = …

我正在寻找一种方法来做快速最近邻居(希望是O(log n))的高维点(通常是~11-13维).我希望它在初始化结构后的插入过程中表现得最佳.KD树出现在我的脑海中,但是如果你不进行批量加载但是进行动态插入,则kd树不再平衡,并且afaik平衡是一项昂贵的操作.

所以,我想知道你喜欢哪种数据结构进行这种设置.您有高维度点,并且您想要插入并查询最近邻居.

我正在尝试用C++ 实现Graham Scan,但它不起作用,我找不到原因.任何领导将不胜感激.经过一些尝试后,似乎我总是有m_M = 22点是最高点,如果有帮助的话.

交叉产品,知道它是右转还是左转.

qreal Interpolation::ccw(QPointF pt1, QPointF pt2, QPointF pt3)
{
    return (pt2.x()-pt1.x())*(pt3.y()-pt1.y()) - (pt2.y()-pt1.y())*(pt3.x()-pt1.x());
}

点积除以常数,cos因为排序角度与排序相同cos in [0, Pi].

qreal Interpolation::dp(QPointF pt1, QPointF pt2)
{
    return (pt2.x()-pt1.x())/qSqrt((pt2.x()-pt1.x())*(pt2.x()-pt1.x()) + (pt2.y()-pt1.y())*(pt2.y()-pt1.y()));
}

主要功能:

void Interpolation::ConvexHull()
{
    QPointF points[m_N+1]; // My number of points
    QPointF pt_temp(m_pt[0]);
    qreal angle_temp(0);
    int k_temp(0);

使用points[1]低y点填充数组点:

    for (int i(1); i < m_N; ++i)
    {
        if (m_pt[i].y() < pt_temp.y())
        {
            points[i+1] = pt_temp;
            pt_temp = …

我有一个自定义形状,如图所示.假设覆盖图像中形状的蓝色矩形描绘了该形状的边界框.

如果我在边界矩形的一个对角线上画线,我怎样才能得到交点(在图像中它们是用绿色绘制的)？

我使用的是Java2D,我有一个GeneralPath,其中包含我在屏幕上绘制形状的所有坐标.

这实际上更像是一个数学问题.但鉴于3分,你如何计算最远点voronoi图？

首先找到通过所有这些并抓住其中心的圆圈.不知道从哪里开始.画面很奇怪

我在绘制箭头方向时遇到了一些问题.我有点(x,y)坐标和它们的角度.我想要做的是根据给定的角度绘制箭头(只是为了在每个点坐标中将点方向显示为箭头).这里,我们应该假设'+ x','+ y',' - x',' - y'的坐标分别是90度,0度,270度,180度.

我对Python绘图工具有点不熟悉.我仍然不确定绘制方向点(基于角度的箭头)我是否使用pylab或其他模块或..仍然不确定.我将以下代码作为示例进行了更好的描述:

 # Inputs:
 x = np.array([ 2, 4, 8, 10, 12, 14, 16])
 y = np.array([ 5, 10, 15, 20, 25, 30, 35])
 angles = np.array([45,275,190,100,280,18,45]) 

 import numpy as np
 import scipy as sp
 import pylab as pl

 def draw_line(x,y,angle):

     # First, draw (x,y) coordinate ???
     # Second, according to the angle indicate the direction as an arrow ???

如何在MATLAB 3D图形的透视图中更改消失点(P1,P2,P3)？下面是一个解释我的意思的方案:

在此先感谢您的帮助.

这是我的第一篇文章,如果我违反任何礼仪规则,请告诉我.

我正在尝试在python中编写一个程序,其中包含形状文件(现在是国会区)并用圆圈"打包"它们.最终目标是获得圆的中心点和半径.我想以最少的圆圈覆盖最大区域.

到目前为止,我通过谷歌找到的所有资源都是关于标准几何对象(如正方形/圆形/三角形等)中的圆形包装......所以我的本能是尝试将这些形状转换为三角形或其他东西,然后应用一些现有的算法更简单的形状.

如果形状有很多小的凹边,这似乎是解决问题的正确途径吗？或者是否有一些我无法通过谷歌找到的算法,任何人都知道这已经做到了？总计算几何noob但愿意学习.