MM's Journal of Technology

目标：将多边形剖分成三角形 1、画廊问题 问题描述：在画廊（如下图的多边形）中，如何设置哨兵可以监控整个画廊？ 画廊，其中的点为哨兵 直观解：如果多边形是凸多边形或星形多边形，那么只须在中间的核设置一个即可。如果多边形不规则，那么最多n个点，即n多边形的每个顶点都设置一个哨兵，就可以将整个多边形覆盖。因此问题的解的上界为n. 然而在数学上有证明指出画廊问题是NP-Hard问题，这里不做多的赘述。 实际上，对于不规则多边形而言，最对只须n/3个点即可覆盖多边形（如下图）。 锯齿形，需要最多的哨兵。因为每三个顶点构成的三角形一定需要一个哨兵。 2、Fisk’s Proof 几个概念 扇形：一个有核点的星形多边形。每个扇形可以由一个点覆盖整个扇形。 内对角线：多边形顶点之间的内部连线 切线：某个点相切。任意一个边或切线都不是对角线 对角线的集合是连续的如果任意两条对角线不相交。 上：内对角线 下：切线 三角剖分问题 多边形P的最大的连续对角线的集合称为P的三角剖分。 着色：任意一条边和内对角线连接的两个点颜色互异。 顶点着色 Fisk’s的证明指出：对于进行三角剖分后 ...

目标：对一系列的几何体，判断它们是否有交集，计算它们交集的个数，枚举所有的交集，构建这些交。 1、Preliminary EU问题 问题描述：给定一系列的实数，判断是否互异。 算法：将他们排序，然后可以通过线性扫描找到。复杂度O(nlogn) Minimum Gap：对于实轴上的n个点，找到相邻两个的最小距离 对于这个问题，我们可以利用EU问题来规约，两个问题的输入都是n个整数，Minimum Gap如果是正数，那么EU的输出为Yes，如果是0，EU的输出是No。因此Minimum Gap的下界也是O(nlogn) Maximum Gap： 算法描述：先找到最小值lo,和最大值hi，然后将这段分成n-1段，然后对每一个元素进行整除放进桶里。接着做线性扫描，先除去那些空桶。对于前面的桶考虑最右元素和后面桶的最左元素。考虑这两者然后找到最大的缝隙。 Integer Element Uniqueness：EU问题中的元素全都为整数 2、Interval Intersection Detection：区间交问题 问题描述：给定一系列数轴上的区间，判断它们是否有交 简单算法 ...

17289f4fd8cc2af956ca06fbbcbbc3ceee270d23331ae046282c79f19ce763204679d39279cf7a5be5a57e187d813b6f 这篇文章记录我在大学期间参加的各个社团与志愿活动、青协活动等经历，需要密钥。

6d63b89221e13b3febb0d4b727fe1cb7b9a5d0e0ce86e70d76eba31de419c45e 其实我很会吃。需要密钥

121020c51dd2a6d451cd928e21400bc4a2f9ccf110435a8cd7adb67156c7f1a7c8c348b94b66e7a7ec707c6d3ce260b84aff699ae2671f349f069d6b8615be2f3d7b45b2685f964739481bf22e411d9e47c19657d8ff99b6754a290ab3222c5722cfefff7e53e2e7328f63611d8fa5b1c65420a9dcab704d018fe5e921a1c3caf7f768621a7932b089a3dd01a96cdf99143fea4ba0863796bd95b8a12a42342202d6876dab74c138ee8193ca2c84b1fadf6b39aea7f59f18cfa9e5be76e5fcd52eb3ddb6560970e020d77bc192eb7754cd1c8f1eb51028a36a2a242d2ed17440f2a6475d15a902603e73bbea6324f43df1330a191cc5f56d9 ...

6d63b89221e13b3febb0d4b727fe1cb7b9a5d0e0ce86e70d76eba31de419c45e 我的教育经历与毕业照片。需要密钥

85d85000c6eae48376b9559cb0794201e1e933e326fefcf6e98bac5473f00347 这篇文章记录我的运动、健身活动与打卡记录。需要密钥

1、凸性(Convexity) 以颜色为例 假设x,y,z是三种颜色，如果仅以x,y就能调出来的颜色，那么如u所示它一定会落在x,y中；若需要x,y,z三种 一起，那么如v所示会落在以x,y,z三点连成的三角形内部。 2、极点(Extreme Point) 在一组点中，沿着这个点作直线，必然能找到一条直线，使得其他所有点都在该直线的一侧。 判断一个点是否为极点：看该点是否存在于其中的三个点围成的三角形的内部 s点就不是极点 To-Left Test：判断一个点是否存在于三个点围成的三角形内部，那么就对该三个点以逆时针方向两两连成有向边，如果该点在这三条直线的左侧，那么成立。（复杂度为O(n^4)） 123456bool InTriangle(Point p, Point q, Point r, Point s) { bool pqLeft = ToLeft(p, q, s); bool qrLeft = ToLeft(q, r, s); bool rpLeft = ToLeft(r, p, s); return (pdLeft == qrLeft) ...

和实验室同学一起继续参加机器人抓取挑战赛，再次拿到冠军 学习： 清华大学-邓俊辉-数据结构与算法 吴恩达-深度学习

daf9e1003c8b639b6138b233a8332339e2259ca3a7d85c615bb2edf324a38a214d205994d14d67f9692853b119bf7034e53344c14647503faa4e11de0e5c78f27727fd4c549cc7f6f54b9338fc900760c1b0303b71e6990f5e8d413029646564d8083e39ece363c8f2e12f6618fa77f1b5a2bf720ed321fc2778aafa079698f79020de90c9943c01691bd98123e14aad4db00b7d3eaface41147477a011651a1c0f61f4d60b6c5106529e1d71eb65c26c88a8cc7944fb64988eb6c8fde3f0710ee4c9fd9a612d25e0621d63c46d19f931f7716c1d9dc4c02e756cf9fa5b363f15152ab20befba8fe124384a26a9ac65d3b8a891559b876d8c ...