Polygon Clipping, Boolean Operations – Example5

Boolean Operations on Polygons

Fade provides polygon clipping and functions to combine polygons through the boolean operations:

  • Union (A OR B)
  • Intersection (A AND B)
  • Difference (A NOT B)
  • Symmetric Difference (A XOR B)

The demo source code described below is contained in the example5.cpp file in the Fade2D download.

Creating two Shapes (Zones)

A Zone represents a polygonal area in a triangulation. We set up two (intersecting) polygons:

  • Four bounding box points are inserted (just to improve the visual appearance)
  • Two vectors of Segment2 objects (intersecting shapes) are created
  • Two ConstraintGraph2 objects are made
  • Two Zone2 objects are made
	

    // * 1 *   Insert 4 bounding box points around the data
    //         Not necessary, just to get a nicer visualization
    Fade_2D dt;
    dt.insert(Point2(-100,-100));
    dt.insert(Point2(+100,-100));
    dt.insert(Point2(+100,+270));
    dt.insert(Point2(-100,+270));

    // * 2 *   Prepare two vectors of Segments
    int numPoints(10);
    std::vector<Point2> vConstraintPoints0;
    std::vector<Point2> vConstraintPoints1;
    generateCircle(numPoints,0,150,80,80,vConstraintPoints0);
    generateCircle(numPoints,0,40,60,130,vConstraintPoints1);

    std::vector<Segment2> vSegments1;
    std::vector<Segment2> vSegments2;
    for(size_t i=0;i<vConstraintPoints0.size();++i)
    {
        Point2& p0(vConstraintPoints0[i]);
        Point2& p1(vConstraintPoints0[(i+1)%vConstraintPoints0.size()]);
        vSegments1.push_back(Segment2(p0,p1));

        Point2& p2(vConstraintPoints1[i]);
        Point2& p3(vConstraintPoints1[(i+1)%vConstraintPoints1.size()]);
        vSegments2.push_back(Segment2(p2,p3));
    }

    // * 3 *   Use the segments to create two ConstraintGraphs. 
    ConstraintGraph2* pCG1=dt.createConstraint(vSegments1,CIS_CONSTRAINED_DELAUNAY);
    ConstraintGraph2* pCG2=dt.createConstraint(vSegments2,CIS_CONSTRAINED_DELAUNAY);
    dt.show("example5_constraints.ps");

    // Make sure pCG1 and pCG2 are closed
    if(!pCG1->isPolygon() || !pCG2->isPolygon() )
    {
        std::cout<<"pCG1 and pCG2 must be closed polygons, stop"<<std::endl;
        return 1;
    }

    // * 4 *   Create two Zone2 objects using ZL_INSIDE:
    Zone2* pZone0(dt.createZone(pCG1,ZL_INSIDE));
    pZone0->show("example5_zone0.ps",true,true); // all triangles=true, show constraints=true

    Zone2* pZone1(dt.createZone(pCG2,ZL_INSIDE));
    pZone1->show("example5_zone1.ps",true,true);

Below the intersecting polygons and the two zones are shown.

Two intersecting Polygons

Two intersecting Polygons


Shape0

Zone0


Shape1

Zone1

NOTE: For boolean operations both Zone2 objects must belong to the same Fade_2D object.

Boolean operations with polygons (zones)

Once the two Zones have been made a boolean operation is carried out with just one more line of code. See the result images below:

	//    a) Union operation
	Zone2* pZoneUnion(zoneUnion(pZone0,pZone1));

	//    b) Intersection operation
	Zone2* pZoneIntersection(zoneIntersection(pZone0,pZone1));

	//    c) Difference operation
	Zone2* pZoneDifference(zoneDifference(pZone0,pZone1));

	//    d) Symmetric Difference operation
	Zone2* pZoneSymDifference(zoneSymmetricDifference(pZone0,pZone1));
Boolean operations: Union of two intersecting shapes

Union


Boolean operations: Intersection of two Shapes

Intersection


Boolean operations: Difference of two Shapes

Difference


Boolean operations: Symmetric Difference of two intersecting Shapes

Symmetric Difference


Extracting triangles and Border Polygons

The triangles of a Zone2 object can be conveniently extracted using Zone2::getTriangles() while Zone2::getBorderEdges() can be used to extract a vector of border edges. Edge2 objects are always counterclockwise oriented with respect to their triangle but Zone2::getBorderEdges() does not deliver them in a specific order, thus they do not form a polygon yet. The code below demonstrates how to use the function edgesToPolygons() to extract polygons.

    // * 6 *   Retrieve the border edges of pZoneSymmetricDifference
    vector<Edge2> vBorders;
    pZoneSymmetricDifference->getBorderEdges(vBorders);
    Visualizer2 v("example5_symDiffBorders.ps");
    dt.show(&v,false); // show only the triangles
    v.addObject(vBorders,Color(CGREEN,0.5,true));
    v.writeFile();

    // * 7 *   Turn the border edges into polygons
    vector<Edge2> vRemainingEdges;
    vector<vector<Edge2> > vvEdges;
    edgesToPolygons(vBorders,vvEdges,vRemainingEdges);
    assert(vRemainingEdges.empty()); // All edges belong to polygons

    // * 8 *   Draw
    Visualizer2 polyVis("example5_polygons.ps");
    pZoneSymmetricDifference->show(&polyVis,false,false); // show only the triangles
    for(size_t poly=0;poly<vvEdges.size();++poly)
    {
        const vector<Edge2>& vPolygon(vvEdges[poly]);
        Color c(Color::getNextColorName(),1.0,false); // Next color from a (repeating) sequence
        for(size_t j=0;j<vPolygon.size();++j)
        {
            const Edge2& edge(vPolygon[j]);
            polyVis.addObject(edge,c);

            Point2* pSourcePoint(edge.getSrc());
            Label lab(*pSourcePoint,toString(j),true,16);
            polyVis.addObject(lab,c);
        }
    }
    polyVis.writeFile();



Border Polygons of a Shape with Holes

The two border polygons of the symmetric difference zone: The edges are CCW oriented with respect to the border triangle, therefore the outer polygon is CCW ordered while the inner one is CW ordered

This post has shown how to combine polygonal areas through set operations and how to extract the boundary polygons of the resulting area. But Zone2 objects can also be defined in order to create high quality triangular meshes. See Example6 – Mesh Generation and the article about Advanced Mesh Generation.

Spread the word. Share this post!

4 Comments

  1. Reply Boris

    Good day. My name is Boris, I am a student from Moscow Institute of Physics and Technology. It would be really cool if you could help me with the following situation:

    In your example above you define coordinates of points of one polygon like coordinates of points of another polygon plus 90 and as a result, we have two intersecting polygons where all intersecting segments intersect only at one point. And everything is going fine. But if I change 90 to 60 everything is change and two leftmost segments start to intersect in infinite amount of points. Triangulation is still going fine but problem occurs when I try to call getBorderEdges() method of an pZoneUnion object. It writes values to std::vector in a wrong order and resulting figure doesn’t have any similarity with one I am waiting for. So the question is: Did I miss some functionality to solve this situation? And if I didn’t is there some way to solve it?

    • Reply Bernhard Kornberger

      Dear Boris,

      The documentation of getBorderEdges() says that the edges are CCW oriented, i.e. they point in counterclockwise direction but they are NOT necessarily ordered. I admit, this is misleading. Next week a new version will be released and then this issue will be solved. However, visualization works when you add this code to example5.cpp:

      std::vector vBorderEdges;
      pZoneUnion->getBorderEdges(vBorderEdges);
      vector vSegments;
      for(std::vector::iterator it(vBorderEdges.begin());it!=vBorderEdges.end();++it)
      {
      Edge2& e(*it);
      Point2* p1;
      Point2* p2;
      e.getPoints(p1,p2);
      vSegments.push_back(Segment2(*p1,*p2));
      }
      Visualizer2 vis(“borders.ps”);
      vis.addObject(vSegments,Color(CGREEN));
      vis.writeFile();

      Union of shapes and its border edges

      It shows the the correct border of the union of the two shapes. If you need the segments in the right order, please use the sortRing function from freeFunctions.h.

      hth

  2. Reply Boris

    Dear Bernhard,

    thank you! Your answer helped me very much. Now I have another problem and I try to find a way of solving it. I want to find a union of two nonconvex polygons and it’s possible that some number of holes will appear inside this union. Awesome getBoundarySegments() method in combination with sortRing() method properly return outer circuit. But is there some way to find circuits of holes inside this union?

    Thank you,
    Boris

    • Reply Bernhard Kornberger

      Dear Boris,

      Yes. A new release was due anyway and I have added that feature. Please download Fade2D v1.58. Extract the edges of the union zone using Zone2::getBoundaryEdges() and then use the edgesToPolygons() function to organize these edges as polygons. I have added demo code to example5.cpp, see also the description above (added right now) and the Documentation of edgesToPolygons

Leave A Reply

Your email address will not be published. Required fields are marked *

*

By continuing to use the site, you agree to the use of cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close