Algorithms for computing diffuse reflection paths in polygons
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 polygonal edges of P. We present three different algorithms for computing diffuse reflection paths from s to t inside P. For constructing such a path, the first algorithm ses 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 + k log n) time, where k denotes the number of reflections in the path. The third algorithm is for both polygons with or without holes, and it runs in O(n2) time. The number of reflections in the path produced by this algorithm can be at most 3 times that of an optimal diffuse reflection path. The problem of computing a diffuse reflection path between two points inside a polygon has not been considered in the past.
|Organisation||School of Computer Science|
Ghosh, S.K. (Subir Kumar), Goswami, P.P. (Partha Pratim), Maheshwari, A, Nandy, S.C. (Subhas Chandra), Pal, S.P. (Sudebkumar Prasant), & Sarvattomananda, S. (Swami). (2009). Algorithms for computing diffuse reflection paths in polygons. doi:10.1007/978-3-642-00202-1_5