Original link: https://www.codewoody.com/posts/33539/

In this article, I will sort out the introduction of 2D Arrangements in the CGAL official documentation. The source document address is: CGAL 5.4.1 – 2D Arrangments . CGAL’s documents generally have a relatively large volume, and it is not easy to understand directly when reading directly, so I will reorganize them again.

1 Introduction

Arrangments is the abbreviation of Geometry Arrangements. This word is not easy to translate directly into Chinese, so we will call it the original name in English below. The concept of Arrangement is

Geometric arrangements, or arrangements for short, are subvisions of some space induced by geometry objects.

In short, Arrangements are the divisions of space produced by a set of elements. The figure below gives an example:

The figure shows two curves c 1 and c 2 in the plane, which generate two bounded faces (Faces) f 1 and f 2 (shaded area in the figure). At the same time, the two curves in the figure also generate 7 vertices (including the start and end points of the curve itself) and 8 edges. The concept of Arrangement can be further extended from a plane to a higher dimensional space, where any element can become a segmentation element.

1.1 Topology and geometry

Topological and geometrical data structures are split in CGAL time. This idea is the key to designing geometry software. This allows us to independently consider the design of topological and geometric algorithms. In CGAL, developers use templates extensively to achieve this.

Consider the following example:

 1
 2

 template < typename GeometryTraits, typename Dcel>
 class Arrangement_2 { ... };

This template form indicates that when constructing the Arrangement object, we need to provide the geometry object type and related Traits (see The Geometry Traits ) in the position of the GeometryTraits type parameter; Dcel represents the Doubly-connected edge list data structure, this data The structure is used for the storage of topological data, which includes related types such as Vertice , Edge , Face and so on, as well as the operation methods for these types of data (see Representation of Arrangements: The Dcel ).

The parent class of Arrangement_2 is:

 1
 2

 template < typename GeometryTraits, typename TopologyTraits>
 class Arrangement_on_surface_2 { ... };

An instance of this class represents an Arrangement of two-dimensional faces in three-dimensional space.

1.2 Well-behaved Curves

In 2D Arrangment, not any curve can participate in the formation of division, which is discussed in detail in The Geometry Traits . However, based on the consideration of computational complexity at the implementation level, we usually have stronger assumptions about the form of the input curve. These assumptions include:

1. The curve is non-self-intersecting;
2. Each curve has a finite number of intersections;

2 Basic Arrangments

This chapter is an introduction to using Arrangments.

2.1 Representation of Arrangements: The Dcel

Given a curved geometry C in a two-dimensional plane, arrangement A ( C ) represents the division of the plane into 0-, 1-, and 2-dimensional elements, called Vertices, Edges, and Faces, respectively. Edges in set C may intersect each other, and these changes do not necessarily conform to x-monotone. We construct a set C′′ from C. The elements in the set C′′ are all x-monotone curves, and these curves do not intersect each other internally (note that the original single curve will be disassembled in this process). Note that the curves of x-monotone are not necessarily self-intersecting. C may also contain isolated points. In this way, C″ can be constructed as a plan view. Eventually A ( C ) and A ( C′′ ) have the same face structure, but the latter may have more vertices and edges.

The graph structure of A ( C” ) can be represented by DCEL. This data structure stores points, edges, faces, and the connections between these elements. This data structure is a member of the Halfedge data structure family of data structures.

In the DCEL data structure, each edge is represented by a pair of directed halfedges, and these two halfedges are twins of each other, with opposite directions. Each directed halfedge has a source vertex and a target vertex. Halfedge is used to connect vertices and separate faces. If a vertex v is the target of a halfedge e , then v and e are incident to each other. For a vertex, the edges connected to this vertex are given in counter-clockwise order. Isolated points have no limbs.

Each Halfedge stores its adjacent face, which is to the left of it. Halfedge will have one of its limbs with the same face. Traversing the DCEL graph from an edge along this relationship will eventually return to itself and form a closed loop, which is called a connected component of the boundary (CCB).

The CCB will form a face in the plane, this CCB is called the outer_ccb of this face. We only consider the following cases

1. Each edge is limited (Bounded), then there is at most one unbounded face in each Arrangment;
2. Arrangement is fixed inside a plane, so that each face has only one outer CCB at the end;

Unbounded faces do not have outer ccb. The ccb inside the face forms a hole, giving the inner ccb in a clockwise loop. Note that inner ccb does not necessarily form a face, it may be a line. An inner ccb may also contain multiple faces. In actual processing, interior outliers are not considered holes.

2.2 Arrangement class template

The main component of the 2D Arrangement package is the Arrangement_2<Traits, Decl> class template; this template provides interfaces for creating, traversing, and maintaining Arrangement data structures.

The 2D Arrangement package is designed with the following two principles:

• Separating the representation of Arrangement and the implementation of internal geometric algorithms;
• Separation of topology and geometry;

The latter element is reflected in the two type parameters of the class template.

• The Traits template parameter should enter a model of the ArrangementBasicTraits_2 concept, which contains lines and 2D points in the x-monotone paradigm, ArrangementBasicTraits_2::X_monotone_curve_2 and ArrangementBasicTraits_2:: ArrangmentBasicTraits_2::Point_2 .
• The DCEL template parameter should enter a model of the ArrangmentDcel concept; its default parameter is Arr_default_dcel<Traits> , which is generally sufficient.

See a basic example below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
 10
 11
 12
 13
 14
 15
 16

 # include <CGAL/Cartesian.h>
 # include <CGAL/Arr_non_caching_segment_traits_2.h>
 # include <CGAL/Arrangement_2.h>
 typedef int Number_type;
 typedef CGAL::Cartesian<Number_type> Kernel;
 typedef CGAL::Arr_non_caching_segment_traits_2<Kernel> Traits;
 typedef Traits_2::Point_2 Point;
 typedef Traits_2::X_monotone_curve_2 Segment;
 typedef CGAL::Arrangement_2<Traits_2> Arrangement;
 int main () {
 Arrangement arr;
 Point p1 ( 1 , 1 ) , p2 ( 1 , 2 ) , p3 ( 2 , 1 ) ;
 Segment cv[] = { Segment (p1, p2), Segment (p2, p3), Segment (p3, p1)};
 CGAL:: insert (arr, &cv[ 0 ], &cv[ sizeof (cv)/ sizeof (Segment)]);
 return 0 ;
 }

This article is reprinted from: https://www.codewoody.com/posts/33539/
This site is for inclusion only, and the copyright belongs to the original author.