polygonTriangulate.H

Go to the documentation of this file.

/*---------------------------------------------------------------------------*\
  =========                 |
  \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   \\    /   O peration     | Website:  https://openfoam.org
    \\  /    A nd           | Copyright (C) 2021 OpenFOAM Foundation
     \\/     M anipulation  |
-------------------------------------------------------------------------------
License
    This file is part of OpenFOAM.
 
    OpenFOAM is free software: you can redistribute it and/or modify it
    under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.
 
    OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
    FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
    for more details.
 
    You should have received a copy of the GNU General Public License
    along with OpenFOAM.  If not, see <http://www.gnu.org/licenses/>.
 
Class
    Foam::polygonTriangulate
 
Description
    Triangulation of three-dimensional polygons
 
SourceFiles
    polygonTriangulate.C
 
\*---------------------------------------------------------------------------*/
 
#ifndef polygonTriangulate_H
#define polygonTriangulate_H
 
#include "DynamicList.H"
#include "HashSet.H"
#include "labelPair.H"
#include "triFace.H"
 
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 
namespace Foam
{
 
/*---------------------------------------------------------------------------*\
                          Class polygonTriangulate Declaration
\*---------------------------------------------------------------------------*/
 
class polygonTriangulate
{
    // Private Data
 
        //- Indirect addressing into point field to form the current as yet
        //  un-triangulated polygon
        DynamicList<label> pointis_;
 
        //- Edge indices of the un-triangulated polygon
        DynamicList<label> edges_;
 
        //- The interior angles of the vertices of the un-triangulated polygon
        DynamicList<scalar> angle_;
 
        //- Flags to denote whether points of the un-triangulated polygon are
        //  "ears"; i.e., that the triangle formed by adding a diagonal between
        //  two adjacent points contains no other point
        DynamicList<bool> ear_;
 
        //- Set of tri-faces used to mark previously considered configurations
        //  in optimisation and prevent unnecessary repetition
        HashSet<triFace, Hash<triFace>> triPointsSet_;
 
        //- Point array. Used if the input points cannot be SubList-d.
        DynamicList<point> points_;
 
        //- Tri-points
        DynamicList<triFace> triPoints_;
 
        //- Tri-edge associations
        DynamicList<FixedList<label, 3>> triEdges_;
 
        //- Edge-tri associations
        DynamicList<labelPair> edgeTris_;
 
 
    // Private Static Member Functions
 
        // Renumber a polygon label to global indexing
        static inline label renumberPolyToGlobal
        (
            const label triPoly,
            const UList<label>& polyToGlobal
        );
 
        // Renumber a container of polygon labels to global indexing
        template<class Type>
        static inline Type renumberPolyToGlobal
        (
            const Type& triPoly,
            const UList<label>& polyToGlobal
        );
 
        //- Return the area of a triangle projected in a normal direction
        template<class PointField>
        static scalar area
        (
            const triFace& triPoints,
            const PointField& points,
            const vector& normal
        );
 
        //- Return the quality of a triangle projected in a normal direction
        template<class PointField>
        static scalar quality
        (
            const triFace& triPoints,
            const PointField& points,
            const vector& normal
        );
 
        //- Return whether or not two edges intersect in the plane defined by a
        //  normal
        template<class PointField>
        static bool intersection
        (
            const edge& edgePointsA,
            const edge& edgePointsB,
            const PointField& points,
            const vector& normal
        );
 
        //- Return the number of intersections of an edge within a polygon
        template<class PointField>
        static label nIntersections
        (
            const edge& edgePoints,
            const PointField& points,
            const vector& normal
        );
 
        //- Return the interior angle of the point in a polygon in the plane
        //  defined by a normal
        template<class PointField>
        static scalar angle
        (
            const label pointi,
            const PointField& points,
            const vector& normal
        );
 
        //- Return whether a point in a polygon is an "ear"; i.e., that the
        //  triangle formed by adding a diagonal between the two adjacent
        //  points contains no other point
        template<class PointField>
        static bool ear
        (
            const label pointi,
            const PointField& points,
            const vector& normal
        );
 
 
    // Private Member Functions
 
        //- Optimise the triangulation quality by flipping edges
        template<class PointField>
        void optimiseTriangulation
        (
            const label trii,
            const PointField& points,
            const vector& normal,
            UList<triFace>& triPoints,
            UList<FixedList<label, 3>>& triEdges,
            UList<labelPair>& edgeTris
        );
 
        //- Perform triangulation of a polygon by ear clipping, assuming that
        //  the polygon is simple/non-intersecting
        void simpleTriangulate
        (
            const UList<point>& points,
            const vector& normal,
            UList<triFace>& triPoints,
            UList<FixedList<label, 3>>& triEdges,
            UList<labelPair>& edgeTris,
            const bool optimal
        );
 
        //- Perform triangulation of a polygon, first by adding a spanning
        //  triangle between a point and an edge, then recursing into the
        //  sub-polygons on either side
        void partitionTriangulate
        (
            const UList<point>& points,
            const vector& normal,
            const label spanPointi,
            const label spanEdgei,
            UList<triFace>& triPoints,
            UList<FixedList<label, 3>>& triEdges,
            UList<labelPair>& edgeTris,
            const bool simple,
            const bool optimal
        );
 
        //- Perform triangulation of the given polygon, detecting self
        //  intersections and resolving them by adding spanning triangles prior
        //  to simple triangulation
        void complexTriangulate
        (
            const UList<point>& points,
            const vector& normal,
            UList<triFace>& triPoints,
            UList<FixedList<label, 3>>& triEdges,
            UList<labelPair>& edgeTris,
            const bool optimal
        );
 
        //- Perform triangulation of the given polygon
        void triangulate
        (
            const UList<point>& points,
            const vector& normal,
            UList<triFace>& triPoints,
            UList<FixedList<label, 3>>& triEdges,
            UList<labelPair>& edgeTris,
            const bool simple = false,
            const bool optimal = true
        );
 
 
public:
 
    // Static Member Functions
 
        //- Generate a random polygon for testing purposes
        static List<point> randomPolygon
        (
            Random& rndGen,
            const label n,
            const scalar error
        );
 
 
 
    // Constructors
 
        //- Construct null
        polygonTriangulate();
 
        //- Disallow default bitwise copy construction
        polygonTriangulate(const polygonTriangulate&) = delete;
 
 
    //- Destructor
    ~polygonTriangulate();
 
 
    // Member Functions
 
        // Access
 
            //- Get the triangles' points
            inline const UList<triFace>& triPoints() const;
 
            //- Get the triangles' renumbered points
            inline List<triFace> triPoints
            (
                const UList<label>& polyPoints
            ) const;
 
            //- Get a triangle's renumbered points
            inline triFace triPoints
            (
                const label trii,
                const UList<label>& polyPoints
            ) const;
 
            //- Get the triangles' edges
            inline const UList<FixedList<label, 3>>& triEdges() const;
 
            //- Get the triangles' renumbered edges
            inline List<FixedList<label, 3>> triEdges
            (
                const UList<label>& polyEdges
            ) const;
 
            //- Get a triangle's renumbered edges
            inline FixedList<label, 3> triEdges
            (
                const label trii,
                const UList<label>& polyEdges
            ) const;
 
 
        //- Perform triangulation of the given polygon
        const UList<triFace>& triangulate
        (
            const UList<point>& points,
            const vector& normal,
            const bool simple = false,
            const bool optimal = true
        );
 
        //- Perform triangulation of the given polygon
        const UList<triFace>& triangulate
        (
            const UList<point>& points,
            const bool simple = false,
            const bool optimal = true
        );
 
        //- Perform triangulation of the given polygon
        inline const UList<triFace>& triangulate
        (
            const UIndirectList<point>& points,
            const vector& normal,
            const bool simple = false,
            const bool optimal = true
        );
 
        //- Perform triangulation of the given polygon
        inline const UList<triFace>& triangulate
        (
            const UIndirectList<point>& points,
            const bool simple = false,
            const bool optimal = true
        );
 
 
    // Member Operators
 
        //- Disallow default bitwise assignment
        void operator=(const polygonTriangulate&) = delete;
};
 
 
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 
} // End namespace Foam
 
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 
#include "polygonTriangulateI.H"
 
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 
#endif
 
// ************************************************************************* //