线性规划
，即二维多胞形。线性目标函数的最优解位于红线与多边形的交点处。这条红线是目标函数的等值线，箭头指示了优化的方向。]] 。目标函数的固定值所形成的表面是平面（图中未显示）。线性规划问题就是要在这个多面体上找到一个点，使其位于具有最高可能值的平面上。]] 线性规划（，简称LP）是一种数学方法，通过线性方程或不等式描述问题的约束条件和目标，以实现最佳结果（例如利润最大化或成本最小化）。作为最优化的一种特例，线性规划在许多领域都有重要应用。 更…
标签：#几何算法
共 6 篇文章
点在多边形内问题
]] 在计算几何中，点在多边形内（point-in-polygon, PIP）问题指定一个平面中的多边形，要求确定输入的点位于多边形的内部、外部还是边界上。它是点定位问题的一个特例，可应用于处理几何数据领域，例如计算机图形学、计算机视觉、地理信息系统(GIS)、运动规划和计算机辅助设计(CAD)。 一份计算机图形学中关于该问题的早期说明表示，早在 1974 年就有了两种常用求解方法——光线投射和角度求和。 在光线追踪新闻的一期 中，可以…
最邻近搜索
最邻近搜索（Nearest Neighbor Search, NNS）又称为“最近点搜索”（Closest point search），是一个在尺度空间中寻找最近点的优化问题。问题描述如下：在尺度空间M中给定一个点集S和一个目标点q ∈ M，在S中找到距离q最近的点。很多情况下，M为多维的欧几里得空间，距离由欧几里得距离或曼哈顿距离决定。 高德纳在《计算机程序设计艺术》（1973）一书的第三章中称之为邮局问题，即居民寻找离自己家最近的邮…
測量員公式
測量員公式（），又稱為鞋帶公式（）、測量師公式、高斯面積公式（），是用來計算笛卡兒平面上的任意多邊形面積的一個公式。內容如下：給定座標平面上n個點的座標（依逆時針順序）A_1(x_1, y_1), A_2(x_2, y_2), A_3(x_3, y_3), \dots, A_n(x_n, y_n)，此n個點所圍成的n邊形之面積S=\frac{1}{2} \begin{vmatrix} x_1 & x_2 & x_3 & {...} & …
星狀多邊形
星狀多邊形（star-shaped polygon）是平面上屬於星形域的多邊形區域，即這個多邊形內部存在「可以看到整個多邊形邊界與整個多邊形內部所有區域」的點。 形式上，若多邊形中存在一點使得對於中的每一點與連成的線段{{tmath|\overline{zp} }}完全位於內，則稱為星狀多邊形。。 如果星狀多邊形是凸多邊形，則任意兩個點間的連結距離（能夠保持在內部連接內部兩點的任意折線的最小線段數）為1。 如果星狀多邊形不是凸多邊形，則…
包围体
在计算机图形学与计算几何领域，一组物体的包围体就是将物体组合完全包容起来的一个封闭空间。将复杂物体封装在简单的包围体中，就可以提高几何运算的效率。通常简单的物体比较容易检查相互之间的重叠。 一组物体的包围体也是包含一个物体及周围相关环境的封闭空间，因此可以用它来表示一个非空、有限的单一物体。 包围体的使用 包围体经常用于加速一些特定的检验过程。 在光线跟踪中，包围体用于光线相交检验，在许多渲染算法中，它又用于视体的检验。如果光线或者视体…