天道酬勤,学无止境

CGAL:二维约束 Delaunay 三角剖分 - 向约束添加信息(CGAL: 2D Constrained Delaunay Triangulation - Adding information to constraints)

问题

可以将信息(如整数)附加到点,然后再将它们添加到三角仪对象。 我这样做是因为我一方面需要一个 int 标志,我稍后使用它来定义我的纹理坐标,另一方面我需要一个索引,以便我可以创建一个索引的 VBO。 http://doc.cgal.org/latest/Triangulation_2/Triangulation_2_2info_insert_with_pair_iterator_2_8cpp-example.html

但是我只想插入约束边缘而不是点。 如果我插入两个 CGAL 会返回奇怪的结果,因为点已被输入两次(一次作为点,一次作为受约束边缘的点)。 http://doc.cgal.org/latest/Triangulation_2/Triangulation_2_2constrained_8cpp-example.html

是否可以以与点信息相同的方式连接到“约束”,以便我只能使用此函数cdt.insert_constraint( Point(j,0), Point(j,6)); 在我迭代结果面之前?

后来当我遍历三角形时,我需要某种方式来访问我之前定义的 int 标志。 像这样,但不是在顶点上,而是在由约束边缘定义的线段的“末端”上:

for(CDT::Finite_faces_iterator fit = m_cdt.finite_faces_begin(); fit != m_cdt.finite_faces_end(); ++fit, ++k) {

    int j = k*3;
    for(int i=0; i < 3; i++) {

        indices[j+i] = fit->vertex(i)->info().first;
    }
}

这个问题是我在这里发布的另一个问题的一部分:Constrained (Delaunay) Triangulation。 由于这是它自己的问题,我第二次独立发布了它。

回答1

问题的作者为自己找到了解决方案,但没有发布答案。 所以,我会做到的。


答案位于官方网站上的那些示例和解释中。

将描述当您只需要Point自定义类时的情况。

获取 MyPointC2 的源代码并修改/添加您需要的内容。

#ifndef MY_POINTC2_H
#define MY_POINTC2_H
#include <CGAL/Origin.h>

class Point_i2 {
private:
  double vec[2];
  int ind;
public:
  Point_i2() : ind(0)
  {
    *vec = 0;
    *(vec+1) = 0;
  }
  Point_i2(const double x, const double y, int i = 0) : ind(i)
  {
    *vec = x;
    *(vec+1) = y;
  }
  const double& x() const  { return *vec; }
  const double& y() const { return *(vec+1); }
  double & x() { return *vec; }
  double& y() { return *(vec+1); }
  int index() const { return ind; }
  int& index() { return ind; }
  bool operator==(const Point_i2 &p) const
  {
    return ( *vec == *(p.vec) )  && ( *(vec+1) == *(p.vec + 1) && ( ind == p.ind) );
  }
  bool operator!=(const Point_i2 &p) const
  {
      return !(*this == p);
  }
};
#endif // MY_POINTC2_H

然后创建新内核:

#ifndef MYKERNEL_H
#define MYKERNEL_H
#include <CGAL/Cartesian.h>
#include "Point_i2.h"

// K_ is the new kernel, and K_Base is the old kernel
template < typename K_, typename K_Base >
class MyCartesian_base
  : public K_Base::template Base<K_>::Type
{
  typedef typename K_Base::template Base<K_>::Type   OldK;
public:
  typedef K_                                Kernel;
  typedef Point_i2                         Point_2;

  template < typename Kernel2 >
  struct Base { typedef MyCartesian_base<Kernel2, K_Base>  Type; };
};
template < typename FT_ >
struct MyKernel
  : public CGAL::Type_equality_wrapper<
                MyCartesian_base<MyKernel<FT_>, CGAL::Cartesian<FT_> >,
                MyKernel<FT_> >
{};

现在我们可以使用我们的新内核而不是默认内核:

typedef MyKernel<double>                   MK;
typedef CGAL::Filtered_kernel_adaptor<MK>  K;

受限制的 HTML

  • 允许的HTML标签:<a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • 自动断行和分段。
  • 网页和电子邮件地址自动转换为链接。

相关推荐
  • CGAL - 约束德劳内三角剖分中的自定义二维点和交点行为(CGAL - custom 2D point and intersection behavior in constrained delaunay triangulation)
    问题 简而言之,我必须从一组带有附加信息的 2D 点生成一个受约束的 delaunay 三角剖分。 由于可能存在交叉约束,我需要三角测量在生成新的交叉点时正确插入卫星数据。 我尝试使用 CGAL (C++) 按照此处的示例定义自定义内核,但我未能成功编译它,主要是因为我缺少 CGAL 的底层通用编程机制的一些基础知识(很多类型不匹配等等。)。 您能否指出一个工作示例,该示例使用在约束交叉点(或至少类似的东西)正确插值的卫星数据扩展点? 理论上,我可以使用带有信息的顶点,但随后我需要一些回调机制来让我处理交集(我实际上通过修改 cgal 源代码以一种肮脏的方式做到了这一点)。 无论如何,我正在寻找一种“cgal 方式”来实现我刚刚讨论的内容。
  • 球形空间约束的Delaunay三角剖分[关闭](Spherical space constrained delaunay triangulation [closed])
    问题 关闭。 此问题不符合堆栈溢出准则。 它当前不接受答案。 想要改善这个问题吗? 更新问题,使它成为Stack Overflow的主题。 3年前关闭。 改善这个问题 为了在球体上实现高性能动态寻路算法(在C ++中),我对在球体表面执行增量约束Delaunay三角剖分感兴趣。 现有的库似乎还不够用-到目前为止,我能找到的最接近的库是CGAL,它的拓扑空间正确,而度量空间错误。 该库应具有: 合理的性能(我有大约10万个积分) 球形拓扑和度量空间(老实说,此规则大范围推翻了#1) 增量点插入和删除(供以后的算法使用) 目前,我唯一的真实选择似乎是近似的(通过在2D欧式度量空间上进行投影,并在Delaunay保证提供的折衷方案中进行权衡)或编写我自己的选择,其中包括所有麻烦。 球形度量空间中是否存在用于约束Delaunay三角剖分的库? 回答1 由于现在已将其标记为脱机主题(由于垃圾邮件?),所以我也至少给出一个全面的答案。 据我所知-截至2017年7月-有两种方法可以计算球体上点的约束Delaunay三角剖分。 第一个是libdts2(1)。 它基于CGAL 2D delaunay三角剖分算法,并使用完全在球面上的有理点。 不在球面上的点将捕捉到恰好在球面上的近似有理点(2)。 它的缺点是总是使用4个辅助点,这些辅助点始终是三角剖分的一部分。 也不可能插入非常接近北极的任何点。
  • 从具有x,y和z坐标的点生成网格(Mesh generation from points with x, y and z coordinates)
    问题 问题:从3D点(带有x,y和z坐标)生成网格。 我所拥有的是3D空间中的点(带有x,y和z坐标),您可以在图1中看到它。 输出的是图像2或图像3或图像4。简而言之,它将是网格。 如果我有网孔,可以提供上面的材料。 我见过很多人说Delaunay三角剖分或约束Delaunay三角剖分将有助于我进行网格生成,但是我最发现的是它在2D点(只有x和Y坐标)中的实现。 但是我的问题是:从图像1中可以看出,我在3D中有一些要点。 Delaunay三角剖分或约束Delaunay三角剖分是否可以与3D点一起使用? 如果是,那怎么办? 还是我必须找到另一种用于从3D点生成网格的算法? 注意:有关2D点的Delaunay三角剖分的一种很好的解释可以在这里找到 回答1 这是网格生成及其相关工作的其他一些良好链接。 • TetGen:高质量的四面体网格生成器http://wias-berlin.de/software/tetgen/ • CGal-计算几何算法库http://www.cgal.org/。 http://www.cgal.org/Manual/latest/doc_html/cgal_manual/packages.html#Pkg:Triangulation3。 http://www.cgal.org/Manual/latest/doc_html/cgal_manual
  • 如何将多边形转换为非重叠三角形上的一组?(How to convert a polygon to a set on non-overlapping triangles?)
    问题 我有一个形成闭合多边形的二维点坐标集。 我需要生成一组完全分布多边形的 2D 三角形。 除了三角形应完全填充多边形区域外,没有任何约束。 如果它是我可以实现的标准算法,那就更有帮助了。 回答1 如上所述,Delaunay 三角剖分是用于此任务的相当复杂的算法。 如果您接受 O(n^2) 运行时间,则可以尝试更易于理解和编码的 Ear Clipping 算法。 基本思想如下。 每个具有 >= 4 个顶点且没有孔的多边形(即其边界是一条没有自相交和自相切的单条折线)至少有一个“耳朵”。 耳朵是三个连续的顶点,因此建立在它们上的三角形位于多边形内部并且不包含多边形内部的其他点。 如果您“切耳朵”(在答案中添加一个三角形并替换删除这三个点的中点),您将任务减少为顶点较少的多边形,依此类推。 耳朵可能在 O(n^2) 中很容易(根据定义)找到,导致 O(n^3) 三角剖分算法。 有 O(n) 寻耳算法,虽然它不是很复杂,但用几句话来描述它是相当长的。 此外,如果您需要更快的算法,您应该查看有关单调多边形三角剖分和将多边形拆分为单调多边形的内容。 甚至存在线性时间三角剖分算法,但它与 Delaunay 三角剖分一样复杂。 您可以考虑维基百科文章,并在那里查看现有方法的小概述。 回答2 对一般多边形进行三角剖分的最佳方法是计算受约束的 Delaunay 三角剖分 - 这是多边形顶点的标准
  • C++ 2D 曲面细分库?(C++ 2D tessellation library?)
    问题 我有一些凸多边形存储为点的 STL 向量(或多或少)。 我想很快地将它们镶嵌,最好是大小相当均匀的块,并且没有“条子”。 我将用它把一些物体炸成小块。 有谁知道一个很好的库来细分多边形(将它们分成较小的凸多边形或三角形的网格)? 我已经看过一些我已经在网上找到的,但我什至无法编译它们。 这些学术类型不太重视易用性。 回答1 CGAL 有包来解决这个问题。 最好的方法可能是使用 2D Polygon Partitioning 包。 例如,您可以生成多边形的 y 单调分区(也适用于非凸多边形),您将得到如下结果: 运行时间为 O(n log n)。 在易用性方面,这是一个生成随机多边形并对其进行分区的小示例代码(基于此手动示例): typedef CGAL::Exact_predicates_inexact_constructions_kernel K; typedef CGAL::Partition_traits_2<K> Traits; typedef Traits::Point_2 Point_2; typedef Traits::Polygon_2 Polygon_2; typedef std::list<Polygon_2> Polygon_list; typedef CGAL::Creator_uniform_2<int, Point_2> Creator
  • 轻量级Delaunay三角剖分库(用于C ++)(Lightweight Delaunay trianguation library (for c++) [closed])
    问题 关闭。 此问题不符合堆栈溢出准则。 它当前不接受答案。 想要改善这个问题吗? 更新问题,使它成为Stack Overflow的主题。 3年前关闭。 改善这个问题 我想研究一些(2D)Delaunay三角剖分,并且正在寻找一个可以使用的较小的库。 我知道CGAL,但是我想知道那里是否有相当简单明了的东西。 我想做的事情: 创建任意点的三角剖分找到任意点所在的三角形,并获取顶点创建三角剖分的图像(可选) 有什么建议吗? 回答1 您可能应该详细说明您的目标,以便提供更多相关的答案,但让我首先介绍一下Triangle(二维Delaunay生成工具),它是用C编写的,可以用作独立程序,也可以从中调用您自己的代码。 然后,关于CGAL,这是一个典型的小示例,以防万一您仍然考虑它: #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
  • CGAL 中使用任意平面的 2D Delaunay 三角剖分(2D Delaunay triangulation in CGAL using an arbitrary plane)
    问题 我是使用 CGAL 的新手,我想知道 CGAL 是否支持使用任意平面对 3D 点进行 2D Delaunay 三角剖分。 CGAL 文档中的示例仅列出Projection_traits_xy_3<R> 、 Projection_traits_yz_3<R>和Projection_traits_xz_3<R> ,换句话说,在 xy 平面、yz 平面和 xz 平面上的投影。 有什么方法可以定义任意投影平面而不是使用 xy、yz 和 xz 平面? 谢谢, 回答1 有一个template < class Kernel > class Triangulation_2_projection_traits_3没有记录并且在标题中定义: CGAL/Triangulation_2_projection_traits_3.h 。 您从平面法线构造特征类并将特征传递给三角剖分。 像下面这样的东西应该工作: typedef CGAL::Exact_predicates_inexact_constructions_kernel K; typedef CGAL::Triangulation_2_projection_traits_3<K> P_traits; typedef CGAL::Delaunay_triangulation_2< P_traits > DT2; std::vector< K
  • CGAL-在Delaunay三角剖分之后检索顶点索引(CGAL - Retrieve Vertex Index After Delaunay Triangulation)
    问题 我正在计算几千个点的2D delaunay三角剖分。 除了x和y坐标外,每个点还有更多与之关联的数据。 因此,我想知道是否有可能检索每个点的索引,以便可以在另一个向量中访问自己的点结构。 当前,当我从Face_handle访问顶点时,它返回一个点(即x,y坐标)。如何通过其ID(索引)而不是其x,y坐标返回每个顶点? 谢谢你。 #include <vector> #include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/Delaunay_triangulation_2.h> typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel; typedef CGAL::Delaunay_triangulation_2<Kernel> Delaunay; typedef Kernel::Point_2 Point; void example() { std::vector<Point> points; points.push_back(Point(1,1)); //index 0 points.push_back(Point(1,2)); //index 1 points.push_back(Point(1,3)
  • CGAL各模块介绍
    文章目录 前言算术与代数Arithmetic and Algebra组合算法Combinatorial Algorithms几何核Geometry Kernels凸包算法Convex Hull Algorithms多边形Polygons细胞复合物和多面体Cell Complexes and Polyhedra排列Arrangements三角剖分和Delaunay三角剖分Voronoi图网格生成Mesh Generation形状重建Shape Reconstruction几何加工Geometry Processing空间搜索和排序Spatial Searching and Sorting几何优化Geometric Optimization插补Interpolation 前言 记录下,方便查阅。官方文档地址:https://doc.cgal.org/latest/Manual/packages.html 算术与代数Arithmetic and Algebra 主要提供了计算几何用到的数学基础:数据类型、多项式、数据结构与算法。 组合算法Combinatorial Algorithms 主要讲述计算几何用到的数学基础:矩阵搜索、线性和二次规划求解器。 几何核Geometry Kernels 主要讲述计算几何中如何表达几何模型。 凸包算法Convex Hull Algorithms
  • 带孔的多边形三角剖分(Polygon Triangulation with Holes)
    问题 我正在寻找一种算法或库(更好)来将多边形分解成三角形。 我将在Direct3D应用程序中使用这些三角形。 最佳的选择是什么? 到目前为止,这是我发现的内容: 本·迪索(Ben Discoe)的笔记 FIST:多边形的快速工业强度三角剖分我知道CGAL提供了三角剖分功能,但不确定是否支持孔。 我真的很感激那些在这方面有经验的人的一些意见。 编辑:这是一个2D多边形。 回答1 乔纳森·肖丘克(Jonathan Shewchuk)的Triangle库非常出色。 过去,我曾用它来自动进行三角剖分。 您可以要求它避免出现小/窄三角形等,因此您会想到“良好”的三角剖分,而不仅仅是任何三角剖分。 回答2 为您提供更多的库选择: 多布尔。 我从没有尝试过,但是看起来很有希望:http://www.complex-a5.ru/polyboolean/index.html 通用多边形剪。 这在实践中效果很好,可以进行三角剖分以及修剪和打洞:http://www.cs.man.ac.uk/~toby/alan/software/ 我个人的建议:使用GLU(OpenGL实用程序库)中的镶嵌。 该代码坚如磐石,比GPC更快,并且生成的三角形更少。 您不需要初始化的OpenGL-Handle或类似的东西就可以使用lib。 如果您不喜欢在DirectX应用程序中包含OpenGL系统库的想法
  • Delaunay三角剖分和最大内切圆的混淆(Confusion on Delaunay Triangulation and Largest inscribed circle)
    问题 我需要找到一个凸多边形的最大内切圆,已经搜索了许多站点,并且可以通过使用Delaunay三角剖分来实现。 我在使用CGAL的算法的CGAL讨论中找到了一个线程: 您可以使用CGAL轻松计算得出: 首先,计算点的Delaunay三角剖分。 然后,在三角剖分的所有有限面上进行迭代。 对于每个有限的面f 计算其外接心c 在三角剖分中定位c(为了加快处理速度,您可以给f的一个顶点作为该点位置的起始提示) 如果由locate(c,hint)返回的面是有限的,则外接中心c位于点的凸包中,因此,f为候选如果f是这样的候选人脸,请计算其平方外接半径,仅保留具有最小平方外接半径的人脸 CGAL手册(第2章三角剖分,以及内核中的一些内容)展示了执行此操作的每个基本功能。 我对该算法的最后部分有些困惑。 当我阅读它时,我从中了解到的是,三角剖分面的最小外圆是最大内切圆的半径。 但是从带Delaunay三角剖分的多边形的例子中,似乎即使最小的外接圆有时也无法容纳在多边形内部,那么它怎么能与最大的内切圆具有相同的半径呢? 回答1 多边形中的最大内切圆。 多边形最大内切圆问题的经典计算几何解决方案是使用多边形面的广义 Voronoi 图。 多边形的中间轴。 这种方法适用于更通用的设置,例如带有孔的多边形,请参见此stackoverflow对类似问题的答案。 凸输入。 但是
  • 填充/缩小(偏移,缓冲)多边形的算法(An algorithm for inflating/deflating (offsetting, buffering) polygons)
    问题 我将如何“充气”一个多边形? 也就是说,我想做类似的事情: 要求是新的(膨胀的)多边形的边/点都与旧的(原始)多边形的边/点都具有相同的恒定距离(在示例图片中,它们不是,因为从那以后,它必须使用圆弧作为膨胀的顶点,但是让我们暂时忘记这一点;))。 我要寻找的数学术语实际上是向内/向外多边形偏移。 +1表示要指出这一点。 另一种命名方式是多边形缓冲。 搜索结果: 以下是一些链接: 多边形偏移策略研究多边形偏移,问题缓冲多边形数据 回答1 我以为我可能会简要提及我自己的多边形裁剪和偏移库-Clipper。 虽然Clipper主要是为多边形裁剪操作而设计的,但它也可以进行多边形偏移。 该库是用Delphi,C ++和C#编写的开源免费软件。 它具有非常宽松的Boost许可证,允许免费使用在免费软件和商业应用程序中。 可以使用以下三种偏移样式之一执行多边形偏移:正方形,圆形和斜切。 回答2 您要查找的多边形在计算几何中称为向内/向外偏移多边形,它与直线骨架紧密相关。 这些是复杂多边形的多个偏移多边形: 这是另一个多边形的笔直骨架: 正如其他注释中所指出的那样,取决于您计划对多边形进行“充气/放气”的距离,最终可以为输出提供不同的连接性。 从计算的角度来看:一旦有了笔直的骨架,就应该能够相对容易地构造偏移多边形。 开源CGAL库(非商业性免费)具有实现这些结构的程序包。
  • 在图中找到最近的边(Find nearest edge in graph)
    问题 我想在图中找到最近的边。 考虑以下示例: 图 1:黄色:顶点,黑色:边缘,蓝色:查询点 一般信息:该图包含大约1000 万个顶点和大约1500 万条边。 每个顶点都有坐标。 边由两个相邻的顶点定义。 最简单的解决方案:我可以简单地计算从查询点到图中所有其他边的距离,但这会非常慢。 思路与难点:我的想法是使用一些空间索引来加速查询。 我已经实现了一个 kd-tree 来找到最近的顶点。 但如图 1 所示,与最近顶点相关的边不一定是离查询点最近的边。 我会得到边缘3-4而不是更近的边缘7-8 。 问题:有没有找到图中最近边的算法? 回答1 一个非常简单的解决方案(但可能不是复杂性最低的解决方案)是根据边界框为所有边使用四叉树。 然后,您只需提取最接近查询点的边集并迭代它们以找到最近的边。 四叉树返回的提取边集应该比原始的 1500 万条边小很多倍,因此迭代成本要低得多。 四叉树是比 R 树更简单的数据结构。 它相当普遍,应该在许多环境中都可以使用。 例如,在 Java 中,JTS Topology Suite 有一个结构QuadTree ,可以轻松地将其包装起来以执行此任务。 回答2 存在适用于除点以外的其他类型数据的空间查询结构。 最通用的是“R 树”结构(及其许多变体),它允许您存储线段的边界矩形。 然后,您可以从查询点向外搜索,检查边界矩形中的线段
  • 一个蛮力约束的 Delaunay 三角剖分?(A Brute-Force Constrained Delaunay Triangulation?)
    问题 我需要从一组点创建一个三角形网格。 该集合的点数很少,因此不需要快速或优化(我最多会处理 100 点)。 网格需要是受约束的“delaunay 三角剖分”。 在下图中,我(在左侧)显示了我从(蓝点和红点)开始的一组点。 我也知道这些点之间的联系(黑色轮廓)。 网格需要看起来像右边的例子(包括形成外部和内部三角形的灰色边缘)。 我不能使用图书馆。 我研究了许多不同的算法。 它们很多,很容易混淆。 我想知道是否有一个简单的算法,因此我可以使用更简单的算法来生成右侧的网格? 蛮力方法很好(ps:我可以做一个 Delaunay 三角剖分)。 回答1 感谢所有的答案。 我经历了开发这个问题的解决方案的过程,所以我想分享我自己的经验,希望遇到问题的人会发现这些见解有用。 因此,根据我自己实现算法的经验,我得出了以下结论: 没有真正快速的方法来解决这个问题。 认为仅用 50 行代码就可以实现是不合理的。 事实上,我写的例程(C++)大约有 400 到 500 行(很难用注释来判断)。 如此合理紧凑但具有挑战性,我花了 2 到 3 天的时间才能使逻辑正确(这可能很棘手)。 我发现 Sloan 在“A FAST ALGORITHM FOR GENERATING CONSTRAINED DELAUNAY TRIANGULATIONS”中提出的算法非常适合手头的问题。 Delaunay
  • 加权 Voronoi 的 CGAL 2D APOLLONIUS 图 - 如何生成和获取面和顶点?(CGAL 2D APOLLONIUS diagram for Weighted Voronoi - How to generate and get the faces and vertices?)
    问题 我正在尝试根据阿波罗尼乌斯图生成加权 voronoi。 我正在使用 CGAL 库。 我找不到如何从 apollonius 获取面和顶点的好例子。 我有以下类型定义: typedef double NT; typedef CGAL::Cartesian< NT> KernelCartes; typedef CGAL::Ray_2<KernelCartes> Cartes_Ray; typedef CGAL::Line_2<KernelCartes> Cartes_Line; typedef CGAL::Segment_2<KernelCartes> Cartes_Segment; typedef std::list<Cartes_Ray> Cartes_RayList; typedef std::list<Cartes_Line> Cartes_LineList; typedef std::list<Cartes_Segment> Cartes_SegmentList; typedef CGAL::Point_2<KernelCartes> Cartes_Point; typedef CGAL::Apollonius_graph_traits_2<KernelCartes> ApoTraits; typedef CGAL::Apollonius_graph_2
  • Delaunay 三角剖分中的矩形约束,其中没有边(Rectangular constraints in Delaunay Triangulation without edges within)
    问题 我正在使用三角剖分库来计算某个大边界内的一组矩形的约束德劳内三角剖分。 该算法返回所有边,但还在定义约束的矩形内添加边。 我希望能够创建一个图形,在任何约束矩形内没有边(当然大边界除外),但是在给我的三角剖分中删除这些边需要比 O(nlog (n)) 至少时间,这不符合我的需要。 我要问的是,有没有什么快速的方法可以让 CDT 防止边缘出现在某个多边形内? 我希望矩形没有边缘,但我不知道如何快速做到这一点。 如果这有帮助,我使用的库是 Marcello Kallmann 的 TriPath,它是用 C++ 编写的(http://graphics.ucmerced.edu/software/tripath/)。 我的应用程序是 Java 的,我使用的是 JNI。 编辑:根据要求,这里有一些图像可以帮助您形象化我要描述的内容。 这个 CDT 是用黑线作为约束构建的。 如您所见,每个受约束的边都是矩形的一部分。 蓝线是不受约束的 Delaunay 边。 我试图从黑色约束矩形内删除任何蓝色无约束德劳内边缘。 回答1 如果受约束的矩形不能重叠或相互包含,我建议在每个原始矩形内放置一个稍小的矩形。 内部矩形和原始矩形之间的间隙应该足够小,以至于在不与较小矩形相交的情况下,任何不受约束的边都可能适合原始矩形。 然后,在三角剖分完成后,删除与这些较小矩形的任何顶点相邻的每条边。
  • 一种线性时间算法,用于查找从其他顶点可见的多边形的任何顶点(A linear-time algorithm to find any vertex of a polygon visible from other vertex)
    问题 假设有一个由n个顶点定义的没有孔和自相交的多边形(即一个简单的多边形)。 选择此多边形的反射顶点v 。 我想找到同一个多边形的任何其他顶点u ,它从顶点v是“可见的”。 可见,我的意思是, v和u之间的线段完全位于多边形内部。 有没有一种算法可以在O(N)时间或更好的时间内做到这一点? 是否有一种算法可以在O(N)时间内找到所有可见顶点? 一项快速研究表明,对于给定的多边形和该多边形内的任何点,都可以在O(N)构建可见性多边形。 我认为找到单个可见顶点应该更容易。 回答1 这个问题在 30 年前就已经解决了: ElGindy和阿维斯,“A线性算法,用于计算从一个点的可视性多边形”,J.算法2,1981年,第 186--197。 Joe & Simpson 在 1985 年发表了一篇非常好的论文,“从一个点看一个简单多边形的可见性”,它提供了经过仔细验证的伪代码:(PDF 下载链接)。 这肯定已经在许多语言中实现了很多次。 例如,维基百科文章中有一个关于该主题的链接。 回答2 我修改了算法,因为它不正确。 我希望这次它涵盖了所有情况!。 从反射a开始,让a'下一个顶点并跟随多边形,直到找到一条与a--a'相交的边a' ,让b此边与线a--a的交点'和c边缘的端点( a--c右侧的那个)。 现在继续穿过多边形的边,如果一条边从左到右穿过a--b段,则将b设置为新的交点
  • 多边形操作库[关闭](Library for polygon operations [closed])
    问题 关闭。 此问题不符合 Stack Overflow 准则。 它目前不接受答案。 想改善这个问题吗? 更新问题,使其成为 Stack Overflow 的主题。 7年前关闭。 改进这个问题 我最近遇到需要一个库或一组库来处理 2D 多边形的操作。 我需要能够执行布尔/裁剪操作(差和并)和三角剖分。 到目前为止,我发现的库是 poly2tri、CGAL 和 GPC。 Poly2tri 看起来很适合三角剖分,但我仍然使用布尔运算,而且我不确定它的成熟度。 只有我自己的项目是免费的,CGAL 和 GPC 才免费。 我的特定项目不是商业性的,所以我对支付或请求任何许可证犹豫不决。 但我可能想将我的代码用于未来的商业项目,所以我对 CGAL 的开源许可证和 GPC 的仅限免费软件的限制犹豫不决。 似乎没有任何具有良好 BSD 风格许可证的多边形裁剪库。 哦,C/C++ 是首选。 回答1 Clipper 是一个开源免费软件多边形裁剪库(用 Delphi 和 C++ 编写)^ 完全符合您的要求(三角剖分除外)- http://sourceforge.net/projects/polyclipping/ 在我的测试中,Clipper 比 GPC 快得多,而且更不容易出错(请参阅此处的更详细比较 - http://www.angusj.com/delphi/clipper.php
  • CGAL 2D Delaunay Triangulation: How to get edges as vertex id pairs
    I have a set of 2D points each with an associated id. (e.g. if the points are stored in an array, the id is the index into each point 0,....,n-1 ). Now I create a Delaunay triangulation of these points and want to list down all the finite edges. For each edge, I would like to have the ids of the points represented by corresponding 2 vertices. Example: if there's an edge between point 0 and point 2 then (0,2). Is this possible? #include <vector> #include <CGAL\Exact_predicates_inexact_constructions_kernel.h> #include <CGAL\Delaunay_triangulation_2.h> typedef CGAL::Exact_predicates_inexact
  • CGAL - custom 2D point and intersection behavior in constrained delaunay triangulation
    In short, I have to generate a constrained delaunay triangulation from a set of 2D points that carry additional information. Since there could be intersecting constraints, I need that the triangulation properly interpolates the satellite data whenever it generates the new point of intersection. I tried with CGAL (C++) to define a custom kernel following the example here, but I've failed to compile it succesfully, basically because there is something fundamental of the underlying generic programming machinery of CGAL that I am missing (lot of type mismatches etc.). Can you point me to a working