标签: computational-geometry

如何测试光线和三角形,如果存在,如何获得光线原点到交点的距离？我可以使用什么优化,如果在我的程序中我必须检查1射线到~10000三角形？

在我完成2D三角测量后,一些三角形具有相同的颜色,我想重新组合它们以绘制成相似颜色的图形路径.我发现如果我只是逐个绘制三角形,一些图形渲染器会显示三角形之间的接缝(至少如果涉及抗锯齿和/或透明度).

那么我如何获取一组(非重叠)三角形并生成一个图形路径,其中可能包含孔和不相交的多边形？

盲目地将三角形添加到图形路径实际上非常适合填充(当然不是用于抚摸),但是导出那些额外的内部点感觉不对.

我有一个由平面上的连续边构成的多边形,并且希望将其细分为三角形或矩形的子多边形.我在哪里可以找到算法来做到这一点？谢谢 !

我正在阅读C++中的Robert Sedwick Algorithms的一本书.以下是关于复合数据结构的书中给出的示例.

问题陈述:给定"d",我们想知道单位平方中一组N个点中的多少对可以通过长度小于"d"的直线连接.

以下程序使用逻辑将单位squre划分为网格,并维护链接列表的二维数组,其中一个列表对应于每个网格方块.选择网格足够精细使得距离"d"内的所有点都在相同的网格正方形或相邻的网格正方形中.

我的问题是

1. 为什么作者在malloc2d(G + 2,G + 2)中分配G + 2？
2. 在gridinsert函数中,为什么作者执行以下语句int X = x*G + 1; int Y = y*G + 1; ？
3. 在for循环中为什么我们对X-1进行了初始化并且j初始化为Y-1？
4. 在代码中我们在相同网格方格或相邻网格中保持距离d内的点？

在理解以下程序时,请通过简单示例请求您的帮助.

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
using namespace std;


float randFloat() {
    return 1.0*rand()/RAND_MAX;
}


struct myPoint {
    float x;
    float y;
};

float myDistance(myPoint a, myPoint b) {
    float dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx*dx + dy*dy);
}

struct node {
    myPoint …

我正在阅读其他人的代码,他将平面表示为法线和偏移,但我不确定该偏移是什么.我想这是从世界起源到飞机中心的距离？

谢谢

如果给出一个n多边形,一条长度线k(at x,y和angle a),是否有一个算法来检测我碰撞过的多边形的哪一边(如果有的话)？到目前为止,我已经尝试测试是否x,y在多边形之外,然后遍历多边形的每个边缘,计算到每个端点的距离.这是一个JS小提琴,展示了我创造的世界.

这是JavaScript(HTML和CSS不值得复制):

var eventLoop,
    maxVelocity = 10,
    agility = 5,
    baseLength = 5,
    degree = ((2*Math.PI)/360),
    world = document.getElementById('world'),
    context = world.getContext("2d"),
    boundry = [[180, 120],[240, 60],[360, 40],[420, 120],[360, 220],[350, 240],[360, 265],[470,360],[450,480],[360,540],[240,550],[140,480],[120,470],[100,360],[120,300],[220,240],[240,220]],
    camera = {
        location: {
            x:300,
            y:90
        },
        angle: 0,
        velocity: 0
    },
    engine = {
        drawWorld: function(shape, context) {
            var point,
                index,
                size = shape.length;

            context.clearRect(0, 0, world.width, world.height);
            context.beginPath();
            for(index = 0; index < …

我在3d空间中收集了百万点.

每个点都是一个对象

Struct Point
{
    double x;
    double y;
    double z;
};

百万点以一些随机顺序存储在c ++向量MyPoints中.

我想根据空间中点的空间分布对这些百万点进行排序,这样物理上更接近的点在排序后也应该在我的阵列内更近.

我对如何做到这一点的第一个猜测如下:首先对Z轴进行排序,然后沿Y轴排序点,然后沿X轴排序点

MyPointsSortedAlongZ = Sort(MyPoints, AlongZAxis )
MyPointsSortedAlongY = Sort(MyPointsSortedAlongZ , AlongYAxis  )
MyPointsSortedAlongX = Sort(MyPointsSortedAlongY , AlongYAxis  )

首先,我不知道这种方法是否正确.我的最终点数MyPointsSortedAlongX是否会在空间上完美排序(或几乎在空间上排序)？

其次,如果这种方法是正确的,它是最快的方法.有什么更好的方法呢？

在下图中，我需要找到从A到B的弧的中点M：

我想根据以下信息找到M：

• AX和AY，A的坐标
• BX和BY，B的坐标
• 半径，圆弧半径
• Center.X和Center.Y，圆弧的中心

如何计算M的坐标？

我目前在C中做一些2D几何,主要是相交的线.这些线有各种斜率:0.001到1000(例子,我甚至都不知道).

到目前为止我一直在使用浮点数并且不必担心值是否非常小(然后浮点将存储0,0011作为1e-3而没有舍入)或非常高(然后1001将存储为1e3)在这两种情况下,在相关的情况下几乎没有精度损失.

但现在我想尝试没有浮点数,整数.如何保持计算的精确度？我可以有一个标志告诉我斜坡是大还是小,然后考虑十分之一的大坡度和十倍小的坡度,这样小坡度的倒圆就没问题了,大斜坡的情况下也没有溢出.但这感觉很头疼.

基本上我仍然需要能够区分0.2和0.4的斜率以及斜率为1000和2000的溢出侧(假设在1000处溢出 - 这里没有问题).

还有其他想法吗？

作为CG新手，我想知道是否存在不仅仅基于站点之间的欧几里得距离而是某些其他度量的Voronoi分区，这样的分区是否仍将保留Voronoi图的属性？

在阅读教科书时，我遇到了一个Voronoi图的示例，其中2D平面上的站点代表足球运动员，如果球碰巧位于某些运动员的Voronoi地区，则意味着他应该朝着它前进，因为他离它最近。现在，如果不仅仅考虑玩家之间的欧几里得距离，我们还考虑了他们的速度，更快的玩家拥有更大的Voronoi单元。

我们失去对等的事实会破坏Voronoi图本身的结构吗？