THE SHORTEST PATH THROUGH THE INTERIOR OF A POLYGON
DOUGLAS W. THOMSON, JOHN V THOMSON · Engineering Optimization · 1987
As part or an expert system dealing with water penetration through window frames, the authors have developed an algorithm for finding the shortest path between two points within a compact, simply connected area in the 2D plane with a finite polygon boundary. The algorithm is based on A∗, a heuristic search algorithm, with improvements taking advantage of the knowledge that only certain points on the polygon need be considered, and a heuristic using the remaining distance to the destination. The algorithm illustrates the use of a generic artificial intelligence technique along with the importance of problem-specific knowledge for obtaining efficiency.