目录
判断点是否在多边形内
点到多边形距离
判断点是否在多边形内
#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;
}