| by YoungTimes | No comments

CGAL计算多边形的对称差 (Symmetric difference)

数学上,两个集合的对称差是只属于其中一个集合,而不属于另一个集合的元素组成的集合。 集合论中的这个运算相当于布尔逻辑中的异或运算。

Symmetric Difference实现

下面我们使用两个带空洞(Hole)的多边形为例,看下symmetric difference的具体实现和效果。

多边形一
多边形二

CGAL提供了symmetric_difference函数可以直接用来帮助我们实现这一功能。

先实现带空洞多边形的打印函数,方面后续调试。

template<class K>
void print_point ( CGAL::Point_2<K> const& p ) {
  std::cout << "(" << p.x() << "," << p.y() << ")" ;
}

template<class K, class C>
void print_polygon ( CGAL::Polygon_2<K,C> const& poly ) {
  typedef CGAL::Polygon_2<K,C> Polygon ;

  std::cout << "Polygon with " << poly.size() << " vertices" << std::endl ;

  for( typename Polygon::Vertex_const_iterator vi = poly.vertices_begin() ; vi != poly.vertices_end() ; ++ vi) {
    print_point(*vi); std::cout << std::endl ;
  }
}

template<class K, class C>
void print_polygon_with_holes ( CGAL::Polygon_with_holes_2<K,C> const& polywh ) {
  typedef CGAL::Polygon_with_holes_2<K,C> PolygonWithHoles ;

  std::cout << "Polygon_with_holes having " << polywh.number_of_holes() << " holes" << std::endl ;

  print_polygon(polywh.outer_boundary());

  for( typename PolygonWithHoles::Hole_const_iterator hi = polywh.holes_begin() ; hi != polywh.holes_end() ; ++ hi )
    print_polygon(*hi);
}

计算两个多边形的symmetric_difference。

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <list>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2                                   Point_2;
typedef CGAL::Polygon_2<Kernel>                           Polygon_2;
typedef CGAL::Polygon_with_holes_2<Kernel>                Polygon_with_holes_2;
typedef std::list<Polygon_with_holes_2>                   Pwh_list_2;

int main () {
  // Construct P - a bounded rectangle that contains a rectangular hole.
  Polygon_2 outP;
  Polygon_2 holesP[1];
  outP.push_back(Point_2(150, 250));
  outP.push_back(Point_2(150, 400));
  outP.push_back(Point_2(500, 400));
  outP.push_back(Point_2(500, 250));

  if (outP.orientation() != CGAL::COUNTERCLOCKWISE) {
      outP.reverse_orientation();
  }
  
  holesP[0].push_back(Point_2(240, 300));
  holesP[0].push_back(Point_2(240, 360));
  holesP[0].push_back(Point_2(400, 360));
  holesP[0].push_back(Point_2(400, 300));

  if (holesP[0].orientation() != CGAL::CLOCKWISE) {
      holesP[0].reverse_orientation();
  }
  
  Polygon_with_holes_2  P(outP, holesP, holesP + 1);
  std::cout << "P = ";
  print_polygon_with_holes(P);

  // Construct Q - a bounded rectangle that contains a rectangular hole.
  Polygon_2 outQ;
  Polygon_2 holesQ[1];
  outQ.push_back (Point_2 (250, 150));
  outQ.push_back (Point_2 (400, 150));
  outQ.push_back (Point_2 (400, 500));
  outQ.push_back (Point_2 (250, 500));

  if (outQ.orientation() != CGAL::COUNTERCLOCKWISE) {
      outQ.reverse_orientation();
  }
  
  holesQ[0].push_back(Point_2(300, 240));
  holesQ[0].push_back(Point_2(360, 240));
  holesQ[0].push_back(Point_2(360, 400));
  holesQ[0].push_back(Point_2(300, 400));
  if (holesQ[0].orientation() != CGAL::CLOCKWISE) {
      holesQ[0].reverse_orientation();
  }
  
  Polygon_with_holes_2  Q(outQ, holesQ, holesQ + 1);
  std::cout << "Q = ";
  print_polygon_with_holes(Q);

  // Compute the symmetric difference of P and Q.
  Pwh_list_2 symmR;
  Pwh_list_2::const_iterator it;
  CGAL::symmetric_difference(P, Q, std::back_inserter(symmR));

  std::cout << "The symmetric difference:" << std::endl;
  for (it = symmR.begin(); it != symmR.end(); ++it) {
    std::cout << "--> ";
    print_polygon_with_holes(*it);
  }

  return 0;
}

g++编译代码:

g++ difference.cpp -std=c++11  -Wall -pedantic -lCGAL -lCGAL_Core -lmpfr -lgmp -pthread  && ./a.out

程序打印结果如下:

The symmetric difference:
--> Polygon_with_holes having 7 holes
Polygon with 12 vertices
(250,500)
(250,400)
(150,400)
(150,250)
(250,250)
(250,150)
(400,150)
(400,250)
(500,250)
(500,400)
(400,400)
(400,500)
Polygon with 4 vertices
(300,400)
(300,360)
(250,360)
(250,400)
Polygon with 4 vertices
(300,300)
(300,250)
(250,250)
(250,300)
Polygon with 4 vertices
(250,360)
(250,300)
(240,300)
(240,360)
Polygon with 4 vertices
(360,360)
(360,300)
(300,300)
(300,360)
Polygon with 4 vertices
(360,250)
(360,240)
(300,240)
(300,250)
Polygon with 4 vertices
(400,300)
(400,250)
(360,250)
(360,300)
Polygon with 4 vertices
(400,400)
(400,360)
(360,360)
(360,400)

为了方便结果直观核验,做个可视化,效果如下:

附上可视化的Python代码:

import cv2
import numpy as np

image = np.ones((1000, 1000,3), np.uint8) * 180

points = np.array([[250, 500], [250, 400], [150, 400], [150, 250], [250, 250], [250, 150], [400, 150],
[400, 250], [500, 250], [500, 400], [400, 400], [400, 500]], np.int32)
inners_1 = np.array([[300, 400], [300, 360], [250, 360], [250, 400]], np.int32)
inners_2 = np.array([[300, 300], [300, 250], [250, 250], [250, 300]], np.int32)
inners_3 = np.array([[250, 360], [250, 300], [240, 300], [240, 360]], np.int32)
inners_4 = np.array([[360, 360], [360, 300], [300, 300], [300, 360]], np.int32)
inners_5 = np.array([[360, 250], [360, 240], [300, 240], [300, 250]], np.int32)
inners_6 = np.array([[400, 300], [400, 250], [360, 250], [360, 300]], np.int32)
inners_7 = np.array([[400, 400], [400, 360], [360, 360], [360, 400]], np.int32)


cv2.fillPoly(image, [points], (180, 120, 0))
cv2.fillPoly(image, [inners_1], (255, 255, 255))
cv2.fillPoly(image, [inners_2], (255, 255, 255))
cv2.fillPoly(image, [inners_3], (255, 255, 255))
cv2.fillPoly(image, [inners_4], (255, 255, 255))
cv2.fillPoly(image, [inners_5], (255, 255, 255))
cv2.fillPoly(image, [inners_6], (255, 255, 255))
cv2.fillPoly(image, [inners_7], (255, 255, 255))


cv2.imshow('image',image)

while True:
    if cv2.waitKey() & 0xFF == ord('q'):
        print("I'm done")
        break

参考材料

https://zh.wikipedia.org/wiki/%E5%AF%B9%E7%A7%B0%E5%B7%AE

https://doc.cgal.org/latest/Boolean_set_operations_2/Boolean_set_operations_2_2symmetric_difference_8cpp-example.html

发表评论