Minimal polygon search is a common problem in computer aided design when trying to determine surface of bounding areas on cross sections. An algorithm solving this problem is commonly implemented in CAD applications by a filling function. The input data are a set of line segments, where not all intersections are known. This thesis proposes an algorithm to find the minimal polygon with edges on segments from a given set which contains a given point of origin and which can also have holes. The algorithm reduces the problem into steps, where each step solves a single computational problem. The output data of each step become input data for the next step, or the end result of the algorithm from the final step. The steps of the algorithm are: a construction of line segment set where all line segments intersect only in their endpoints, finding minimal polygons defined by the set of line segments, and finding the minimal polygon containing the given point, including holes in that polygon.
|
