算法面试题：求n边形周长的k等分点坐标（今日头条）第一种写法

题目

本题来自今日头条的笔试：

有一个n边形(P0, P1, ..., Pn)， 每一条边皆为垂直或水平线段。现给定数值k，以P0为起点将n边形的周长分为k段，每段的长度相等，请打印出k等分点的坐标(T0, T1, ..., Tk）的坐标。

思路：

1. n边形肯定是偶数边，即n个点，n条边，n是偶数（没有为什么，自己琢磨）；

2. 一个回路平分k段，有k个点，k条线段，第一个点或者最后一个点就是P0；

3. 周长计算方法：

3.1. 方法1——Sum(|P(i).x - P(i).x| + |P((i+1)%n).y - P((i+1)%n).y|)(0~n)。即相邻两点边长计算；

3.2. 方法2——[Max(P(i).x) + Max(P(i).y) - Min(P(i).x) + Min(P(i).y)] * 2。这个n边型可以变型成一个规则的矩形。所以周长可以这样计算。

第一种方法：

/**
 * 随机生成多边形，n是边数
 * 有bug，随机生成的多边形会出现边和边的交叉，但不影响结果结算
 * */
function n_polygon(n){
    var points = [];
    for (var i=0, l =n;i<l;i++){
        if(i==0) {
            x = Math.round(Math.random(0, 1)*100);
            y = Math.round(Math.random(0, 1)*100);
        }
        else {
            if(i%2==1){
                y = points[i-1].y;
                x = Math.round(Math.random(0, 1)*100);
            }else{
                x = points[i-1].x;
                y = Math.round(Math.random(0, 1)*100);
            }
            if(i==l-1){
                x = points[0].x;
            }
        }
        points.push({'x': x, 'y':y});
    }
}

/**
 * 平分多段后，获取分割点的坐标
 * */
function average_perimeter(points, n){
 
    // 计算周长
    var perimeter = 0, lines = [];
    for (var i=1, l =points.length;i<=l;i++){
        _line = Math.abs(points[i-1].x - points[i%l].x) + Math.abs(points[i-1].y - points[i%l].y);
        lines.push(_line);
        perimeter += _line;
    }
    console.log(perimeter, lines);
 
    // 每条线段的长
    var line_length = perimeter / n;
    console.log(line_length);
 
    // 最终坐标
    var result_points = [];
    var _temp_line_length = line_length, diff = 0;
 
    // 在线上找到点
    for(var i=0, l = lines.length; i<l; i++){
        diff = lines[i] - _temp_line_length;
 
 
        while (diff>=0){
            // 线段的起始坐标，然后位移步长就能找到坐标。需要考虑位移是纵向还是横向
            _temp_point = {x:points[i].x, y:points[i].y};
 
            // 线段的终点
            var next = (i+1)%l;
            // 纵边
            if(points[i].x == points[next].x){
                if(points[i].y < points[next].y)
                    _temp_point.y += _temp_line_length;
                else
                    _temp_point.y -= _temp_line_length;
            }else{
                // 横边
                if(points[i].x < points[next].x)
                    _temp_point.x += _temp_line_length;
                else
                    _temp_point.x -= _temp_line_length;
            }
 
            result_points.push(_temp_point);
            diff -= line_length;
            _temp_line_length += line_length;
        }
 
        _temp_line_length = Math.abs(diff);
 
    }
 
    console.log(result_points);
    return result_points;
}

// 规范测试数据
// points = [{x: 0, y: 50}, {x: 50, y: 50}, {x: 50, y: -50}, {x: -50, y: -50}, {x: -50, y: 0},{x: 0, y: 0}];
// 随机测试数据
var points = n_polygon(6);
console.log(points);
var result_points = average_perimeter(points, 10);

后续优化代码，并补充第二种解法