The STUDIA UNIVERSITATIS BABEŞ-BOLYAI issue article summary

The summary of the selected article appears at the bottom of the page. In order to get back to the contents of the issue this article belongs to you have to access the link from the title. In order to see all the articles of the archive which have as author/co-author one of the authors mentioned below, you have to access the link from the author's name.

 
       
         
    STUDIA INFORMATICA - Issue no. 1 / 2008  
         
  Article:   SIGNEDINTERSECTION - A NEW ALGORITHM FOR FINDING THE INTERSECTION OF TWO SIMPLE POLYGONS.

Authors:  ANDREEA SABĂU.
 
       
         
  Abstract:  The operation of determining the intersection of two polygons is one of the most important operations of computational geometry. This paper presents a new algorithm called SignedIntersection which founds the intersection of two simple polygons, convex or concave, without holes, in two steps. The first step is using a sweep line in order to find the intersection points and segments that form the polygons’ intersection. This data is enriched with additional values that indicate the way the sweep line traverse the segments, if the vertexes are given in counter-clockwise order. Such an additional value is a sign, positive or negative. The final step consists in building the result using the data determined by the previous step. The result of the intersection of two (possible) non-convex polygons may be empty or may consist of one or more polygons, convex or concave.  
         
     
         
         
      Back to previous page