由定比分点求折线等分点的算法 OC版

这个算法的需求是需要把已知的一系列坐标有序连接起来的折线按间距等分。

用到的数学知识点是 :

定比分点

定比分点-摘自百度百科

效果图:
示例图

图中黄点是已知的有序坐标,绿线是由黄点连接起来的折线,红点就是所求的等分点了。

此算法是我朋友写的,我把它写成了OC版然后帮助测试了一下。

声明部分:

@property (nonatomic, assign) CGFloat spacing; // 间距
@property (nonatomic, assign) CGFloat distanceSum; // 总距离的和
@property (nonatomic, assign) CGFloat surplusDistance; //上一段线段剩余的距离
@property (nonatomic, strong) NSArray *pointArr; // 折线点数组
@property (nonatomic, strong) NSMutableArray *spacingPoints; // 存放等分点的数组
@property (nonatomic, strong) NSMutableArray *distanceArr; // 存放折线中每两点间距的数组

辅助方法:

/**
 * 计算总长度
 */
- (NSMutableArray *)calculateDistanceSum:(NSArray *)points
{
    // 存放两点间间距的数组
    NSMutableArray *pointDistance = [NSMutableArray array];
    
    for (int i = 0; i < points.count - 1; i++) {
        
        CGPoint point1 = [points[i] CGPointValue];
        CGPoint point2 = [points[i+1] CGPointValue];
        
        self.distanceSum += [self calculateDistance:point1 :point2];
        [pointDistance addObject:[NSNumber numberWithDouble:[self calculateDistance:point1 :point2]]];
    }
    
    return pointDistance;
}


/**
 * 计算两点的间距
 *
 * @param point1 点A
 * @param point2 点B
 * @return 间距
 */
- (double)calculateDistance:(CGPoint)point1 :(CGPoint)point2
{
    double x = pow(point1.x - point2.x, 2);
    double y = pow(point1.y - point2.y, 2);
    
    double result = sqrt(x + y);
    
    return result;
}


/**
 * 计算λ
 *
 * @param s 折线上两点间的间距
 * @param n spacing - surplusDistance;
 * @return λ
 */
- (double)calculateLambda:(double)s :(double)n
{
    double lambda = n / (s - n);
    return lambda;
}

/**
 * 已知λ,x1,x2,计算目标坐标点x
 *
 * @param lambda λ
 * @param x1 point1 的x
 * @param x2 point2 的x
 * @return 目标点x值
 */
- (double)calculateX:(double)lambda :(double)x1 :(double)x2
{
    double x = (x1 + lambda * x2) / (1 + lambda);
    return x;
}

/**
 * 已知λ,y1,y2,计算目标坐标点y
 *
 * @param lambda λ
 * @param y1 point1 的y
 * @param y2 point2 的y
 * @return 目标点y值
 */
- (double)calculateY:(double)lambda :(double)y1 :(double)y2
{
    double y = (y1 + lambda * y2) / (1 + lambda);
    return y;
}

主要方法:

// 开始计算
// 递归,i初始值为0
// 表示折线中的第i条线段
- (void)doCalculate:(int)i
{
    CGPoint startPoint = CGPointZero;
    CGPoint endPoint   = CGPointZero;
    
    if (i < self.pointArr.count - 1) {
        startPoint = [self.pointArr[i] CGPointValue];
        endPoint   = [self.pointArr[i+1] CGPointValue];
        
        // 存在的点个数
        int pointNum = (int)(([self.distanceArr[i] doubleValue] + _surplusDistance) / self.spacing);
        
        if (pointNum > 0) {
            
            for (int j = 0; j < pointNum; j++) {
                
                double n = 0;
                double s = 0;
                
                if (j == 0) {
                    
                    n = self.spacing - _surplusDistance;
                    s = [self.distanceArr[i] doubleValue];
                } else {
            
                    n = (j + 1) * self.spacing - _surplusDistance;
                    s = [self.distanceArr[i] doubleValue];
                }
                
                if (n != s) {
                    
                    double lambda = [self calculateLambda:s :n];
                    double x = [self calculateX:lambda :startPoint.x :endPoint.x];
                    double y = [self calculateY:lambda :startPoint.y :endPoint.y];
                    
                    CGPoint newPoint = CGPointMake(x, y);
                    [self.spacingPoints addObject:[NSValue valueWithCGPoint:newPoint]];
                } else {
                    
                    [self.spacingPoints addObject:[NSValue valueWithCGPoint:endPoint]];
                }
            }
            
            // 更新剩余距离
            _surplusDistance += [self.distanceArr[i] doubleValue] - pointNum * self.spacing;
            
        } else {
            
            // 更新剩余距离
            _surplusDistance += [self.distanceArr[i] doubleValue] - pointNum * self.spacing;
        }
        
        [self doCalculate:i + 1];
    }
}

供有需要的朋友参考。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 第一章数和数的运算 一概念 (一)整数 1整数的意义 自然数和0都是整数。 2自然数 我们在数物体的时候,用来表示...
    meychang阅读 2,708评论 0 5
  • 天气转凉,一大早收到彪妈咪发来的微信,提醒添衣。 一个人在外,想把生活过得自在自得一点,可是好像每个人都被或大或小...
    丛囡囡阅读 274评论 0 0
  • 第一课:对创伤说是!每个人都带着原生的爱与创伤 找到心中那个受伤的小孩 听着冥想,想象那个受伤的小孩,小肚子就开始...
    lily北妈阅读 282评论 0 0
  • 浪费时间不如学习文学 浪费生命不如学习文学 浪费粮食不如学习文学 浪费书籍不如学习文学
    王密亮阅读 145评论 0 0
  • 你们一定听说过美人鱼的眼泪会变成珍珠,也应该熟悉吕洞宾的师傅可以“点石成金”,但是你们谁都不知道我也有一种超能力,...
    漠漠鬼话阅读 824评论 17 16