如何才能找到包含predefined点的脸，当我有嵌入在一个平面上的平面图 [英] How can a find a face containing a predefined point when i have a planar graph embedded on a plane
问题描述
我有嵌入在一个平面上（平面图）平面图形，并希望搜索它的面孔。 未连接的曲线图，但包括几个连通图，这是不分开adressable（例如，一个子可以被包含在另一个图形的面） 我想找到的多边形（面），其中包括一定的二维点。 多边形是由曲线图的面形成。由于面的数量是相当大的，我想，以避免预先判断他们。 什么是这样的搜索，什么C ++库/编码方法可以用我来完成它的总体复杂性。
I have a planar graph embedded on a plane (plane graph ) and want to search its faces. The graph is not connected but consists of several connected graphs, which are not separately adressable (e.g. a subgraph can be contained in the face of another graph) I want to find the polygons (faces) which include a certain 2d point. The polygons are formed by the faces of the graphs. As the number of faces is quite big I would like to avoid to determine them beforehand. What is the general complexity of such a search and what c++ library/ coding approach can I use to accomplish it.
更新澄清：我指的图形在XY平面位置
Updated to clarify: I am refering to a graph in the xy plane here
推荐答案
您带来一个有趣的挑战。一个相对简单的解决方案是可能的，如果多边形发生始终是凸的，因为在这种情况下，人们只需要询问所述兴趣点是否位于同一侧面（无论是左或右）中的所有多边形的边。虽然我知道对于一般情况下，没有特别简单的解决方案，下面的code似乎为任何工作，任意多边形，由柯西著名的积分公式的启发是间接的。
You pose an interesting challenge. A relatively simple solution is possible if the polygon happens always to be convex, because in that case one need only ask whether the point of interest lies on the same flank (whether left or right) of all the polygon's sides. Though I know of no especially simple solution for the general case, the following code does seem to work for any, arbitrary polygon, as inspired indirectly by Cauchy's famous integral formula.
人们不需要熟悉柯西跟随code，对于内code注释说明了该技术。
One need not be familiar with Cauchy to follow the code, for comments within the code explain the technique.
#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;
}
当然，上面的code是只是一些我写的，因为你的挑战很有趣，我想看看我是否能满足它。如果你的应用是很重要的，那么你应该测试和审查code，并请修改回到这里，你发现任何错误。我已经测试了code对两个或三个的情况下，它似乎工作，但重要的职责，将需要更详尽的测试。
Of course, the above code is just something I wrote, because your challenge was interesting and I wanted to see if I could meet it. If your application is important, then you should both test and review the code, and please revise back here any bugs you find. I have tested the code against two or three cases, and it seems to work, but for important duty it would want more exhaustive testing.
祝您的应用程序。
这篇关于如何才能找到包含predefined点的脸，当我有嵌入在一个平面上的平面图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
