Algorithm For General Polygon Clipping And Its Applications In Civil Engineering

Clipping algorithm is an basic algorithm in the Computer Graphics and the base of a lot of important task. Some algorithms of line clipping have been very perfect, especially the algorithms about line clipping by the rect window, but the line clipping algorithms of general polygons window haven't been developed well. What's more, polygon clipping algortithm of the polygon window haven't been widely noticed. But both of the latter have much more weighty practical meaning in the Computer Graphic and engineering pracitce. Especially, literature about the algorithm which describes how to a polygon window clip a polygon with a or more arc edge hasn't been found yet, however, which is the main operation in the three dimensions visualization budget software in the civil engineering.So, firstly, a minitype vector graphics system is empoldered with Visual C++ language and Open Graphics Library(Open GL) in this paper, which provides a graphic flat for the continued algorithm design, debugging and application.Second, an algorithm about general polygons clipped by the general polygon window is designed in the paper. Above all, this algorithm can be used to process general polygons such as protruding polygons, concave polygons, polygons with holes inside and polygon with at least one arc edge named widesense polygon in this paper. Next, the technology involving box, and the technology of calculating insection of line segments, radial methods in the computational geometry are used in the paper, which greatly predigest the computing procedure. What's more, objects of CObList Class and CArray class supported well by Vicual C++ Language are used for storing data in the algorighm, which makes the single list date structure possible and less memory and running time required. Sign function is introduced which cut off the course of error transfer and insure the computing precision. Finally, aiming at the deficiency of the member function of Microsoft Foundation Class Library, a new function is compiled which can be used to judge the postiotn relation between the given point and the widesence polygon, which effectively eliminates the lethal error caused by the member function mentioned above. Last, an algorithm with much geometrical adaptability and lower time and space complexity is finished.Lastly, the new algorithm is used in the three dimensions visualization budget software of the civil engineering, which successfully realizes the deduction between the wall and wall, wall and beam, wall and pole and wall and board in the three dimensions dynamic intersection.