GuoFan

系列文章 -> A算法初探究及优化 - 自动解贪吃蛇 A算法深入探究 - 使用Qt和C++实现带权重版本的A* A算法扩展 - 三维A 说起来，贪吃蛇游戏好像贯穿了我的编程学习之路。 大一时候，用单片机点亮了一个8x8的LED阵列，配合上下左右四个按键，在C51平台写了自己所理解的贪吃蛇版本。以至于大二当上了光协技术部部长时也把“调通我提供的贪吃蛇框架代码、自己再实现部分特殊功能”作为学校电子竞赛软件类的题目用来“迫害”学弟学妹们。 之后参加电赛，暑假准备期间，为了让到正式比赛时我们的作品能有很好的界面以及交互，开始调一块4.7寸的电容屏，在STM32平台上编写自己的图形框架。框架编写得很顺利，所以开始写程序玩，又想到了贪吃蛇！可是现在只有触屏，要是照着手机的策略，加上虚拟按键搓屏幕，总觉得不够优雅。要不让贪吃蛇自己动起来吧！想了一些方案，当时也还不知道有A*算法，用DFS写出了自己的第一个自动贪吃蛇版本。角色互换，玩家通过触屏控制食物的生成，计算机来控制蛇寻找食物并吃掉。 学习python的过程中，接触到了pygame，又把之前在MCU的自动贪吃蛇用python实现了 ...

系列文章 -> GAMES101笔记 - Resterization（光栅化） GAMES101笔记 - Shading（着色） GAMES101笔记 - Geometry（几何） 20年的时候，好朋友推荐了这个课程给我，简直是神仙课程！当时每天下班后就再花一个多小时来听一节课，陆陆续续听完了。最近打算重温一下这系列课程，顺便补上笔记。 图形学有一种魔力，每次学图形学相关的知识的时候，总在感叹其美妙。第一次系统地学习图形学是在大三，当时智能车已经进入了平稳的调试期，所以找了一些囤积起来的一直想学的技术书籍开始学习：Golang、图形学、Unity3D等等。 学到图形学的时候，正好智能车这边在调试利用陀螺仪对坡道的识别，所以突发奇想：在屏幕上显示一个3D图形，然后把陀螺仪解算出来的姿态实时绑定到3D图形上面，会比单纯地看上位机展示出来的陀螺仪数据曲线要来的直观很多吧！于是有了这个玩意： 线代知识点回顾 向量 a⃗=(xa,ya,za)Tb⃗=(xb,yb,zb)T\begin{aligned} \vec{a} &= (x_a, y_a, z_a)^T \\ \vec ...

准备工作 vscode：官方网站 插件：vscode 中搜索插件 PlantUML 并进行安装，需要注意的是，如果使用 ssh 远程编辑，则还需在 remote 端安装此插件 graphviz：由于 PlantUML 是在 graphviz 基础上运行的，所以需要下载并安装 graphviz（下载页面）。如果不想本地安装，也有在线网页进行图形输出。 java环境：graphviz 的运行需要 java 环境，下载java。或者 linux 环境下直接 sudo apt install openjdk-17-jdk。 开始编辑 PlantUML 语法见官方手册 在任意一个文档（推荐新建后缀为.puml的文件）中输入 PlantUML 的代码，使用快捷键Alt+D（Macos 下可能是 Opt+D）即可实时预览自动排版的 UML 图。 效果如下（左边是代码，按了快捷键后自动分出右边窗口用来同步显示）： 常用技巧 分析类图 例如利用如下代码： 12345678910111213141516171819@startuml 分析类图boundary boundary_1control co ...

系列文章 《计算几何——算法与应用（第三版）》学习笔记1 - 扫描线（第1-4章） 《计算几何——算法与应用（第三版）》学习笔记2 - 空间索引（第5-7章） 番外篇 计算几何 - C++ 库的调研 Boost C++ Libraries学习 - Geometry -> Boost C++ Libraries学习 - Boost.Polygon (GTL) 参考 Boost 官方手册 The Boost.Polygon library provides algorithms focused on manipulating planar polygon geometry data. Specific algorithms provided are the polygon set operations (intersection, union, difference, disjoint-union) and related algorithms such as polygon connectivity graph extraction, offsetting and map-o ...

一般线性规划问题的数学模型 问题的提出 生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是所谓线性规划问题。 问题提法千千万，总结起来都是：给定一定量的资源或任务，通过一种最优化的方案分配资源或任务，使得获得效益最大或者消耗资源最少。这时我们会有一个优化目标，以及其约束于（subject to, 或简写为 s.t.）的约束条件。 线性规划问题的数学模型 线性规划问题的数学模型包含三个组成要素： 决策变量：指决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。 目标函数：指问题要达到的目的要求，表示为决策变量的函数。 约束条件：指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。 如果在规划问题的数学模型中，决策变量为可控的连续变量，目标函数和约束条件都是线性的，这类模型称为线性规划问题的数学模型。一般写成如下形式： max(或min)z=CXmax(\text{或} min) z = CX max(或min)z=CX s.t.{AX≤(或=,≥)bX≥0s.t. \begin{cases} AX \ ...

系列文章 《计算几何——算法与应用（第三版）》学习笔记1 - 扫描线（第1-4章） -> 《计算几何——算法与应用（第三版）》学习笔记2 - 空间索引（第5-7章） 番外篇 计算几何 - C++ 库的调研 Boost C++ Libraries学习 - Geometry Boost C++ Libraries学习 - Boost.Polygon (GTL) 正交区域查找：数据库查询 将数据库中的每条记录对应到多维空间中的一个点，这样就可以将本来针对记录的查询变成针对点的查询。例如下图，把“yyyymmdd”格式的日期作为 x 坐标，把“月收入”作为 z 坐标，把“家庭成员数量”作为 y 坐标，图中的立方体就可以作为“查询出生于 1950 年至 1955 年之间、月收入在 $3000 至 $4000 之间并且家庭成员有 2 到 4 人的所有员工”的几何化表示。 有了这种表示，接下来要解决的问题是如何找到落在这个立方体中的点。在计算几何中，这类查询被称为矩形区域查询（rectangular range query），或者正交区域查找（orthogonal range query） ...

系列文章 GAMES101笔记 - Resterization（光栅化） GAMES101笔记 - Shading（着色） -> GAMES101笔记 - Geometry（几何） Ways to Represent Geometry 隐式（Implicit）几何 通过描述点之间的关系来确定几何。例如单位球的隐式表示：x2+y2+z2=1x^2+y^2+z^2=1x2+y2+z2=1。 定义函数f(x,y,z)=0f(x,y,z)=0f(x,y,z)=0，在隐式几何表示中，只要找到点满足该函数，则说明该点在几何上。 缺点：难以描述复杂形状。 优点： 容易表述。 容易查询（内/外、点到表面的距离）。 容易做光线求交。 对简单形状友好，没有走样。 容易处理拓扑变化。 表示方式： Algebraic Surfaces（代数表示）。 Constructive Solid Geometry (CSG)：将隐式表示的几何通过布尔运算组合起来。 Distance Functions（距离函数）：通过描述空间中任何点到平面的最近距离俩表示几何。 通过 blend 距离函数，可以得到像 ...

系列文章 《计算几何——算法与应用（第三版）》学习笔记1 - 扫描线（第1-4章） 《计算几何——算法与应用（第三版）》学习笔记2 - 空间索引（第5-7章） 番外篇 -> 计算几何 - C++ 库的调研 Boost C++ Libraries学习 - Geometry Boost C++ Libraries学习 - Boost.Polygon (GTL) Boost.Geometry 官方网站 学习笔记：Boost C++ Libraries学习 - Geometry License Distributed under the Boost Software License, Version 1.0. 特点 易于使用，资料多、文档齐全。 常见的几何操作都有，但更小众的需求可能不如 CGAL。 可视化调试 vscode 插件：Graphical Debugging 使用方法：在 Debug 界面会有 GRAPHICAL WATCH 栏（图中左下角），在里面点击“+”号，输入变量名即可，效果如下： 但由于 GDB 和 LLDB 不会输出变量的原始类型（例如使用了typ ...

系列文章 A算法初探究及优化 - 自动解贪吃蛇 A算法深入探究 - 使用Qt和C++实现带权重版本的A* -> A算法扩展 - 三维A 基本思路 本项目是基于这篇文章里面的代码修改的：A*算法深入探究 - 使用Qt和C++实现带权重版本的A* 先将 A* 相关的类修改为维度无关的（Dimension Agnosticism），再实现一份存储三维地图数据的地图结构。由于之前的工作，A* 算法已经与地图类解耦了，所以可以实现用同一份 A* 算法，寻路的维度由地图类决定。 使用模板扩展Node的维度 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960namespace astar {namespace bg = boost::geometry;namespace bgm = boost::geometry::model;enum class NodeStatus{ wild, open, ...

系列文章 《计算几何——算法与应用（第三版）》学习笔记1 - 扫描线（第1-4章） 《计算几何——算法与应用（第三版）》学习笔记2 - 空间索引（第5-7章） 番外篇 计算几何 - C++ 库的调研 -> Boost C++ Libraries学习 - Geometry Boost C++ Libraries学习 - Boost.Polygon (GTL) 参考 Boost 官方手册 Boost.Geometry contains a dimension-agnostic, coordinate-system-agnostic and scalable kernel, based on concepts, meta-function and tag dispatching. On top of that kernel, algorithms are built: area, length, perimeter, centroid, convex hull, intersection (clipping), within (point in polygon), distance ...