* 给你三个点，怎么计算三个夹角的角度？
思路：用点积除叉积
python：
import numpy as np
def angle_between(v1, v2):
"""Returns the angle in radians between vectors 'v1' and 'v2'"""
cosang = np.dot(v1, v2)
sinang = np.linalg.norm(np.cross(v1, v2))
return np.arctan2(sinang, cosang)
def calculate_angle(p1, p2, p3):
"""Calculate the angle at p2"""
v1 = np.array(p1) - np.array(p2)
v2 = np.array(p3) - np.array(p2)
return angle_between(v1, v2)
p1 = [1, 0]
p2 = [0, 0]
p3 = [0, 1]
print(calculate_angle(p1, p2, p3))C++
#include <cmath>
#include <iostream>
#include <vector>
struct Point {
double x, y, z;
};
double dot_product(Point a, Point b) {
return a.x * b.x + a.y * b.y + a.z * b.z;
}
Point cross_product(Point a, Point b) {
return {a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x};
}
double norm(Point a) {
return std::sqrt(a.x * a.x + a.y * a.y + a.z * a.z);
}
double angle_between(Point a, Point b) {
double cosang = dot_product(a, b);
double sinang = norm(cross_product(a, b));
return std::atan2(sinang, cosang);
}
Point subtract(Point a, Point b) {
return {a.x - b.x, a.y - b.y, a.z - b.z};
}
double calculate_angle(Point p1, Point p2, Point p3) {
Point v1 = subtract(p1, p2);
Point v2 = subtract(p3, p2);
return angle_between(v1, v2);
}
int main() {
Point p1 = {1, 0, 0};
Point p2 = {0, 0, 0};
Point p3 = {0, 1, 0};
std::cout << calculate_angle(p1, p2, p3) << std::endl;
return 0;
}
* 输入一个凸包的所有顶点，返回排序好的点顺序。（按凸包顺序连接）
思路：①计算质心，②计算每个点与质心的夹角，③按照夹角排序，返回的即为凸包连接
python实现：
import numpy as np
def convex_hull(points):
# 计算质心
center = np.mean(points, axis=0)
# 计算每个点相对于质心的角度
angles = np.arctan2(points[:,1] - center[1], points[:,0] - center[0])
# 对角度进行排序，得到排序后的索引
indices = np.argsort(angles)
# 返回排序后的点
return points[indices]
points = np.array([[0, 0], [1, 0], [0, 1], [1, 1], [0.5, 0.5]])
print(convex_hull(points))C++实现：
#include <algorithm>
#include <vector>
#include <cmath>
struct Point {
double x, y;
};
Point center; // 定义全局变量center，表示质心
// 计算两点之间的角度
double angle(Point a, Point b) {
return atan2(b.y - a.y, b.x - a.x);
}
// 比较函数，用于排序
bool compare(Point a, Point b) {
return angle(center, a) < angle(center, b);
}
std::vector<Point> convexHull(std::vector<Point>& points) {
// 计算质心
center = {0, 0};
for (Point p : points) {
center.x += p.x;
center.y += p.y;
}
center.x /= points.size();
center.y /= points.size();
// 根据每个点相对于质心的角度进行排序
std::sort(points.begin(), points.end(), compare);
return points;
}
int main() {
std::vector<Point> points = {{0, 0}, {1, 0}, {0, 1}, {1, 1}, {0.5, 0.5}};
std::vector<Point> hull = convexHull(points);
for (Point p : hull) {
std::cout << "(" << p.x << ", " << p.y << ")" << std::endl;
}
return 0;
}
* 如何计算两个凸包的iou，输入为两堆点
思路：
- 首先，我们需要确保输入的点集是有序的，这样我们可以使用Graham扫描或其他方法构建凸包。
- 然后，我们需要计算两个凸包的交集。这可以通过计算每个凸包的所有边与另一个凸包的交点，然后将这些交点与两个凸包的顶点合并，再次构建凸包来实现。
- 计算两个凸包的并集。这可以通过将两个凸包的所有顶点合并，然后构建凸包来实现。
- 最后，我们计算交集和并集的面积，然后用交集的面积除以并集的面积，得到IoU。
from shapely.geometry import Polygon
def compute_iou(points1, points2):
# 构建凸包
hull1 = Polygon(convex_hull(points1))
hull2 = Polygon(convex_hull(points2))
# 计算交集和并集
intersection = hull1.intersection(hull2)
union = hull1.union(hull2)
# 计算IoU
iou = intersection.area / union.area
return iou
points1 = np.array([[0, 0], [1, 0], [0, 1], [1, 1], [0.5, 0.5]])
points2 = np.array([[0.5, 0.5], [1.5, 0.5], [0.5, 1.5], [1.5, 1.5], [1, 1]])
print(compute_iou(points1, points2))
* 如何计算三角形的面积，输入三个点。（或四边形面积）
利用向量积（叉积）计算三角形的面积和多边形的面积 - NGUper - 博客园
python实现：
import numpy as np
def triangle_area(A, B, C):
AB = B - A
AC = C - A
return 0.5 * np.linalg.norm(np.cross(AB, AC))
def quadrilateral_area(A, B, C, D):
return triangle_area(A, B, C) + triangle_area(A, C, D)
A = np.array([0, 0, 0])
B = np.array([1, 0, 0])
C = np.array([1, 1, 0])
D = np.array([0, 1, 0])
print(quadrilateral_area(A, B, C, D))C++实现：
#include <Eigen/Dense>
#include <iostream>
double triangleArea(const Eigen::Vector3d& A, const Eigen::Vector3d& B, const Eigen::Vector3d& C) {
Eigen::Vector3d AB = B - A;
Eigen::Vector3d AC = C - A;
return 0.5 * AB.cross(AC).norm();
}
double quadrilateralArea(const Eigen::Vector3d& A, const Eigen::Vector3d& B, const Eigen::Vector3d& C, const Eigen::Vector3d& D) {
return triangleArea(A, B, C) + triangleArea(A, C, D);
}
int main() {
Eigen::Vector3d A(0, 0, 0);
Eigen::Vector3d B(1, 0, 0);
Eigen::Vector3d C(1, 1, 0);
Eigen::Vector3d D(0, 1, 0);
std::cout << quadrilateralArea(A, B, C, D) << std::endl;
return 0;
}
// 如果用的是cv::Point3d（cv::Point3d A_cv(0, 0, 0);），可以先转成Eigen::Vector3d
// Eigen::Vector3d A(A_cv.x, A_cv.y, A_cv.z);
// Eigen::Vector3d A(v[0], v[1], v[2]); // vector 转 Eigen::Vector3d
* 计算任意多边形的面积
思路：①类似凸包进行排列，②依次取两个点与原点计算外积/2，③将所有的面积加起来
python 实现：
import numpy as np
def polygon_area(points):
area = 0
for i in range(len(points)):
j = (i + 1) % len(points)
area += points[i][0] * points[j][1] # 相当于与0,0构成的面积
area -= points[j][0] * points[i][1] # (a1, a2)和(b1, b2)的外积为a1b2 - a2b1
area = abs(area) / 2.0
return area
points = np.array([[0, 0], [1, 0], [1, 1], [0, 1]])
print(polygon_area(points))C++实现：
#include <vector>
#include <cmath>
struct Point {
double x, y;
};
double polygon_area(const std::vector<Point>& points) {
double area = 0;
for (size_t i = 0; i < points.size(); ++i) {
size_t j = (i + 1) % points.size();
area += points[i].x * points[j].y;
area -= points[j].x * points[i].y;
}
area = std::abs(area) / 2.0;
return area;
}
int main() {
std::vector<Point> points = { {0, 0}, {1, 0}, {1, 1}, {0, 1} };
std::cout << polygon_area(points) << std::endl;
return 0;
}
NMS算法实现
非极大值抑制(Non-Maximum Suppression, NMS), 顾名思义就是抑制那些不是极大值的元素, 可以理解为局部最大值搜索. 对于目标检测来说, 非极大值抑制的含义就是对于重叠度较高的一部分同类候选框来说,
去掉那些置信度较低的框, 只保留置信度最大的那一个进行后面的流程, 这里的重叠度高低与否是通过 NMS 阈值来判断的.
struct Bbox {
int x1;
int y1;
int x2;
int y2;
float score;
}
float iou (Bbox box1, Box box2){
int x1 = std::max(box1.x1, box2.x1);
int y1 = std::max(box1.y1, box2.y1);
int x2 = std::min(box1.x2, box2.x2);
int y2 = std::min(box1.y2, box2.y2);
int w = std::max(0, x2 - x1 + 1); // 为什么要加一，0~2代表0，1，2三个像素点
int h = std::max(0, y2 - y1 + 1);
int inter = w * h;
int area1 = (box1.x2 - box1.x1 + 1) * (box1.y2 - box1.y1 + 1);
int area2 = (box2.x2 - box2.x1 + 1) * (box2.y2 - box2.y1 + 1);
return (float)(inter/(area1 + area2 - inter))
}
std::vector<Bbox> nms(std::vector<Bbox> &vecBbox, float threshold){
std::vector<Bbox> res;
std::sort(vecBbox.begin(), vecBbox.end(),[](Bbox a, Bbox b){
return a.score > b.score;
})
while(vecBbox.size()>0){
res.push_back(vecBbox[0]);
vecBbox.erase(vecBbox.begin());
for (auto it = vecBbox.begin(); it != vecBbox.end();){
if (iou(res.back(), *it) > threshold){
it = vecBbox.erase(it);
}
else ++it;
}
}
return res;
}
softmax层的实现
考虑下数值计算较大时，如何避免溢出问题。
using namespace std;
int activation_function_softmax(const float* src, float* dst, int length){
float max_val = *std::max_element(src, src + length);
std::vector<float> eps(length);
for (int i = 0; i < length; ++i){
eps[i] = std::exp(src[i] - max_val);
}
float sum = std::accumulate(eps.begin(), eps.end());
for (int i = 0; i < length; ++i){
dst[i] = eps[i]/sum;
}
}
3D IOU
# 3D IOU 计算
def boxes_iou3d_gpu(boxes_a, boxes_b):
"""
Args:
boxes_a: (N, 7) [x, y, z, dx, dy, dz, heading]
boxes_b: (N, 7) [x, y, z, dx, dy, dz, heading]
Returns:
ans_iou: (N, M)
"""
assert boxes_a.shape[1] == boxes_b.shape[1] == 7
# height overlap
boxes_a_height_max = (boxes_a[:, 2] + boxes_a[:, 5] / 2).view(-1, 1)
boxes_a_height_min = (boxes_a[:, 2] - boxes_a[:, 5] / 2).view(-1, 1)
boxes_b_height_max = (boxes_b[:, 2] + boxes_b[:, 5] / 2).view(1, -1)
boxes_b_height_min = (boxes_b[:, 2] - boxes_b[:, 5] / 2).view(1, -1)
# bev overlap
overlaps_bev = torch.cuda.FloatTensor(torch.Size((boxes_a.shape[0], boxes_b.shape[0]))).zero_() # (N, M)
iou3d_nms_cuda.boxes_overlap_bev_gpu(boxes_a.contiguous(), boxes_b.contiguous(), overlaps_bev)
max_of_min = torch.max(boxes_a_height_min, boxes_b_height_min)
min_of_max = torch.min(boxes_a_height_max, boxes_b_height_max)
overlaps_h = torch.clamp(min_of_max - max_of_min, min=0)
# 3d iou
overlaps_3d = overlaps_bev * overlaps_h
vol_a = (boxes_a[:, 3] * boxes_a[:, 4] * boxes_a[:, 5]).view(-1, 1)
vol_b = (boxes_b[:, 3] * boxes_b[:, 4] * boxes_b[:, 5]).view(1, -1)
iou3d = overlaps_3d / torch.clamp(vol_a + vol_b - overlaps_3d, min=1e-6)
return iou3d
找到a[index] = index的索引
#include <iostream>
#include <vector>
int find_fixed_point(const std::vector<int>& nums) {
int low = 0, high = nums.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == mid) {
return mid;
} else if (nums[mid] < mid) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // 如果没有找到满足条件的index，返回-1
}
int main() {
std::vector<int> nums = {-10, -5, 2, 2, 2, 3, 4, 7, 9, 12, 13};
int index = find_fixed_point(nums);
if (index != -1) {
std::cout << "Fixed point is at index " << index << std::endl;
} else {
std::cout << "No fixed point found in the array." << std::endl;
}
return 0;
}
// 如果要找到全部 index
std::vector<int> find_fixed_points(const std::vector<int>& nums) {
std::vector<int> result;
int n = nums.size();
for (int i = 0; i < n; ++i) {
if (nums[i] == i) {
result.push_back(i);
}
}
return result;
}