# trilaterate

**Repository Path**: runningcircle/trilaterate

## Basic Information

- **Project Name**: trilaterate
- **Description**: 一个通过三边定位算法计算二维平面上未知点坐标的程序。基于三个已知参考点的坐标及未知点到各参考点的直线距离，求解满足条件的未知点坐标集合。
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2025-04-26
- **Last Updated**: 2025-06-17

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 三边定位算法

## 项目简介
本项目实现了一个基于三边定位原理的算法，用于计算二维平面上未知点的精确坐标。通过已知三个参考点的坐标以及未知点到这三个参考点的距离，可以求解未知点的坐标。

此算法常用于GPS定位、室内导航、无线传感器网络定位等领域。

## 算法原理
三边定位法基于几何圆交点的原理工作：
1. 以三个已知点为圆心
2. 以未知点到各已知点的距离为半径作圆
3. 三个圆的交点即为未知点位置

在理想情况下，三个圆会在一个点相交。但在实际应用中，由于测量误差，可能会出现无解、唯一解或两个解的情况。此实现使用了最小二乘法处理无解情况，提高了算法的鲁棒性。

## 核心功能
- 计算二维平面上未知点的坐标
- 自动处理测量误差（允许±0.1%的距离误差容限）
- 支持多解情况判断与处理（无解/一个解/两个解）
- 使用最小二乘法优化无解情况
- 完善的异常处理机制
- 提供交互式用户界面
- 内置单元测试

## 使用方法

### 编译
```bash
g++ -std=c++11 -o localization LocalizationAlgorithm.cpp
```

### 运行
```bash
./localization
```

### 交互式使用
程序启动后，按照提示输入三个参考点的坐标和距离：
1. 输入第一个参考点的x坐标、y坐标和距离（用空格分隔）
2. 输入第二个参考点的x坐标、y坐标和距离
3. 输入第三个参考点的x坐标、y坐标和距离
4. 程序计算并显示结果
5. 根据提示选择是否继续计算

### 作为函数库使用
可以将核心函数`trilaterate`集成到其他项目中：

```cpp
// 函数签名
vector<Point> trilaterate(
    double x1, double y1, double d1,  // 第一个参考点坐标和距离
    double x2, double y2, double d2,  // 第二个参考点坐标和距离
    double x3, double y3, double d3   // 第三个参考点坐标和距离
);

// 返回值是可能解的集合，可能包含0个、1个或2个解
```

## 输入输出规范

### 输入参数
- 三个参考点的坐标：(x1, y1), (x2, y2), (x3, y3)
- 未知点到各参考点的距离：d1, d2, d3

### 输出结果
- 无解情况：返回空集合
- 一个解：返回包含一个点的集合
- 两个解：返回包含两个点的集合
- 坐标值自动保留四位小数
- 当存在多个解时，按x坐标升序排列，若x坐标相同则按y坐标升序排列

## 技术实现细节
- 采用C++14标准
- 使用lambda表达式简化代码
- 浮点数计算误差阈值设置为1e-6
- 距离测量误差容限为0.1%
- 使用向量和元组提高代码可读性
- 完整的输入验证和边界条件处理
- 几何退化情况的特殊处理

## 算法优化
1. **前处理**：验证所有输入数据的有效性
2. **几何求解**：基于前两个圆的交点计算
3. **验证**：使用第三个圆筛选有效解
4. **后处理**：
   - 去重处理
   - 当交点不存在时使用最小二乘法优化
   - 结果排序

## 单元测试
项目内置了单元测试，用于验证算法的正确性：
1. 标准情况（唯一解）
2. 两个解的情况
3. 无解情况