监视摄像机问题——2002年第7期题解

问题描述请参见2002年第7期杂志。问题分析本题是一个经典的计算几何问题。满足题目要求的摄像机位置所组成的轨迹在计算几何学中称为“多边形的核”。原题就是要求判断一个多边形的核是否存在。定义一:给定任意简单多边形P,若P内存在点z,使得对于P内所有的点P,线段zp完全位于P内,具有上述性质的点z的轨迹称为多边形P的核。构造多边形的核不仅是解决某些计算几何问题(比如包含问题)所需要的预处理步骤,而且在工程设计、计算机图形学领域中有重要应用价值。下面我们分几步来解决这个问题。