图形/多段线内缩外扩思路

图形/多段线内缩外扩思路

前言

我在网上找了很多关于多边形内缩外扩的资料，也测试了一些算法库，如Clipper，boost::geometry::buffer，其实都可以得到不错的结果。

Clipper

• 例程

#include "clipper.hpp"   
... 
using namespace ClipperLib; 
  
int main() 
{ 
  Path subj; 
  Paths solution; 
  subj <<  
    IntPoint(348,257) << IntPoint(364,148) << IntPoint(362,148) <<  
    IntPoint(326,241) << IntPoint(295,219) << IntPoint(258,88) <<  
    IntPoint(440,129) << IntPoint(370,196) << IntPoint(372,275); 
  ClipperOffset co; 
  co.AddPath(subj, jtRound, etClosedPolygon); 
  co.Execute(solution, -7.0); 
    
  //draw solution ... 
  DrawPolygons(solution, 0x4000FF00, 0xFF009900); 
}

• 效果

  
  

boost::geometry::buffer

• 例程

#include 
#include 
#include 


int main()
{
    typedef double coordinate_type;
    typedef boost::geometry::model::d2::point_xy<coordinate_type> point;
    typedef boost::geometry::model::polygon<point> polygon;

    // Declare strategies
    const double buffer_distance = 1.0;
    const int points_per_circle = 36;
    boost::geometry::strategy::buffer::distance_symmetric<coordinate_type> distance_strategy(buffer_distance);
    boost::geometry::strategy::buffer::join_round join_strategy(points_per_circle);
    boost::geometry::strategy::buffer::end_round end_strategy(points_per_circle);
    boost::geometry::strategy::buffer::point_circle circle_strategy(points_per_circle);
    boost::geometry::strategy::buffer::side_straight side_strategy;

    // Declare output
    boost::geometry::model::multi_polygon<polygon> result;

    // Declare/fill a linestring
    boost::geometry::model::linestring<point> ls;
    boost::geometry::read_wkt("LINESTRING(0 0,4 5,7 4,10 6)", ls);

    // Create the buffer of a linestring
    boost::geometry::buffer(ls, result,
                distance_strategy, side_strategy,
                join_strategy, end_strategy, circle_strategy);


    // Declare/fill a multi point
    boost::geometry::model::multi_point<point> mp;
    boost::geometry::read_wkt("MULTIPOINT((3 3),(4 4),(6 2))", mp);

    // Create the buffer of a multi point
    boost::geometry::buffer(mp, result,
                distance_strategy, side_strategy,
                join_strategy, end_strategy, circle_strategy);


    // Declare/fill a multi_polygon
    boost::geometry::model::multi_polygon<polygon> mpol;
    boost::geometry::read_wkt("MULTIPOLYGON(((0 1,2 5,5 3,0 1)),((1 1,5 2,5 0,1 1)))", mpol);

    // Create the buffer of a multi polygon
    boost::geometry::buffer(mpol, result,
                distance_strategy, side_strategy,
                join_strategy, end_strategy, circle_strategy);


    return 0;
}

• 效果

  
  
  
  

遇到的问题

我现在得到的图形是经过反向解析文件再生成的，每个点位都是包含了一些信息，原始的点位个数和顺序是不可以轻易被改变的，而且图形也不一定是封闭的，其组成是可能带圆弧的多段线，后面再生成的文件还得和原始图形的点位顺序对应上才行。而以上两种处理库，是会改变点传入点位的个数和顺序的，这样的结果并不能正确生成理想的文件，就是这个问题让我很是头疼。

后来尝试找些几何理论的资料来解决，而网上的不少资料都是通过向量的方式来求夹角的，在出现内缩到一定程度，会有自交的情况，需要自己跳过垂直平行重复的点位，显然这也不是我想要的结果。

• 参考资料
  • 多边形扩展或收缩算法
  • 多边形扩展和收缩(凸多边形和凹多边形)
  • 多边形轮廓等距外扩
  • 实现凹凸多边形外扩与内缩, 无内缩外扩混乱问题

抛砖引玉

期间想到可以用直线段按照斜率平移的方法来处理，内缩的情况是相邻两线段的交点就是图形新的顶点，而拐角是圆弧的时候，判断圆弧两边的线段平移后有没有交点来决定要不要移除。当然这个办法显然比较笨，但是得到的图形顶点顺序和个数是可控的，也能让我如愿与原始的点位所带的信息对应上。

这里只是记录了思路，具体代码实现省略。附带直线的相关知识。

• 直线的倾斜角与斜率、直线的方程
• c++实现：知道一条线的起点和终点，如何求出固定距离（lz）平行线的起点和终点
• c++求两条直线的交点

可以参考大神的实现方法

jbuckmccready/CavalierContours

最后

感谢各位大佬的无私奉献。