Algorithms for computing diffuse reflection paths in polygons
Algorithms for computing diffuse reflection paths in polygons
复制标题
计算多边形中漫反射路径的算法
DOI：
10.1007/s00371-011-0670-z
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Swami Sarvattomananda
中科院分区：
文献类型：
--
作者：
S. Ghosh;Partha P. Goswami;A. Maheshwari;S. Nandy;S. P. Pal;Swami Sarvattomananda
设S是n个顶点的多边形P内的一个点光源。从S到P内某点t的多边形路径称为漫反射路径，如果该路径的转折点位于P的边上。如果漫反射路径上的反射次数最少，则称该路径为最优路径。从S到P内部t的漫反射路径的计算问题过去没有明确地考虑过。对于这个问题，我们提出了三种不同的算法，它们都会产生次优路径。为了构造这样的路径，第一种算法使用贪婪方法，第二种算法使用最小链路路径的变换，第三种算法使用P的边-边可见性图。前两种算法是针对无洞的多边形的，它们的运行时间为O(n+klogn)，其中k表示所构造的路径中的反射次数。第三种算法适用于有洞或无洞的多边形，运行时间为O(N2)。由第三种算法产生的路径中的反射次数最多可以是最佳漫反射路径的三倍。虽然第三种算法中使用的组合方法对路径上的反射次数提供了更好的界限，但第一种和第二种算法基于其基于局部几何信息的优雅几何方法的优点。
Let s be a point source of light inside a polygon P of n vertices. A polygonal path from s to some point t inside P is called a diffuse reflection path if the turning points of the path lie on edges of P. A diffuse reflection path is said to be optimal if it has the minimum number of reflections on the path. The problem of computing a diffuse reflection path from s to t inside P has not been considered explicitly in the past. We present three different algorithms for this problem which produce suboptimal paths. For constructing such a path, the first algorithm uses a greedy method, the second algorithm uses a transformation of a minimum link path, and the third algorithm uses the edge–edge visibility graph of P. The first two algorithms are for polygons without holes, and they run in O(n+klogn) time, where k denotes the number of reflections in the constructed path. The third algorithm is for polygons with or without holes, and it runs in O(n2) time. The number of reflections in the path produced by this third algorithm can be at most three times that of an optimal diffuse reflection path. Though the combinatorial approach used in the third algorithm gives a better bound on the number of reflections on the path, the first and the second algorithms stand on the merit of their elegant geometric approaches based on local geometric information.