标签: triangulation

阅读完相关内容后，我想到了这一点：

#include <vector>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Delaunay_triangulation_2<K>                   Delaunay;    
typedef K::Point_2                                          Point;

void load_points(std::vector< Point >& points)
{
  points.push_back(Point(1., 1.));
  points.push_back(Point(2., 1.));
  points.push_back(Point(2., 2.));
  points.push_back(Point(1., 2.));      
}

int main()
{
  std::vector< Point > points;
  load_points(points);
  Delaunay dt;
  dt.insert(points.begin(), points.end());
  std::cout << dt.number_of_vertices() << std::endl;

  typedef std::vector<Delaunay::Face_handle> Faces;
  Faces faces;
  std::back_insert_iterator<Faces> result( faces );
  result = dt.get_conflicts ( Delaunay::Point(1.5, 1.5),
                                std::back_inserter(faces) );

  return 0;
}

这应该找到外接圆包含该点的面。之后，我必须采用这些三角形并使用一种方法来测试该点是否在它们内部（CGAL 会这样做吗？我知道这很容易实现）。

不管怎样，我怎样才能把三角形从脸上去掉呢？

答案是

CGAL::Triangle_2<K> f = dt.triangle(faces[0]);
std::cout << dt.triangle(faces[0]) << …

当网络用于定位时，这些无线网络是广播他们的ID，还是网络实际上是运营商网络，你打电话时使用的网络？

据我所知，每当我使用 GPS 时，都会使用手机信号塔来加速这个过程，这被称为 AGPS。即使在设备上禁用了无线功能，也会发生这种情况。

当您使用网络提供商时，它会使用附近的无线网络，而不会与蜂窝塔三角测量进行任何交互。为了实现这一点，必须打开无线。

这样对吗？

我已经绘制了n随机点（黑点）并使用了 delaunay 三角剖分，现在我想插入m随机评估点（红点），所以我需要计算评估点位于哪个三角形内。

计算三角形每个点的顶点的方法是什么？

首先让我澄清一下..我不是在问 2D 网格，要确定 2D 网格的缠绕顺序，使用法向 z 方向非常容易。

其次，我不要求任何优化算法，我不担心时间或速度，我只想用我的网格来做。

当我使用贪婪投影三角剖分算法对 3D 对象进行三角剖分时，会发生此问题。检查所附图片。

如果我使用“计算有符号面积”或“三角形的 AB 和 BC 向量的交叉产生”对该模型应用 2D 方法，它只能求解 2D 网格，但 3D 网格又如何呢？

首先我们需要检查哪些三角形在 3D 网格中缠绕方向错误，然后我们只考虑这些三角形，那么问题是，我们如何检查哪些三角形在 3D 中缠绕方向错误？我们不能只用 2D 方法来做我已经测试过但没有成功。

例如，对于球体，我们不能对球体应用 2D 方法。那么有没有办法解决这个问题呢？

谢谢。

更新#1：

下面是检查哪条边具有相同缠绕的算法。效果不太好，我不知道为什么。理论上它应该纠正所有三角形，但它没有纠正。例如，在附图中检查球体的情况下。有问题。

void GLReversedEdge(int i, int j, GLFace *temp)
{
    //i'th triangle
    int V1 = temp[i].v1;
    int V2 = temp[i].v2;
    int V3 = temp[i].v3;

    //i'th triangle edges
    int E1[] ={V1, V2};
    int E2[] ={V2, V3};
    int E3[] ={V3, V1};

    //adjacent triangle
    int jV1 = temp[j].v1;
    int jV2 …

我正在尝试对位图进行三角测量（为我的 2d 游戏生成关卡），但我被卡住了。我正在使用 Jonathan Shewchuk 的 Triangle 库使用这个包装器。

我从一张图片开始，

然后我检测边缘并确定哪些顶点是洞。我每四个选择一次进行三角测量，

然后我将这些点传递给三角测量，但我最终得到了这样的结果

我的洞消失的地方。我究竟做错了什么？另外，为什么我会得到一些凸包而不是三角多边形？

到目前为止，这是我的代码：

    #here i am loading all data, that i will use later on but i had to insert that, just in case
    mapfg = glob(path.join(pathtomapfolder, "Foreground.png"))[0] #Getting map foreground image
    mapob = glob(path.join(pathtomapfolder, "Obstacles.png"))[0] #Getting map file
    mappr = glob(path.join(pathtomapfolder, "Properties.txt"))[0] #Getting map info file
    self.mapprops = [mapob, mapfg, mappr]
    #getting ground and obstacles
    obsbitmap = Image.open(self.mapprops[0])
    lockBitmap = obsbitmap.load()
    compareClr = (0, 0, 0)
    for …

我正在尝试使用众所周知的双通道扫描线算法来实现多边形三角测量，该算法将多边形细分为第一通道扫描线中的单调子组件，然后在第二通道中对这些单调组件进行三角测量。我当前的实现适用于一般情况，但我一生都无法弄清楚如何调整它来处理包含多个重合边缘段的输入（从左到右扫描时具有相同 x 坐标的段，或者从右向左扫描时 y 坐标相等）。

编辑：我刚刚意识到我提出这个问题的方式使它变得相当长和冗长，所以这里有一个快速的TL;DR; 对于任何了解多边形三角测量但不想阅读整个内容的人：以下形状是三角测量算法第二遍的有效输入吗？如果是：如何调整第二遍来处理它，如果否：如何调整第一遍，使其生成可以输入第二遍的单调子组件：

http://www.wouterbijlsma.nl/~wouter/tmp/RTdr6rET9.png

此点以下问题的长版本;-)

该算法的快速概述：

1. 第一遍将输入多边形细分为“单调子组件”。单调子组件是一个多边形，可以分为 2 个连接的链，这些链的坐标要么从左到右排序（当使用垂直扫描线实现算法时），要么从上到下排序（当使用水平扫描时）线）。假设我们使用垂直扫描线：每个单调子组件可以分为上链和下链，在最小和最大 x 坐标处连接，并且当扫描任一链的顶点时，x 坐标为增加。如果子组件是严格单调的，则上链和下链不能具有具有相同x坐标的边缘段（即：垂直边缘段）。

2. 第二遍扫描单调子组件，并通过添加内部边缘将它们细分为三角形。这个想法是，每个子组件从左到右扫描，并且在扫描线击中的每个顶点处，可能会发生以下两种情况之一：a）可以通过添加对角线来对扫描线左侧的未三角化区域进行三角剖分，或 b) 当前顶点无法“看到”扫描线左侧未三角化区域中任何先前扫描过但未处理的顶点。在情况 b) 中，顶点被压入堆栈（“反射链”），并且通过构造，在某个时刻会发生情况 a)，并且反射链的顶点将被一一弹出并与到最后一个扫描线顶点的对角线。

上面的描述缺乏一些细节，但我假设任何知道如何回答我的问题的人都已经理解了该算法，所以我不会在这里详细介绍。

我遇到的问题如下：假设我有一个代表指向左的箭头的多边形，例如如下所示：

http://www.wouterbijlsma.nl/~wouter/tmp/RTdr6rET9.png

当我将这个形状输入到我的算法中时，单调细分过程不会影响该形状：其中有垂直边缘，因此它不是严格单调的，但它是单调的，并且据我了解该算法，它不必在对它进行三角测量之前先对其进行细分（也许这是我出错的地方，因为我的假设很糟糕）。

现在假设我将（未修改的）箭头多边形输入第二遍以对其进行三角测量。如何处理箭头底部的 2 个垂直边缘段？扫描线算法要求多边形的顶点从左到右排序，因此您会假设答案将归结为如何对具有相同 x 坐标的顶点进行排序（例如，按链顺序，或在 y 坐标上，或在多边形边界索引上），但无论我使用什么排序，三角测量总是会失败。

我们将最左边的顶点称为顶点 0，并按逆时针顺序对顶点进行排序。这意味着箭头底部的 4 个顶点是顶点 1、2、5 和 6。我们有三种排序选项：

1. 我用来实现该算法的一些源材料说“在增加 y 坐标的情况下对具有相等 x 坐标的顶点进行排序”，即：1、2、5、6。如果我这样做并扫描它们，第一个三角形就出来了（ 0, 1, 2)，但之后算法将添加一条边 (5, 2)，从而创建一个 4 顶点组件 (0, 2, 5, 6)。不添加边 (0, 5)，因为三角剖分算法规定将边添加到反射链上除第一个之外的所有先前未三角化的顶点（更改此设置会破坏一般情况）。虽然由 4 个顶点包围的多边形区域的形状是三角形，但它显然不是三角形，因为它有 4 个点，而且根据大多数定义，它也不是有效的多边形，因为它具有共线边。

2. 我读到的另一篇论文说“打破联系，从而保留链序”。这意味着我的示例中的 4 个顶点将排序为 1、2、6、5，因为下部链和上部链都是从左到右运行的。如果我按这个顺序扫描它们，我会再次得到一个三角形 (0, 1, 2)，但是扫描的下一个顶点 (6) 将创建一个多边形 (0, …

好的，所以我有一个多边形（简单但凹形），我试图将其切成三角形以使其与其他多边形碰撞。

我知道我的多边形是凹面的，所以我决定使用 LibGDX EarClippingTriangulator来设法将它切成三角形。

所以，通过这段代码，我得到了我的三角形顶点：

public void triangulate()
    {
        Vector<float[]> trianglesVertices = new Vector<float[]>();
        ShortArray pointsCoords = new ShortArray();
        EarClippingTriangulator triangulator = new EarClippingTriangulator();

        // Cut in triangles
        pointsCoords = triangulator.computeTriangles(this.getTransformedVertices());

        // Make triangles
        for (int i = 0; i < pointsCoords.size / 6; i++)
        {
            trianglesVertices.add(new float[] {
                    pointsCoords.get(i), pointsCoords.get(i+1),
                    pointsCoords.get(i+2), pointsCoords.get(i+3),
                    pointsCoords.get(i+4), pointsCoords.get(i+5),
            });
            Polygon triangle = new Polygon(trianglesVertices.get(i));
            triangles.add(triangle);
        }

        System.out.printf("Triangulation made %d triangles.\n", pointsCoords.size / 6);
    }

但是当我尝试绘制我刚刚制作的那些三角形时，它们只是在 0,0 坐标中堆叠......而且，所有三角形看起来几乎相同是否正常，我的意思是它们都有相同的方向？

我没有找到太多关于 libgdx 的这种截断用途的信息你能帮忙吗？

（对不起我的英语我是法国人，对不起没有照片，我在这里太年轻了）

编辑： …

在计算机视觉中，“中点”方法解决了从两个 2D 点确定 3D 点的三角测量问题（请参见此处）。是否可以将其推广到两个以上的点，例如 n 点，它叫什么？这篇文章确实提到了直接线性变换，但我不确定这就是我正在寻找的......

我有一个现有的系统，它提供 3D 网格。提供的数据是一个包含 3 个分量 (x, y, z) 的顶点坐标数组和一个索引列表。问题是索引列表是一个连续的四元组数组。
系统必须首先使用核心配置文件OpenGL 上下文运行，然后再使用 OpenGL ES 3.x。

我知道所有四边形都具有相同的缠绕顺序（逆时针方向），但我没有关于四边形的更多信息。我对他们的关系或邻接一无所知。

由于我想使用核心配置文件上下文进行渲染，因此无法使用GL_QUAD原始类型。我必须将四边形转换为三角形。

当然，四边形索引数组可以轻松转换为三角形索引数组：

std::vector<unsigned int> triangles;
triangles.reserve( no_of_indices * 6 / 4 );
for ( int i = 0; i < no_of_indices; i += 4 )
{
    int tri[] = { quad[i], quad[i+1], quad[i+2], quad[i], quad[i+2], quad[i+3] };
    triangles.insert(triangles.end(), tri, tri+6 );
}

如果只需要完成一次，那么这就是解决方案。但是网格数据不是静态的。数据可以动态变化。数据并不是每次都连续变化，而是不可预测地随机变化。

另一个简单的解决方案是创建一个顶点数组对象，它直接引用带有四边形的元素数组缓冲区，并使用GL_TRIANGLE_FAN原始类型在循环中绘制它们：

for ( int i = 0; i < no_of_indices; i += 4 ) …

我目前正在 Godot 中开发一个游戏，该游戏涉及渲染地球上的国家/地区。我之前对 Godot 的经验很少，但过去曾尝试过。

我将来自 Natural Earth 的这些数据用于国家边界，并成功地使用线网格将其显示在地球上。数据最初是 shapefile 格式，但我使用mapshaper.org将其转换为 GeoJSON 。

图片

数据基本上归结为以纬度和经度给出的点列表，然后我将其转换为 3d 点并使用 SurfaceTool 创建网格。

但是，我无法为网格生成实际表面。首先，我无法找到一个内置函数来根据这些数据生成三角形网格。我研究了许多解决方案，包括使用内置的 Mesh.PRIMITIVE_TRIANGLE_FAN 格式，该格式不适用于凹面形状。

我研究了三角剖分算法，例如 delaunay 三角剖分，但在实现它们方面收效甚微。

我目前的计划是使用二维数据（x，y = 经度，纬度）生成一个三角形网格，并将其投影到球体表面。为了产生曲面，我将在网格中包含球体本身的顶点（示例）。

我想知道如何根据这些数据构建三角形网格。本质上，我需要一个可以做以下事情的算法：

1. 从凹多边形（国家边界）创建三角形网格
2. 将网格连接到此多边形内的一系列点
3. 允许多边形内的孔（用于湖泊等）

这是我正在寻找的结果示例。

再说一次，我对戈多很陌生，我可能把事情复杂化了。如果有更简单的方法来渲染地球上的国家/地区，请告诉我。

这是我当前的代码：

extends Node

export var radius = 1
export var path = "res://data/countries.json"

func coords(uv):
    return (uv - Vector2(0.5, 0.5)) * 360

func uv(coords):
    return (coords / 360) + Vector2(0.5, 0.5)

func sphere(coords, r):
    var angles = coords / …