时间戳

首页 > 技术文章 > [2020 BUAA 软件工程]个人项目作业

[2020 BUAA 软件工程]个人项目作业

tuoniao 原文

[2020 BUAA 软件工程]个人项目作业
项目 内容
这个作业属于哪个课程 2020春北航计算机学院软件工程(罗杰 任健)
这个作业的要求在哪里 个人项目作业
我在这个课程的目标是 系统学习软件工程相关知识，培养自己的软件开发能力与团队协作能力，接受一定的实战锻炼
这个作业在哪个具体方面帮助我实现目标 练习个人项目开发

项目地址

  • 教学班级：006

  • 项目地址：https://github.com/blackbird52/Intersection-Calculation.git

    • 目录结构：
    Intersection-Calculation/
├── bin
│   └── intersect.exe
├── README.md
├── src
│   ├── main.cpp
│   ├── counter.cpp
│   ├── line.cpp
│   ├── intersection.h
│   ├── counter.h
│   └── line.h
└── test
    ├── pch.h
    ├── pch.cpp
    └── UnitTest.cpp

解题思路

  • 第 2 行至第 N + 1 行：每行描述一条直线。具体格式如下：
    • 直线：L ，表示通过点 (x1, y1) 和 (x2, y2) 的直线。输入保证给定两点不重合。

所有直线参数均为整数，范围为 (-100000, 100000)。

直线表示方法

根据题目所给定的信息，一条直线由线上两点表示。

为方便表示所有类型的直线，同时便于判断平行和求交点，采用直线的一般式方程来描述：

[Ax+By+C=0 ]

这里，(A, B, C) 三个量的计算方法为：

  • (A=y_2-y_1)
  • (B=x_1-x_2)
  • (C=x_2*y_1-x_1*y_2)

在这种情况下，两直线平行时：

[A_1B_2=A_2B_1 ]

两直线交点坐标：

[(frac{B_1C_2-B_2C_1}{A_1B_2-A_2B_1}, frac{A_2C_1-A_1C_2}{A_1B_2-A_2B_1}) ]

交点表示方法

根据上述的交点坐标公式，可以直接求得坐标的具体值。

但为了避免浮点数的精度问题，在中间过程中可以不直接求得具体值。

我一开始选择的方法是将余数和商分别存储，但在实现中我发现这样其实存在多余存储与计算：

  • 需要存储六个量：
    • (x) 坐标的余数、商、除数
    • (y) 坐标的余数、商、除数
  • 而坐标公式中实际只有三个量：
    • (B_1C_2-B_2C_1)
    • (A_2C_1-A_1C_2)
    • (A_1B_2-A_2B_1)

所以直接存储这三个量既免除了不必要计算，同时也节省了空间。

存储方法

选择使用集合 (set) 存储直线和交点，让集合自动去除重复元素。

判断方法

目前没有想到好的判断方法，所使用的就是暴力枚举，每枚举完一个将这条直线从集合中去除。

复杂度

因为是暴力枚举，复杂度仅能达到 (O(n^2))。

设计实现过程

本设计包含一个结构体和两个类。

交点 struct Intersection

由于交点仅需存储三个量，操作比较简单，不需要用类实现。

struct Intersection {
	int x_numerator;
	int y_numerator;
	int denominator;
};

同时为了使用 (set) 存储交点，需要重载 (<) 运算符。

bool operator <(const Intersection& s) const {
    return (this->x_numerator * s.denominator < s.x_numerator * this->denominator)
        || (this->x_numerator * s.denominator == s.x_numerator * this->denominator
            && this->y_numerator * s.denominator < s.y_numerator * this->denominator);
}

这里使用的比较方法是分数的交叉相乘。

直线 class Line

直线用一般式表示，需要存储 (A, B, C) 三个量。

class Line {
private:
	int A_;
	int B_;
	int C_;
public:
	Line(int x1, int y1, int x2, int y2);
	bool IsParallel(Line* line);
	struct Intersection* CalculateIntersection(Line* line);
};

构造函数传入两个坐标，计算出 (A, B, C)。

Line::Line(int x1, int y1, int x2, int y2) {
	this->A_ = y2 - y1;
	this->B_ = x1 - x2;
	this->C_ = x2 * y1 - x1 * y2;
}

两直线平行也直接使用公式 (A_1B_2=A_2B_1) 判断。

bool Line::IsParallel(Line* line) {
	return this->A_ * line->B_ == line->A_ * this->B_;
}

交点计算同样套用公式 ((frac{B_1C_2-B_2C_1}{A_1B_2-A_2B_1}, frac{A_2C_1-A_1C_2}{A_1B_2-A_2B_1}))，存储三个中间量。

struct Intersection* Line::CalculateIntersection(Line* line) {
	int x_numerator = this->B_ * line->C_ - line->B_ * this->C_;
	int y_numerator = line->A_ * this->C_ - this->A_ * line->C_;
	int denominator = this->A_ * line->B_ - line->A_ * this->B_;

	struct Intersection* intersection = new Intersection(x_numerator, y_numerator, denominator);
	return intersection;
}

计数器 class counter

计数器包含直线集合 (line\_set) 和交点集合 (intersection\_set)。

class Counter {
private:
	int line_count_;
	set<Line*>* line_set_;
	set<struct Intersection>* intersection_set;

public:
	Counter(ifstream& input);
	size_t CalculateIntersection();
};

将输入文件传入计数器的构造函数，完成直线集合 (line\_set) 的初始化。

Counter::Counter(ifstream& input) {
	this->line_set_ = new set<Line*>;
	this->intersection_set = new set<struct Intersection>;
	
	input >> this->line_count_;

	string type;
	int x1, y1, x2, y2;
	for (int i = 0; i < this->line_count_; i++) {
		input >> type ;

		if (type == "L") {
			input >> x1 >> y1 >> x2 >> y2;
			Line* line = new Line(x1, y1, x2, y2);
			this->line_set_->insert(line);
		} else if (type == "O") {
			// TO DO
		}
	}
}

使用 (Counter->CalculateIntersection())，在去除平行线后计算交点并存入交点集合 (intersection\_set)，自动去重，最后集合大小即为交点个数。

size_t Counter::CalculateIntersection() {
	set<Line*>::iterator iter_1 = this->line_set_->begin();

	while (iter_1!= this->line_set_->end()) {

		set<Line*>::iterator iter_2 = this->line_set_->begin();
		while (iter_2 != this->line_set_->end()) {
			if (!(*iter_1)->IsParallel(*iter_2)) {
				this->intersection_set->insert(*(*iter_1)->CalculateIntersection(*iter_2));
			}
			iter_2++;
		}

		iter_1 = this->line_set_->erase(iter_1);
	}

	return intersection_set->size();
}

改进程序性能

这是在数据量为 (5,000) 时的性能分析图，可以看出，程序中消耗最大的函数是 Counter::CalculateIntersection()。

size_t Counter::CalculateIntersection() {
    set<Line*>::iterator iter_1 = this->line_set_->begin();

    while (iter_1!= this->line_set_->end()) {

        set<Line*>::iterator iter_2 = this->line_set_->begin();
        while (iter_2 != this->line_set_->end()) {
            if (!(*iter_1)->IsParallel(*iter_2)) {
                this->intersection_set->insert(*(*iter_1)->CalculateIntersection(*iter_2));
            }
            iter_2++;
        }

        iter_1 = this->line_set_->erase(iter_1);
    }

    return intersection_set->size();
}

该函数由于包含 (O(n^2)) 的循环求交点和 (set) 更新操作，无法简化。

我曾尝试将 (set) 更换为 (unordered\_set, hasp\_map)，但是并没有明显改善。

测试

消除 Code Quality Analysis 中的所有警告

分支覆盖率


在覆盖率达到 99% 后，分析代码我发现未覆盖的语句是 (struct Intersection) 中对 (<) 的重载中，若两个 (Intersection) 相等，返回 (fsalse) 这一判断。

但是我比较奇怪的是为什么未覆盖语句是这个 (else)，在我发现已经有相等样例后也无法覆盖，于是我尝试把 (else) 删除，发现居然就 100% 了，我并没有理解这一机制。

单元测试

分别测试交点计算、平行判断、交点计数。

Line::IsParallel(Line* line)

TEST_METHOD(Line_IsParallel_1) {
    Line* line1 = new Line(1, 1, 2, 2);
    Line* line2 = new Line(3, 3, 4, 4);
    Assert::IsTrue(line1->IsParallel(line2));
}

TEST_METHOD(Line_IsParallel_2) {
    Line* line1 = new Line(1, 2, 3, 4);
    Line* line2 = new Line(2, 3, 8, 5);
    Assert::IsFalse(line1->IsParallel(line2));
}

Line::CalculateIntersection(Line* line)

TEST_METHOD(Line_CalculateIntersection) {
    Line* line1 = new Line(0, 0, 3, 3);
    Line* line2 = new Line(0, 2, 2, 0);
    Intersection* i = line1->CalculateIntersection(line2);
    Assert::AreEqual(1.0, (double)i->x_numerator / (double)i->denominator);
    Assert::AreEqual(1.0, (double)i->y_numerator / (double)i->denominator);
}

Counter::CalculateIntersection()

TEST_METHOD(Counter_CalculateIntersection_1) {
    ifstream input;
    input.open("test1.txt");
    Counter* counter = new Counter(input);
    input.close();
    Assert::AreEqual(0, (int)counter->CalculateIntersection());
}

TEST_METHOD(Counter_CalculateIntersection_2) {
    ifstream input;
    input.open("test2.txt");
    Counter* counter = new Counter(input);
    input.close();
    Assert::AreEqual(3, (int)counter->CalculateIntersection());
}

TEST_METHOD(Counter_CalculateIntersection_3) {
    ifstream input;
    input.open("test3.txt");
    Counter* counter = new Counter(input);
    input.close();
    Assert::AreEqual(1, (int)counter->CalculateIntersection());
}

TEST_METHOD(Counter_CalculateIntersection_4) {
    ifstream input;
    input.open("test4.txt");
    Counter* counter = new Counter(input);
    input.close();
    Assert::AreEqual(23, (int)counter->CalculateIntersection());
}

PSP 2.1

PSP2.1 Personal Software Process Stages 预估耗时（分钟） 实际耗时（分钟）
Planning 计划
· Estimate · 估计这个任务需要多少时间 10 10
Development 开发
· Analysis · 需求分析 (包括学习新技术) 30 60
· Design Spec · 生成设计文档 30 30
· Design Review · 设计复审 (和同事审核设计文档) 0 0
· Coding Standard · 代码规范 (为目前的开发制定合适的规范) 10 10
· Design · 具体设计 30 60
· Coding · 具体编码 60 90
· Code Review · 代码复审 60 60
· Test · 测试（自我测试，修改代码，提交修改） 120 120
Reporting 报告
· Test Report · 测试报告 20 20
· Size Measurement · 计算工作量 10 10
· Postmortem & Process Improvement Plan · 事后总结, 并提出过程改进计划 30 40
合计 400 510

推荐阅读