标签: computational-geometry

您将在平面上获得一组U个n点,并且可以在恒定时间内计算任意一对点之间的距离.选择一个名为C的U的子集,使得C中恰好有k个点,并且C中最远的2个点之间的距离对于给定的k尽可能小.1 <k <= n

除了明显的n-choose-k解决方案之外,最快的方法是什么？

给定一个凸polgyon和一个数字N,我如何找到最小的多边形

1. 包含原始多边形中的每个点
2. 正好有N个角点

例如,假设我有一组点并计算它们的凸包(绿色).现在我想找到包含所有点的最小四边形(红色)

很容易看出任何其他具有4个角的多边形要么更大,要么不能包含所有点.但是如何在一般情况下找到这个多边形呢？

编辑:

最小的多边形是指覆盖最小区域的多边形,但我不确定最小的圆周是否会产生不同的结果.

我添加了另外两个示例图片,遗憾的是,在其中一个答案中似乎没有使用"删除边缘"方法

一些背景资料:

目标是通过图像识别准确地确定形状.例如拍摄一个长方体的照片.2D照片中框内的所有点都将包含在6角凸多边形中.然而,由于真实世界的形状没有完美的角落,并且相机增加了一些模糊,因此该多边形的边缘将是圆形的.请参阅问题从凸点获取角落的附图

我正在研究一种数据挖掘算法,我想从特征空间的特定点中选择一个随机方向.

如果我为[-1,1]中的每个n维选择一个随机数,然后将矢量标准化为长度1,我将在所有可能的方向上得到均匀分布？

我在理论上只是在这里说,因为计算机生成的随机数实际上并不是随机的.

我正在研究教授指定的一个问题,而我正在寻找一种方法来检测3点之间的角度是否大于180度,例如:

我想检测alpha是否超过180度.无论如何,我的教授有一个解决问题的代码,但他有一个名为zcross的函数,但我不知道它是如何工作的.有谁能告诉我？他的代码在这里:

#include <fstream.h>
#include <math.h>
#include <stdlib.h>

struct point {
    double  x;
    double  y;
    double  angle;
};

struct vector {
    double  i;
    double  j;
};

point   P[10000];
int     hull[10000];

int 
zcross (vector * u, vector * v)
{
    double  p = u->i * v->j - v->i * u->j;
    if (p > 0)
    return 1;
    if (p < 0)
    return -1;
    return 0;
}

int 
cmpP (const void *a, const void *b)
{
    if (((point *) a)->angle < ((point *) …

2D版本中的经典算法问题通常被描述为

给定n个非负整数表示每个柱的宽度为1的高程图,计算下雨后能够捕获的水量.

例如,给定输入

[0,1,0,2,1,0,1,3,2,1,2,1] 

返回值是

6

我用来解决上述2D问题的算法是

int trapWaterVolume2D(vector<int> A) {
    int n = A.size();
    vector<int> leftmost(n, 0), rightmost(n, 0);

    //left exclusive scan, O(n), the highest bar to the left each point
    int leftMaxSoFar = 0;
    for (int i = 0; i < n; i++){
        leftmost[i] = leftMaxSoFar;
        if (A[i] > leftMaxSoFar) leftMaxSoFar = A[i];
    }


    //right exclusive scan, O(n), the highest bar to the right each point
    int rightMaxSoFar = 0;
    for (int i = n - 1; i …

在工业中,通常存在一个问题,您需要计算材料的最有效使用,无论是织物,木材,金属等.因此起点是给定尺寸的X形状,由多边形和/或弯曲制成lines和target是给定尺寸的另一个多边形.

我假设许多当前的CAM套件实现了这一点,但没有使用它们或内部的经验,使用什么样的计算算法来找到最有效的空间利用？有人能指出我讨论这个主题的书或其他参考书吗？

检测线是否与凸多边形相交的O(n)算法包括检查多边形的任何边是否与线相交,并查看交点的数量是奇数还是偶数.

是否存在渐近更快的算法,例如O(log n)算法？

我正在寻找一个计算二维alpha形状的实现.我正在运行ubuntu.我更喜欢这个任务的命令行实用程序,但也可以使用python库.

在Google中,我发现了许多计算alpha形状的实现.但它们都没有输出我想要的东西.作为输入,我有一个二维点列表(例如,文本文件中每行一对浮点数).作为输出,我想要另一个具有相同比例的二维点列表.

我已经尝试安装cgal的最新python绑定,但是这些在一段时间内都没有得到支持,不再在Ubuntu 11.04上编译(我也试过Ubuntu 10.04但没有运气). Clustr,由Aaron Straup Cope在flickr开发的项目也不会在Ubuntu 11.04上编译(可能是因为它也与旧的CGAL库绑定).

我还在贝尔实验室的Ken Clarkson 尝试过这个实现.它输出几乎我想要的,输出似乎是另一个规模,它将浮动变成整数.

我也尝试了dionysus的python绑定.这些编译,但当我fill_alpha2D_complex(points, f)用我的点列表输入函数时,输出不是我所期望的.它不是一个二维点的列表,而是似乎是一个"持久性图",我不知道这意味着什么.

有人知道这个问题的简单解决方案吗？

更新:我想打印出与alpha形状相关的点,它们已经处于不再连接的边缘.我认为这意味着"给我与最小的alpha值相关联的点,使形状连接起来."

更新我现在从dionysus实现中找到了如何从Ken Clarkson的实现和(或多或少我想要的)获得我想要的东西.Clarkson的实现是做正确的事情,它只是输出点的索引而不是点本身(与dionysus相同的故事),我需要得到一些可选的标记.我写的包装器如下.这种解决方案是理想的,因为它产生的α形状既连接又不包含孔.Alpha自动设置.另一方面,狄俄尼索斯并没有自动发现这种α值.另外,Clarkson的实现可以设置为输出形状的ps图像(带-afps标志).要使用非古代版本的GCC编译Clarkson的代码,您需要按照此处概述的步骤操作.以下代码可用作库或独立包装器:

#!/usr/bin/python -O

import sys, os
import subprocess
import tempfile

hull_path = "./hull.exe"

def get_alpha_shape(points):
    # Write points to tempfile
    tmpfile = tempfile.NamedTemporaryFile(delete=False)
    for point in points:
        tmpfile.write("%0.7f %0.7f\n" % point)
    tmpfile.close()

    # Run hull
    command = "%s -A -m1000000 -oN < …

免责声明:是的,这是一个家庭作业,我正在思考它几天但却找不到路要走.

所以有n条直线(y = ax + b),我想找到它们的上部包络线(图中的粗体部分).它必须在O(nlogn).

我的理解是,我需要找到一种方法来忽略一些行,因为如果我搜索所有行,它将不是O(nlogn).

我正在考虑分而治之的方法,以便我可以将列表分成两部分并递归地继续直到解决方案.但后来我不知道如何摆脱一些线路.很明显,我不需要考虑图片中的一些底线,因为他们不可能为解决方案做出贡献.但是我没有想到任何事情.任何提示都表示赞赏.

标准凸包算法不适用于(经度,纬度)点,因为标准算法假设您需要一组笛卡尔点的船体.纬度 - 经度点不是笛卡尔坐标,因为经度在反子午线(+/- 180度)处"环绕".即,经度179以东两度是-179.

因此,如果您的一组点恰好跨越反子午线,您将计算出错误地在世界各地伸展的虚假船体.

我可以使用标准凸包算法来解决这个问题的任何建议,或指向正确的"地球"船体算法？

现在我想起来,有更多有趣的案例需要考虑而不是跨越反梅迪安.考虑一个包围地球的点"带" - 它的凸包将没有东/西边界.或者甚至更进一步,{(0,0),(0,90),(0,-90),(90,0),( - 90,0),(180,0)}的凸包是什么？ - 它似乎包含整个地球表面,所以它的周边有哪些点？