标签: computational-geometry

问题：假设您在 2D 平面中有一组点。我想知道这组点是否位于规则网格上（如果它们是 2D 点阵的子集）。我想要一些关于如何做到这一点的想法。

现在，假设我只关心这些点是否形成轴对齐的矩形网格（底层晶格是矩形，与 x 轴和 y 轴对齐），并且它是一个完整的矩形（网格的子集）晶格有一个没有孔的矩形边界）。任何解决方案都必须非常有效（优于 O(N^2)），因为 N 可以是数十万或数百万。

上下文：我编写了一个 2D 矢量场图生成器，它适用于任意采样的矢量场。在采样在规则网格上的情况下，有更简单/更有效的插值方案来生成绘图，我想知道什么时候可以使用这种特殊情况。特殊情况已经足够好，值得做。该程序是用 C 编写的。

QPolygonF具有与其他 QPolygonF 并集、相交和相减的方法，但我需要与 QLineF 执行相交测试。API 中似乎缺少此功能。

我想我可以做这样的事情：

if (polygon .containsPoint (line .p1 ()) != polygon .containsPoint (line .p2 ())
    return true;

QPointF a = polygon .back ();
foreach (QPointF b, polygon)
{
    if (QLineF :: BoundedIntersection == line .intersect (QPointF (a, b))
       return true;
    a = b;
}

return false;

上面可能隐藏着一些数字或边缘情况的惊喜，所以我宁愿不这样做。

Qt API 中是否有我看不到的提供的方法？

我试图确定特定点是否位于多面体内.在我目前的实现中,我正在研究的方法是我们正在寻找多面体的面数组(在这种情况下为三角形,但稍后可能是其他多边形).我一直在努力从这里找到的信息开始工作:http://softsurfer.com/Archive/algorithm_0111/algorithm_0111.htm

下面,你会看到我的"内部"方法.我知道nrml /正常的东西有点奇怪..它是旧代码的结果.当我运行它时,无论我给出什么输入,它似乎总是返回真实.(这个问题已经解决了,请参阅下面的答案 - 此代码现在正在运行).

bool Container::inside(Point* point, float* polyhedron[3], int faces) {
  Vector* dS = Vector::fromPoints(point->X, point->Y, point->Z,
                 100, 100, 100);
  int T_e = 0;
  int T_l = 1;

  for (int i = 0; i < faces; i++) {
    float* polygon = polyhedron[i];

    float* nrml = normal(&polygon[0], &polygon[1], &polygon[2]);
    Vector* normal = new Vector(nrml[0], nrml[1], nrml[2]);
    delete nrml;

    float N = -((point->X-polygon[0][0])*normal->X + 
                (point->Y-polygon[0][1])*normal->Y +
                (point->Z-polygon[0][2])*normal->Z);
    float D = dS->dot(*normal);

    if (D == 0) {
      if …

我有一组轴平行的二维矩形，由它们的左上角和右下角定义（都在整数坐标中）。给定一个点查询，你如何有效地确定它是否在一个矩形中？我只需要一个是/否的答案，不需要担心它在哪个矩形中。

我可以通过查看 x 是否在 x1 和 x2 之间以及 y 是否在 y1 和 y2 之间来检查 (x,y) 是否在 ((x1, y1), (x2, y2)) 中。我可以为每个矩形单独执行此操作，这些矩形以矩形数量的线性时间运行。但是由于我有很多矩形并且我会做很多点查询，所以我想要更快的东西。

有没有快速的方法来做到这一点？在线搜索显示函数或单个多边形的凸性.但我需要能够检查整个模型.物体可以具有凸面,但可以像圆环一样整体凹入.

我想制作一个单位向量的查找表。每个单位向量将映射到该表中的一个容器，并且该容器将包含具有相似方向的一小组向量的一些信息。

我可以轻松地使用 ($\theta$, $\phi$, 1) 表示向量，然后将角度范围切入容器以制作 2D 查找表（因此第一个容器是 0 到 $2* 范围内的 theta \pi / N$，其中 N 是我想要的 theta 方向的 bin 数量）。这样做的问题是，我认为某些箱将比其他箱代表单位球体表面上更大的区域，并且我希望获得大致相同大小的区域。

我认为均匀划分角度范围会使某些垃圾箱比其他垃圾箱更大，这是错误的吗？如果没有，有人知道制作这个查找表的更好方法吗？

我发现了一些像这样的论文和演示文稿，但我不会撒谎，我不明白它（我听说过勒贝格测度，但如果我知道它意味着什么，我会被诅咒的），而且它无论如何，看起来并不是特别有希望。

我有一堆共面点在 3D 空间中定义了一个多边形。这些总是以相同的方式缠绕（例如顺时针）。我需要确定包含该多边形的平面的有符号法线，即，知道该多边形的“向上”方向。

起初这似乎很容易：取两条边（顶点差）并计算叉积。但是如果边缘恰好是共线的（你得到一个零幅度的叉积），那就失败了。

然后我尝试遍历顶点列表，直到找到与第一条边成相当大角度的第二条边。这在凸多边形上可靠地工作，但如果我最终得到的两条边没有定义多边形内部的三角形，它可能会在非凸多边形上失败（指向相反的方向）。

我知道如果我先对多边形进行三角剖分，那么我可以轻松可靠地检查任何三角形的面……但问题是我的三角剖分库需要知道平面法线。所以，鸡蛋必须先于鸡。

如何在非凸多边形中选取两条边（或三个顶点）来可靠地定义多边形面向的方向？

VTK 中顶点和点的主要区别是什么？

好吧，我正在为vtkPolyData输出分配一些计算点：

vtkPolyData* oput = vtkPolyData::SafeDownCast(out_info->Get(vtkDataObject::DATA_OBJECT()));

我想知道是使用方法SetVerts(vtkCellArray *v)还是方法SetPoints(vtkPoints *)。

我需要以 AX+BY+CZ+D=0 的形式计算两个平面的交点，并以两个 (x,y,z) 点的形式得到一条线。我知道如何进行数学计算，但我想避免发明自行车并使用有效且经过测试的东西。是否有任何库已经实现了这一点？试图搜索 opencv 和 google，但没有成功。

我想在python中找到两个向量之间的顺时针角度，角度应该在（-90,90）范围内

计算角度的方程/代码是什么？

class Vect:
  def __init__(self, a, b):
    self.a = a
    self.b = b

  def findClockwiseAngle(self, other):
    ## how to compute ??
    pass


vector1 = Vect(a1,b1)  ## a1*i + b1*j
vector2 = Vect(a2,b2)  ## a2*i + b2*j
angle = vect1.findClockwiseAngle(vect2)