CGAL 6.0 - 2D Polygons: User Manual

link管理

链接快照平台

输入网页链接，自动生成快照
标签化管理网页链接

相关文章推荐

气势凌人的洋葱 · 山东省教育厅烟台市招远黄金博物馆· 6 月前 ·

有胆有识的甘蔗 · GitHub - ...· 7 月前 ·

闯红灯的馒头 · X03 - Silvent AB· 1 年前 ·

痴情的板凳 · 百度一下，你就知道· 1 年前 ·

聪明伶俐的刺猬 · Big airline heist | ...· 1 年前 ·

Introduction

A polygon is a closed chain of edges. Several algorithms are available for polygons. For some of those algorithms, it is necessary that the polygon is simple. A polygon is simple if edges don't intersect, except consecutive edges, which intersect in their common vertex.

The following algorithms are available:

find the leftmost, rightmost, topmost and bottommost vertex.

compute the (signed) area.

check if a polygon is simple.

check if a polygon is convex.

find the orientation (clockwise or counterclockwise)

check if a point lies inside a polygon.

All those operations take two forward iterators as parameters in order to describe the polygon. These parameters have a point type as value type.

The type Polygon_2 can be used to represent polygons. Polygons are dynamic. Vertices can be modified, inserted and erased. They provide the algorithms described above as member functions. Moreover, they provide ways of iterating over the vertices and edges.

The Polygon_2 class is a wrapper around a container of points, but little more. Especially, computed values are not cached. That is, when the Polygon_2::is_simple() member function is called twice or more, the result is computed each time anew.

Polygons with Holes and Multipolygons with Holes

This package also provides classes to represent polygons with holes and multipolygons with holes.

For polygons with holes, these are Polygon_with_holes_2 and General_polygon_with_holes_2 . They can store a polygon that represents the outer boundary and a sequence of polygons that represent the holes.

For multipolygons with holes, there is Multipolygon_with_holes_2 . It stores a sequence of polygons with holes.

These classes do not add any semantic requirements on the simplicity or orientation of their boundary polygons.

Examples The Polygon Class

The following example creates a polygon and illustrates the usage of some member functions.

File Polygon/Polygon.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>

#include <CGAL/Polygon_2.h>

#include <iostream>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;

typedef K::Point_2 Point;

typedef CGAL::Polygon_2<K> Polygon_2;

using std::cout; using std::endl;

int main()

Point points[] = { Point(0,0), Point(5.1,0), Point(1,1), Point(0.5,6)};

Polygon_2 pgn(points, points+4);

// check if the polygon is simple.

cout << "The polygon is " <<

(pgn.is_simple() ? "" : "not " ) << "simple." << endl;

// check if the polygon is convex

cout << "The polygon is " <<

(pgn.is_convex() ? "" : "not " ) << "convex." << endl;

return 0;

CGAL::Exact_predicates_inexact_constructions_kernel

CGAL::Polygon_2

The class Polygon_2 implements polygons.

Definition: Polygon_2.h:65

The Multipolygon with Holes Class

The following example shows the creation of a multipolygon with holes and the traversal of the polygons in it.

File Polygon/multipolygon.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>

#include <CGAL/Multipolygon_with_holes_2.h>

using Kernel = CGAL::Exact_predicates_inexact_constructions_kernel ;

using Point_2 = Kernel::Point_2 ;

using Polygon_2 = CGAL::Polygon_2<Kernel> ;

using Polygon_with_holes_2 = CGAL::Polygon_with_holes_2<Kernel> ;

using Multipolygon_with_holes_2 = CGAL::Multipolygon_with_holes_2<Kernel> ;

int main() {

Point_2 p1_outer[] = { Point_2 (0,0), Point_2 (1,0), Point_2 (1,1), Point_2 (0,1)};

Point_2 p1_inner[] = { Point_2 (0.2,0.2), Point_2 (0.8,0.2), Point_2 (0.8,0.8), Point_2 (0.2,0.8)};

Polygon_with_holes_2 p1(Polygon_2(p1_outer, p1_outer+4));

Polygon_2 h(p1_inner, p1_inner+4);

p1.add_hole(h);

Point_2 p2_outer[] = { Point_2 (0.4,0.4), Point_2 (0.6,0.4), Point_2 (0.6,0.6), Point_2 (0.4,0.6)};

Polygon_with_holes_2 p2(Polygon_2(p2_outer, p2_outer+4));

Multipolygon_with_holes_2 mp;

mp.add_polygon_with_holes(p1);

mp.add_polygon_with_holes(p2);

for ( auto const & p: mp.polygons_with_holes()) {

std::cout << p << std::endl;

return 0;

CGAL::Multipolygon_with_holes_2

The class Multipolygon_with_holes_2 models the concept MultipolygonWithHoles_2.

Definition: Multipolygon_with_holes_2.h:35

CGAL::Polygon_with_holes_2

The class Polygon_with_holes_2 models the concept GeneralPolygonWithHoles_2.

Definition: Polygon_with_holes_2.h:43

Kernel::Point_2

Kernel

Figure 15.1 A polygon and some points

Algorithms Operating on Sequences of Points

The following example creates a polygon and illustrates the usage of some global functions that operate on sequences of points.

File Polygon/polygon_algorithms.cpp

      
       #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
      
       #include <CGAL/Polygon_2_algorithms.h>
      
       #include <iostream>
      
       typedef
      
       CGAL::Exact_predicates_inexact_constructions_kernel
      
      K;
     
       typedef
      
      K::Point_2 Point;
     
       using
      
      std::cout;
      
       using
      
      std::endl;
     
       void
      
      check_inside(Point pt, Point *pgn_begin, Point *pgn_end, K traits)
     
      cout <<
      
       "The point "
      
      << pt;
     
       switch
      
      (
      
       CGAL::bounded_side_2
      
      (pgn_begin, pgn_end,pt, traits)) {
     
       case
      
       CGAL::ON_BOUNDED_SIDE
      
      :
     
      cout <<
      
       " is inside the polygon.\n"
      
      ;
     
       break
      
      ;
     
       case
      
       CGAL::ON_BOUNDARY
      
      :
     
      cout <<
      
       " is on the polygon boundary.\n"
      
      ;
     
       break
      
      ;
     
       case
      
       CGAL::ON_UNBOUNDED_SIDE
      
      :
     
      cout <<
      
       " is outside the polygon.\n"
      
      ;
     
       break
      
      ;
     
       int
      
      main()
     
      Point points[] = { Point(0,0), Point(5.1,0), Point(1,1), Point(0.5,6)};
     
       // check if the polygon is simple.
      
      cout <<
      
       "The polygon is "
      
      << (
      
       CGAL::is_simple_2
      
      (points, points+4, K()) ?
      
       ""
      
      :
      
       "not "
      
      )
     
      <<
      
       "simple."
      
      << endl;
     
      check_inside(Point(0.5, 0.5), points, points+4, K());
     
      check_inside(Point(1.5, 2.5), points, points+4, K());
     
      check_inside(Point(2.5, 0), points, points+4, K());
     
       return
      
      0;
     
     Polygons in 3D Space
     
      Sometimes it is useful to run a 2D algorithm on 3D data. Polygons may be contours of a 3D object, where the contours are organized in parallel slices, generated by segmentation of image data from a scanner.
     
      In order to avoid an explicit projection on the
      
       xy
      
      plane, one can use the traits class
      
        Projection_traits_xy_3
       
      which is part of the 2D and 3D Linear Geometric Kernel.
     
      File
     
      Polygon/projected_polygon.cpp
     
        #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
       
        #include <CGAL/Projection_traits_yz_3.h>
       
        #include <CGAL/Polygon_2_algorithms.h>
       
        #include <iostream>
       
        typedef
       
        CGAL::Exact_predicates_inexact_constructions_kernel
       
       K;
      
        typedef
       
       K::Point_3
       
        Point_3
       
       ;
      
        int
       
       main()
      
        Point_3
       
       points[4] = {
       
        Point_3
       
       (0,1,1),
       
        Point_3
       
       (0,2,1),
       
        Point_3
       
       (0,2,2),
       
        Point_3
       
       (0,1,2) };
      
        bool
       
       b =
       
        CGAL::is_simple_2
       
       (points,
      
       points+4,
      
        CGAL::Projection_traits_yz_3<K>
       
       ());
      
        if
       
       (!b){
      
       std::cerr <<
       
        "Error polygon is not simple"
       
       << std::endl;
      
        return
       
       1;
      
        return
       
       0;
      
      Iterating over Vertices and Edges
      
       The polygon class provides member functions such as
       
         Polygon_2::vertices_begin()
        
       and
       
         Polygon_2::vertices_end()
        
       to iterate over the vertices. It additionally provides a member function
       
         Polygon_2::vertices()
        
       that returns a range, mainly to be used with modern
       
        for
       
       loops. The same holds for edges and for the holes of the class
       
         Polygon_with_holes_2
        
       .
      
       File
      
       Polygon/ranges.cpp
      
         #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
        
         #include <CGAL/Polygon_2.h>
        
         typedef
        
         CGAL::Exact_predicates_inexact_constructions_kernel
        
        K;
       
         typedef
        
         CGAL::Polygon_2<K>
        
        Polygon_2;
       
         typedef
        
        K::Point_2
        
         Point_2
        
        ;
       
         typedef
        
        K::Segment_2
        
         Segment_2
        
        ;
       
         int
        
        main()
       
         // create a polygon and put some points in it
        
        Polygon_2 p;
       
        p.push_back(
        
         Point_2
        
        (0,0));
       
        p.push_back(
        
         Point_2
        
        (4,0));
       
        p.push_back(
        
         Point_2
        
        (4,4));
       
         for
        
        (
        
         const
        
         Point_2
        
        & p : p.vertices()){
       
        std::cout << p << std::endl;
       
         // As the range is not light weight, we have to use a reference
        
         const
        
         Polygon_2::Vertices
        
        & range = p.vertices();
       
         for
        
        (
        
         auto
        
        it = range.begin(); it!= range.end(); ++it){
       
        std::cout << *it << std::endl;
       
         for
        
        (
        
         const
        
         Segment_2
        
        & e  : p.edges()){
       
        std::cout << e << std::endl;
       
         return
        
        EXIT_SUCCESS;
       
       Draw a Polygon
       
        A polygon can be visualized by calling the
        
         CGAL::draw<P>()
        
        function as shown in the following example. This function opens a new window showing the given polygon. A call to this function is blocking, that is the program continues as soon as the user closes the window. Versions for polygons with holes and multipolygons with holes also exist, cf.
        
         CGAL::draw<PH>()
        
        and
        
         CGAL::draw<MPH>()
        
        .
       
        File
       
        Polygon/draw_polygon.cpp
       
          #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
         
          #include <CGAL/Polygon_2.h>
         
          #include <CGAL/draw_polygon_2.h>
         
          typedef
         
          CGAL::Exact_predicates_inexact_constructions_kernel
         
         K;
        
          typedef
         
          CGAL::Polygon_2<K>
         
         Polygon_2;
        
          typedef
         
          CGAL::Point_2<K>
         
         Point;
        
          int
         
         main()
        
          // create a polygon and put some points in it
         
         Polygon_2 p;
        
         p.push_back(Point(0,0));
        
         p.push_back(Point(4,0));
        
         p.push_back(Point(4,4));
        
         p.push_back(Point(2,2));
        
         p.push_back(Point(0,4));
        
          CGAL::draw
         
         (p);
        
          return
         
         EXIT_SUCCESS;
        
        This function requires
        
         CGAL_Qt6
        
        , and is only available if the macro
        
         CGAL_USE_BASIC_VIEWER
        
        is defined. Linking with the cmake target
        
         CGAL::CGAL_Basic_viewer
        
        will link with
        
         CGAL_Qt6
        
        and add the definition
        
         CGAL_USE_BASIC_VIEWER
        
        .
       
          Figure 15.2
         
         Result of the run of the draw_polygon program. A window shows the polygon and allows to navigate through the scene.