c++ 点到多边形的距离

目录

判断点是否在多边形内

点到多边形距离

判断点是否在多边形内

#include <vector>
 
struct Point {
    double x, y;
};
 
bool isPointInPolygon(const Point &p, const std::vector<Point> &polygon) {
    bool result = false;
    int j = polygon.size() - 1;
    for (int i = 0; i < polygon.size(); i++) {
        if ((polygon[i].y > p.y) != (polygon[j].y > p.y) &&
            (p.x < (polygon[j].x - polygon[i].x) * (p.y - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x)) {
            result = !result;
        }
        j = i;
    }
    return result;
}
 
int main() {
    // 定义多边形顶点，多边形顶点需按顺序（顺时针或逆时针）定义
    std::vector<Point> polygon = {{1, 1}, {1, 4}, {4, 4}, {4, 1}};
    Point p = {2, 3};  // 待判断的点
 
    if (isPointInPolygon(p, polygon)) {
        std::cout << "点在多边形内" << std::endl;
    } else {
        std::cout << "点不在多边形内" << std::endl;
    }
 
    return 0;
}

点到多边形距离

点在外部，是负数，点在内部，是正数。

#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
 
struct Point {
    double x, y;
};
 
double distance(const Point& p1, const Point& p2) {
    return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
}
 
bool isPointInPolygon(const Point& p, const std::vector<Point>& polygon) {
    bool inside = false;
    for (int i = 0, j = polygon.size() - 1; i < polygon.size(); j = i++) {
        if ((polygon[i].y > p.y) != (polygon[j].y > p.y) &&
            (p.x < (polygon[j].x - polygon[i].x) * (p.y - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x)) {
            inside = !inside;
        }
    }
    return inside;
}
 
double pointToSegmentDistance(const Point& p, const Point& a, const Point& b) {
    Point AB{ b.x - a.x, b.y - a.y };
    Point BP{ p.x - b.x, p.y - b.y };
    Point AP{ p.x - a.x, p.y - a.y };
    double abSquare = AB.x * AB.x + AB.y * AB.y;
    double abapProduct = AB.x * AP.x + AB.y * AP.y;
    double t = abapProduct / abSquare;
 
    if (t < 0.0) {
        return distance(p, a);
    }
    else if (t > 1.0) {
        return distance(p, b);
    }
    else {
        Point closest{ a.x + t * AB.x, a.y + t * AB.y };
        return distance(p, closest);
    }
}
 
double pointToPolygonDistance(const Point& p, const std::vector<Point>& polygon) {
    double minDist = std::numeric_limits<double>::max();
    for (int i = 0, n = polygon.size(); i < n; i++) {
        int j = (i + 1) % n;
        double dist = pointToSegmentDistance(p, polygon[i], polygon[j]);
        minDist = std::min(minDist, dist);
    }
 
    // 如果点在多边形外，返回负的距离
    if (!isPointInPolygon(p, polygon)) {
        minDist = -minDist;
    }
 
    return minDist;
}
 
int main() {
    std::vector<Point> polygon = { {50, 300}, {200, 300}, {300, 250}, {200, 100}, {100, 150} };
    Point p = { 150, 150 };  // 待计算的点
 
    double distance = pointToPolygonDistance(p, polygon);
    std::cout << "点到多边形的最短距离是: " << distance << std::endl;
 
    return 0;
}