我有一个嵌入在平面上的平面图（平面图）并且想要搜索它的面。该图不是连接的，而是由几个连接的图组成，这些图不能单独寻址（例如，子图可以包含在另一个图的面上）我想找到包含某个二维点的多边形（面）。多边形由图形的面形成。由于面孔的数量很大，我想避免事先确定它们。这种搜索的一般复杂性是什么，我可以使用什么 c++ 库/编码方法来完成它。
更新以澄清：我在这里指的是 xy 平面中的图表
问问题
260 次
1 回答
1
你提出了一个有趣的挑战。如果多边形碰巧总是凸的，则相对简单的解决方案是可能的，因为在这种情况下，只需询问兴趣点是否位于多边形所有边的同一侧面（无论是左侧还是右侧）。虽然我知道对于一般情况没有特别简单的解决方案，但下面的代码似乎确实适用于任何任意多边形，这间接地受到柯西著名的积分公式的启发。
无需熟悉 Cauchy 即可遵循代码，因为代码中的注释解释了该技术。
#include <vector>
#include <cstddef>
#include <cstdlib>
#include <cmath>
#include <iostream>
// This program takes its data from the standard input
// stream like this:
//
// 1.2 0.5
// -0.1 -0.2
// 2.7 -0.3
// 2.5 2.9
// 0.1 2.8
//
// Given such input, the program answers whether the
// point (1.2, 0.5) does not lie within the polygon
// whose vertices, in sequence, are (-0.1, -0.2),
// (2.7, -0.3), (2.5, 2.9) and (0.1, 2.8). Naturally,
// the program wants at least three vertices, so it
// requires the input of at least eight numbers (where
// the example has four vertices and thus ten numbers).
//
// This code lacks really robust error handling, which
// could however be added without too much trouble.
// Also, its function angle_swept() could be shortened
// at cost to readability; but this is not done here,
// since the function is already hard enough to grasp as
// it stands.
//
//
const double TWOPI = 8.0 * atan2(1.0, 1.0); // two times pi, or 360 deg
namespace {
struct Point {
double x;
double y;
Point(const double x0 = 0.0, const double y0 = 0.0)
: x(x0), y(y0) {}
};
// As it happens, for the present code's purpose,
// a Point and a Vector want exactly the same
// members and operations; thus, make the one a
// synonym for the other.
typedef Point Vector;
std::istream &operator>>(std::istream &ist, Point &point) {
double x1, y1;
if(ist >> x1 >> y1) point = Point(x1, y1);
return ist;
}
// Calculate the vector from one point to another.
Vector operator-(const Point &point2, const Point &point1) {
return Vector(point2.x - point1.x, point2.y - point1.y);
}
// Calculate the dot product of two Vectors.
// Overload the "*" operator for this purpose.
double operator*(const Vector &vector1, const Vector &vector2) {
return vector1.x*vector2.x + vector1.y*vector2.y;
}
// Calculate the (two-dimensional) cross product of two Vectors.
// Overload the "%" operator for this purpose.
double operator%(const Vector &vector1, const Vector &vector2) {
return vector1.x*vector2.y - vector1.y*vector2.x;
}
// Calculate a Vector's magnitude or length.
double abs(const Vector &vector) {
return std::sqrt(vector.x*vector.x + vector.y*vector.y);
}
// Normalize a vector to unit length.
Vector unit(const Vector &vector) {
const double abs1 = abs(vector);
return Vector(vector.x/abs1, vector.y/abs1);
}
// Imagine standing in the plane at the point of
// interest, facing toward a vertex. Then imagine
// turning to face the next vertex without leaving
// the point. Answer this question: through what
// angle did you just turn, measured in radians?
double angle_swept(
const Point &point, const Point &vertex1, const Point &vertex2
) {
const Vector unit1 = unit(vertex1 - point);
const Vector unit2 = unit(vertex2 - point);
const double dot_product = unit1 * unit2;
const double cross_product = unit1 % unit2;
// (Here we must be careful. Either the dot
// product or the cross product could in theory
// be used to extract the angle but, in
// practice, either the one or the other may be
// numerically problematical. Use whichever
// delivers the better accuracy.)
return (fabs(dot_product) <= fabs(cross_product)) ? (
(cross_product >= 0.0) ? (
// The angle lies between 45 and 135 degrees.
acos(dot_product)
) : (
// The angle lies between -45 and -135 degrees.
-acos(dot_product)
)
) : (
(dot_product >= 0.0) ? (
// The angle lies between -45 and 45 degrees.
asin(cross_product)
) : (
// The angle lies between 135 and 180 degrees
// or between -135 and -180 degrees.
((cross_product >= 0.0) ? TWOPI/2.0 : -TWOPI/2.0)
- asin(cross_product)
)
);
}
}
int main(const int, char **const argv) {
// Read the x and y coordinates of the point of
// interest, followed by the x and y coordinates of
// each vertex in sequence, from std. input.
// Observe that whether the sequence of vertices
// runs clockwise or counterclockwise does
// not matter.
Point point;
std::vector<Point> vertex;
std::cin >> point;
{
Point point1;
while (std::cin >> point1) vertex.push_back(point1);
}
if (vertex.size() < 3) {
std::cerr << argv[0]
<< ": a polygon wants at least three vertices\n";
std::exit(1);
}
// Standing as it were at the point of interest,
// turn to face each vertex in sequence. Keep
// track of the total angle through which you
// have turned.
double cumulative_angle_swept = 0.0;
for (size_t i = 0; i < vertex.size(); ++i) {
// In an N-sided polygon, vertex N is again
// vertex 0. Since j==N is out of range,
// if i==N-1, then let j=0. Otherwise,
// let j=i+1.
const size_t j = (i+1) % vertex.size();
cumulative_angle_swept +=
angle_swept(point, vertex[i], vertex[j]);
}
// Judge the point of interest to lie within the
// polygon if you have turned a complete circuit.
const bool does_the_point_lie_within_the_polygon =
fabs(cumulative_angle_swept) >= TWOPI/2.0;
// Output.
std::cout
<< "The angle swept by the polygon's vertices about the point\n"
<< "of interest is " << cumulative_angle_swept << " radians ("
<< ((360.0/TWOPI)*cumulative_angle_swept) << " degrees).\n"
<< "Therefore, the point lies "
<< (
does_the_point_lie_within_the_polygon
? "within" : "outside of"
)
<< " the polygon.\n";
return !does_the_point_lie_within_the_polygon;
}
当然，上面的代码只是我写的，因为你的挑战很有趣，我想看看我能不能满足它。如果您的应用程序很重要，那么您应该测试和审查代码，并请在此处修改您发现的任何错误。我已经针对两个或三个案例测试了代码，它似乎可以工作，但是对于重要的任务，它需要更详尽的测试。
祝你的申请好运。
于 2012-06-06T14:22:32.047 回答