海康威视 U3D客户端开发 一面

1. 自我介绍和项目介绍

2.怎么判断一个点在凸多边形里面

答案：如果是凸多边形，最常见的方法就是判断这个点是否始终在每一条边的同一侧。具体做法是依次计算多边形每条边和目标点构成的叉积，如果所有叉积同号，说明点在凸多边形内部；如果有正有负，说明点在外部。这种方法的好处是实现简单，时间复杂度是 O(n)，很适合面试时手写。

代码：

#include <vector>
using namespace std;

struct Point {
    double x, y;
};

double cross(const Point& a, const Point& b, const Point& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

bool isPointInConvexPolygon(const vector<Point>& poly, const Point& p) {
    int n = poly.size();
    if (n < 3) return false;

    double prev = 0;
    for (int i = 0; i < n; ++i) {
        double cur = cross(poly[i], poly[(i + 1) % n], p);
        if (cur != 0) {
            if (prev != 0 && cur * prev < 0) return false;
            prev = cur;
        }
    }
    return true;
}

3. 怎么判断一个点在平面多边形里面

答案：如果题目没有强调是凸多边形，那通常默认是普通多边形。这时候最常见的方法是射线法。从目标点向一个固定方向引一条射线，统计它和多边形边的交点个数。如果交点个数是奇数，说明点在多边形内部；如果是偶数，说明点在外部。这种方法实现比较通用，但要注意边界情况，比如点刚好在边上、射线经过顶点、水平边重复统计这些问题。

代码：

#include <vector>
#include <algorithm>
using namespace std;

struct Point {
    double x, y;
};

bool onSegment(const Point& a, const Point& b, const Point& p) {
    double cross = (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x);
    if (cross != 0) return false;
    return p.x >= min(a.x, b.x) && p.x <= max(a.x, b.x) &&
           p.y >= min(a.y, b.y) && p.y <= max(a.y, b.y);
}

bool isPointInPolygon(const vector<Point>& poly, const Point& p) {
    int n = poly.size();
    bool inside = false;

    for (int i = 0, j = n - 1; i < n; j = i++) {
        if (onSegment(poly[j], poly[i], p)) return true;

        bool intersect = ((poly[i].y > p.y) != (poly[j].y > p.y)) &&
                         (p.x < (poly[j].x - poly[i].x) * (p.y - poly[i].y) /
                                    (poly[j].y - poly[i].y) + poly[i].x);
        if (intersect) inside = !inside;
    }
    return inside;
}

4. Protobuf 和 JSON 的区别

答案：这两个本质上都是数据序列化方式，但特点不一样。JSON 是