原创 ： CGAL的2D Nef多边形布尔操作
CGAL的2D Nef多边形布尔操作
计算机图形学中的2D Boolean Operations on Nef Polygons，通常简称为Boolean Operations on Nef Polygons，是一种在二维空间中对Nef多边形进行布尔运算的方法。Nef多边形是一种特殊的二维多边形，其边界由一系列有序的点组成，且不包含任何内部点。
在计算机图形学中，布尔运算是一种常用的操作，用于对多边形进行合并、交集、差集等操作。通过这些操作，可以在保持图形特征的情况下对图形进行修改和操作。
对于Nef多边形的布尔运算，通常需要遵循一定的步骤和规则。首先，需要确定两个多边形的边界和内部区域。然后，根据需要进行合并、交集或差集等操作。在合并操作中，需要将两个多边形的所有边界点合并为一个新的边界；在交集操作中，需要找到两个多边形公共的边界点并保留下来；在差集操作中，需要将一个多边形从另一个多边形中减去。
在进行布尔运算时，需要注意一些细节和技巧。例如，需要确保边界点的顺序正确，避免出现环路或多边形交叉的情况；需要保证操作的可逆性和可重现性，即多次进行相同操作应该得到相同的结果；需要合理处理边界线的相交和交叉情况，避免出现异常结果。
1、介绍
当处理多边形和多面体集合时，数学模型确定了可以表示的点集类型。Nef多面体是最通用的直线多面体模型。包含在Nef多面体域内的更简单的拓扑模型包括：凸多面体，通常定义为非空有限点集的凸包，凸多面体是紧闭流形集。基本多面体，通常定义为有限个凸多面体的并集。多面体集，通常定义为有限个闭半空间的交集。这样的集合是封闭和凸的，但不一定是紧的。线性多面体，通常定义为简单复形的单纯形的所有点的集合。
平面Nef多面体是可以通过使用集合补和交集操作从有限个开半空间的集合中获得的集合。由于所有其他二元集合操作（如并集、差集和对称差集）都可以简化为交集和补集计算，Nef多面体在这些操作下也是封闭的。除了集合补操作之外，还有更多的拓扑一元集合操作在Nef多面体的域中是封闭的。给定一个Nef多面体，可以确定其内部、边界和闭包，以及像正规化（定义为内部或点集的闭包）这样的组合操作。
2、构造和组成
根据上述定义，数据类型 Nef_polyhedron_2<T> 允许通过所提到的集合操作来构造基本 Nef 多面体以及进行二元和一元组合。可以将类型 Point 和 Line 视为标准二维 CGAL 内核（Point_2<K> 和 Line_2<K>）的模型。
此外，可以从包含简单多边形链的迭代器范围构造 Nef 多面体。Nef 多面体具有输入和输出运算符，允许通过流输出它们并从流中读取它们。目前可以进行图形输出。
3、 研究
通过递归组合二元和一元操作，可以得出一个非常复杂的直线结构。为了探索该结构，有一个数据类型 Nef_polyhedron_2::Explorer，它允许对直线结构进行只读探索。为了理解它的可用性，我们需要更多关于 Nef 多面体表示的知识。
Nef多面体下面的直线结构存储在选择性平面图中。平面图在这里是指一个嵌入有面对象的双向图，使得平面中的每个点都可以唯一地分配给由该图定义的平面细分的对象（顶点、边、面）。选择性是指每个对象（顶点、边、面）都有一个与之关联的布尔值，用于指示集合的包含或排除。
平面图由接口数据类型 Nef_polyhedron_2::Topological_explorer 定义。通过标准仿射点嵌入顶点不足以对半空间和射线状结构的无界性进行建模。因此，平面细分由一个以坐标系原点为中心的轴平行正方形框进行符号化限制。所有延伸到无限大的结构都被该框修剪。线和射线在框上有符号端点。面是圆周闭合的。这里的极小值意味着它的几何延伸总是足够大（但我们的直觉是有限的）。假设您用一个仿射点接近该框，则该点始终在框内。直线也是如此；它们总是与框相交。有更精确的“足够大”的概念，但前面的命题在这一点上已经足够了。由于最小外接矩形包含在平面图中，因此顶点和边都根据该矩形进行划分。
方框内的顶点称为标准顶点，它们由 Explorer::Point 类型的仿射点嵌入。方框上的顶点称为非标准顶点，它们在射线与方框相交的地方嵌入（它们的嵌入由 Explorer::Ray 类型的对象定义）。通过它们的直线嵌入，边缘表示段、射线、线或方框段，具体取决于它们的源和目标顶点的特征。
在探索过程中，可以通过 Nef_polyhedron_2::Explorer 接口追踪长方体对象，该接口从 Nef_polyhedron_2::Topological_explorer 派生而来，并在后者的接口中添加了长方体探索功能。在下面的代码片段中，我们迭代 Nef 多面体的所有顶点，并检查它们的嵌入是仿射点还是极小帧上的点。
通过函数Nef_polyhedron_2::Topological_explorer::mark()，我们可以检查一个面是否是N0的一部分。
通过函数Nef_polyhedron_2::Explorer::is_frame_edge()，我们可以区分“标准”边和infimaximal帧边。
通过函数Nef_polyhedron_2::Explorer::is_standard()，我们可以区分位于infimaximal框架上或内部的顶点，它们在Nef_polyhedron_2::Explorer::ray()所获得的方向上处于无穷远。
可以通过上述五幅图对nef多边形进行理解。
4、特质类
现在，我们终于阐明了类Nef_polyhedron_2的模板参数实际建模的内容。T承载了所谓的扩展几何内核的实现。
目前有三个内核模型：Extended_cartesian<FT>、Extended_homogeneous<RT>和Filtered_extended_homogeneous<RT>。后者是最优的。前两个是对应于简单平面仿射内核的更简单的版本。实际上，它满足（伪代码表示中的类型相等）：
CGAL::Nef_polyhedron_2< CGAL::Extended_cartesian<FT> >::Point == CGAL::Cartesian<FT>::Point_2 CGAL::Nef_polyhedron_2< CGAL::Extended_homogeneous<RT> >::Point == CGAL::Homogeneous<RT>::Point_2 CGAL::Nef_polyhedron_2< CGAL::Filtered_extended_homogeneous<RT> >::Point == CGAL::Homogeneous<RT>::Point_2
类似的方程适用于Nef_polyhedron_2的局部范围内的线类型和方向类型。
5、实施
底层的集合运算是通过用于两个平面图的叠加的高效且完整的算法来实现的。该算法是有效的，因为它的运行时间由输入的大小加上输出的大小乘以对数因子来限制。该算法是完整的，因为它可以处理所有输入，并且不需要一般的位置假设。
主要介绍nef多边形中的定义,重载了很多运算符，这些运算符可以计算nef多边形的交集
https://doc.cgal.org/latest/Nef_2/index.html#Nef_2Construction
关于博主
an actually real engineer
通信工程专业毕业,7年开发经验
技术栈:
精通c/c++
精通golang
熟悉常见的脚本,js,lua,python,php
熟悉电路基础,嵌入式,单片机
耕耘领域:
服务端开发
嵌入式开发
>gin接口代码CURD生成工具
sql ddl to struct and markdown,将sql表自动化生成代码内对应的结构体和markdown表格格式,节省宝贵的时间。
qt .ui文件转css文件
duilib xml 自动生成绑定控件代码
协议调试器
基于lua虚拟机的的协议调试器软件 支持的协议有:
串口
tcp客户端/服务端
udp 组播/udp节点
tcp websocket 客户端/服务端
软件界面
使用例子: 通过脚本来获得接收到的数据并写入文件和展示在界面上
下载地址和源码
webrtc easy demo
webrtc c++ native 库 demo 实现功能:
基于QT
webrtc摄像头/桌面捕获功能
opengl渲染/多播放窗格管理
janus meeting room
下载地址和源码
wifi,蓝牙 - 无线开关
实现功能:
通过wifi/蓝牙实现远程开关电器或者其他电子设备
电路原理图:
实物图:
深度学习验证工具
虚拟示波器
硬件实物图:
实现原理
基本性能
采集频率: 取决于外部adc模块和ebaz4205矿板的以太网接口速率,最高可以达到100M/8 约为12.5MPS
上位机实现功能: 采集,显示波形,存储wave文件。
参数可运行时配置
上位机:
显示缓冲区大小可调
刷新率可调节
触发显示刷新可调节
又一个modbus调试工具
最近混迹物联网企业,发现目前缺少一个简易可用的modbus调试工具,本软件旨在为开发者提供一个简单modbus测试工具。
主打一个代码简单易修改。
特点:
1. 基于QT5
2. 基于libmodbus
3. 三方库完全跨平台,linux/windows。
开源plutosdr 板卡
1. 完全开源
2. 提高固件定制服务
3. 硬件售价450 手焊产量有线
测试数据
内部DDS回环测试
接收测试
外部发送500MHZ FM波形
matlab测试
2TRX版本
大部分plutosdr应用场景都是讲plutosdr板卡作为射频收发器来使用。
实际上plutosdr板卡本身运行linux 操作系统。是具有一定脱机运算的能力。
对于一些微型频谱检测,简单射频信号收发等应用完全可以将应用层直接实现在板卡上
相较于通过网卡或者USB口传输具有更稳定,带宽更高等优点。
本开源板卡由于了SD卡启动,较原版pluto支持了自定义启动应用的功能。
提供了应用层开发SDK(编译器，buildroot文件系统)。
通过usb连接电脑,经过RNDIS驱动可以近似为通过网卡连接
(支持固件的开发定制)。
二次开发例子
```
all:
arm-linux-gnueabihf-gcc -mfloat-abi=hard --sysroot=/root/v0.32_2trx/buildroot/output/staging -std=gnu99 -g -o pluto_stream ad9361-iiostream.c -lpthread -liio -lm -Wall -Wextra -lrt
clean:
rm pluto_stream
版面分析即分析出图片内的具体文件元素,如文档标题,文档内容,文档页码等,本工具基于cnstd模型