标签: computational-geometry

有一个点列表,我如何找到顺时针顺序？

例如:

point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)

会说它是逆时针(或逆时针,对某些人来说).

我如何"膨胀"多边形？也就是说,我想做类似的事情:

要求是新的(膨胀的)多边形的边/点都与旧的(原始)多边形处于相同的恒定距离(在示例图片上它们不是,因为那时它必须使用弧来填充顶点,但是让我们暂时忘掉它;)).

我正在寻找的数学术语实际上是向内/向外多边形的偏离.+1指向balint指出这一点.替代命名是多边形缓冲.

我的搜索结果:

以下是一些链接:

• 多边形脱靶策略综述
• 多边形偏移,问题
• 缓冲多边形数据

我有纬度和经度,我想从数据库中提取记录,该记录具有最近的纬度和经度,如果该距离长于指定的距离,则不检索它.

表结构:

id
latitude
longitude
place name
city
country
state
zip
sealevel

给定一个x,y点数组,如何按顺时针顺序(围绕它们的整体平均中心点)对该数组的点进行排序？我的目标是将点传递给线创建函数,以最终看起来相当"坚实"的东西,尽可能凸起,没有相交的线.

为了它的价值,我正在使用Lua,但任何伪代码都会受到赞赏.非常感谢您的帮助!

更新:作为参考,这是基于Ciamej优秀答案的Lua代码(忽略我的"app"前缀):

function appSortPointsClockwise(points)
    local centerPoint = appGetCenterPointOfPoints(points)
    app.pointsCenterPoint = centerPoint
    table.sort(points, appGetIsLess)
    return points
end

function appGetIsLess(a, b)
    local center = app.pointsCenterPoint

    if a.x >= 0 and b.x < 0 then return true
    elseif a.x == 0 and b.x == 0 then return a.y > b.y
    end

    local det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)
    if det < 0 then return true
    elseif det > 0 then …

我试图找出从3D范围数据进行表面重建的算法.乍一看,似乎Ball旋转算法(BPA)和泊松表面重建是更成熟的方法？

• 除了BPA和泊松表面重建算法之外,该领域中已建立的更稳健的算法是什么？
• 推荐的研究出版物
• 有可用的源代码吗？

我想确定一个多边形并实现一个算法,该算法将检查一个点是在多边形内部还是外部.

有谁知道是否有任何类似算法的可用示例？

问题:

在2维平面上给出N个点.同一条直线上的最大点数是多少？

问题有O(N ²)解决方案:遍历每个点并找到dx / dy与当前点相关的点数.将dx / dy关系存储在哈希映射中以提高效率.

有没有比O(N ²)更好的解决这个问题的方法？

从手册页XFillPolygon:

• 如果shape是复杂的,则路径可以自相交.请注意,路径中的连续重合点不会被视为自相交.

• 如果shape是Convex,对于多边形内的每对点,连接它们的线段不与路径相交.如果客户端知道,指定Convex可以提高性能.如果为非凸的路径指定Convex,则图形结果未定义.

• 如果shape是Nonconvex,则路径不会自相交,但形状不是完全凸的.如果客户端知道,指定Nonconvex而不是Complex可以提高性能.如果为自相交路径指定Nonconvex,则图形结果未定义.

我遇到填充性能问题XFillPolygon,正如手册页所示,我想要采取的第一步是指定多边形的正确形状.我目前正在使用Complex来保证安全.

是否有一种有效的算法来确定多边形(由一系列坐标定义)是凸的,非凸的还是复杂的？

我画了一个有10000个顶点(100x100)的三角形网格,它将是一个草地.我使用了gldrawelements().我看了一整天,仍然无法理解如何计算这个法线.每个顶点是否有自己的法线或每个三角形都有自己的法线？有人能指出我正确的方向如何编辑我的代码以合并法线？

struct vertices {
    GLfloat x;
    GLfloat y;
    GLfloat z;
}vertices[10000];

GLuint indices[60000];

/*
99..9999
98..9998
........
01..9901
00..9900
*/

void CreateEnvironment() {
    int count=0;
    for (float x=0;x<10.0;x+=.1) {
        for (float z=0;z<10.0;z+=.1) {
            vertices[count].x=x;
            vertices[count].y=0;
            vertices[count].z=z;
            count++;
        }
    }
    count=0;
    for (GLuint a=0;a<99;a++){
        for (GLuint b=0;b<99;b++){
            GLuint v1=(a*100)+b;indices[count]=v1;count++;
            GLuint v2=(a*100)+b+1;indices[count]=v2;count++;
            GLuint v3=(a*100)+b+100;indices[count]=v3;count++;
        }
    }
    count=30000;
    for (GLuint a=0;a<99;a++){
        for (GLuint b=0;b<99;b++){
            indices[count]=(a*100)+b+100;count++;//9998
            indices[count]=(a*100)+b+1;count++;//9899
            indices[count]=(a*100)+b+101;count++;//9999
        }
    }
}

void ShowEnvironment(){
    //ground
    glPushMatrix();
    GLfloat GroundAmbient[]={0.0,0.5,0.0,1.0};
    glMaterialfv(GL_FRONT,GL_AMBIENT,GroundAmbient);
    glEnableClientState(GL_VERTEX_ARRAY);
    glIndexPointer( GL_UNSIGNED_BYTE, 0, indices ); …

测试点P是否在由一组点X形成的凸包内的最简单方法是什么？

我想要一种在高维空间(例如,最多40维)中工作的算法,该算法不会明确地计算凸包本身.有任何想法吗？