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