多边形三角剖分/网格

多边形三角剖分，顾名思义，就是把一个多边形分割成三角形的过程。形式上，三角剖分是用一组最大的不相交对角线将多边形分解成三角形。不相交对角线的集合应该是最大的，以确保在三角形的边缘内部没有多边形顶点。例子

多边形的三角剖分是许多图形应用程序的基本构建模块。高速图形渲染通常依赖于将曲面细分为三角形，以便硬件进行有效处理。多边形三角化是计算几何中的一个基本问题。

每个简单多边形都允许三角剖分，而任何简单多边形的三角剖分 $n$顶点由 $n -$三角形。

百分度

让 $u$而且 $w$的两个相邻顶点 $v$关于边界 $P$．如果开放段 $\眉题{uw}$在内心深处 $P$，我们找到了一条对角线。否则，会有一个或多个这样的顶点，让 $v \ '$做最远的那个 $\眉题{uw}$．段连接 $v \ '$来 $v$不能与的边相交 $P$，因为这样的边在三角形内部会有一个端点 $\眉题{uw}$，与的定义相矛盾 $v \ '$．因此 $\眉题{vv \ '}$是一个对角。一旦我们确定了对角线的存在，那么我们就可以说任何对角线都可以切割 $P$变成两个简单的多边形 $P_a$而且 $P_b$．让 $v_1$是证书的数量 $P_a$而且 $v_2$的顶点数 $P_b$． $V_1$而且 $V_2$必须小于 $n$通过归纳 $P_a$而且 $P_b$也可以进行三角测量。这意味着 $P$也可以进行三角测量。

假设你有一个画廊，里面收藏着在艺术爱好者中不受欢迎但在罪犯中也很受欢迎的著名画家的作品。

图像

因此，艺术画廊必须小心地保护他们的作品。白天安保人员可以监视，但晚上就必须通过监控摄像头来完成。你需要放置足够多的这样的摄像头，以便在任何时候，整个画廊的每个部分都能被监督。为了简单起见，让我们假设画廊的平面图是一个简单的多边形。让我们还假设安全摄像头不能移动，它们被放置在角落里，或者顶点多边形。

艺术画廊定理:对于一个简单的多边形 $n$顶点, $\ lfloor \压裂{n} {3} \ rfloor$摄像机总是足以使多边形中的每个点对至少一个摄像机可见。

让我们从一个简单的例子开始，一个凸多边形 $n = 3$(三角形)。放置在三角形顶点的摄像机可以清楚地监视整个三角形。这是因为连接三角形中任意两点的任何直线都完全包含在三角形中。

现在考虑一般的多边形。如果我们能把它分成几个三角形，那么在三角形顶点的守卫就可以监督每个单独的三角形，这样整个多边形就会得到安全的守卫。

上面描述的多边形也可以被认为是一个图，每个顶点代表一个节点。

图

这个问题现在简化为图形着色问题。如果我们想用三种不同的颜色给顶点上色这样每个三角形就不会有两个相同颜色的顶点。用红、绿、蓝三种颜色。每个三角形的树角必须有三种颜色。因此，每个三角形的一个角上都有一个红色节点。因此，如果守卫被放置在红节点上，整个多边形就会被覆盖。类似地，如果守卫被放置在绿色节点或蓝色节点上，整个多边形将被覆盖。

最后一步涉及到应用<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/pigeonhole-principle-definition/">鸽子洞原理．如果 $n$对象被放置在 $k$鸽子洞，那么至少一个洞必须包含不超过 $k \压裂{n} {}$对象。如果每一个 $k$洞里有超过 $k \压裂{n} {}$洞口，物体的总数就会超过 $n$．在我们的例子中 $n$对象是 $n$三角剖分图的节点，和 $k$三种颜色的洞。原则是一种颜色不能超过 $\压裂{n} {3}$次了。自 $n$是一个整数，我们可以得出结论，一种颜色使用不超过 $\ lfloor \压裂{n} {3} \ rfloor$次了。从而证明了定理。

我们讨论过的大多数几何问题，特别是多边形，如果定义了某种网格，就可以自然地分解为单个单元格。这样做有助于解决这些单元格上的某些计算问题。三角定位并不困难。我们可以插入正方形中的两条对角线中的一条，或者从正六边形中的任意一点辐射出的三条对角线将其三角化。这仅仅是因为这些图形是凸的;凹槽和凸起使这个问题更加困难。

范围查询

给定平面上的一组点，很自然地就会问这些点中的哪些在某个特定的区域内。“列出阿姆斯特丹50英里内的所有城市”就是这类问题，如果有一组与城市对应的点，就可以合理地提出这个问题。一般来说，我们假设我们有一组记录具有某些属性，这些属性的值来自某个有序集。在实际应用中查找数据库中满足问题指定范围限制的所有记录。

但是，为了简单起见，让我们考虑一下表单的查询 $n \乘以m$“矩阵的一个给定子矩形中的值的和是多少?”

任何面向轴的矩形都可以由两点指定:左上角 $(x_l y_l)$还有右下角 $(x_r y_r)$．最简单的算法是运行一个嵌套循环，将值相加[我][j]为 $X_l \leq I \leq x_r$而且 $Y_r \leq j \leq y_l$．然而，这是低效的。相反，我们可以构造第二个矩形矩阵这样的元素a1 [x] [y]表示所有元素的和[我][j]为 $我\ leq x$而且 $j \ leq y$．这优势矩阵这样可以很容易地找到任何矩形中元素的和，因为这样的方框中的元素的和是:

1

年代(xl、yl xr,年)= m1 (xr) (yl) m1 [xl-1][我们]m1 (xr)[一]+ m1 (xl-1)(一)

这产生了一个整体 $O (mn)$解决方案哪个更好。