How to find a face containing a predefined point when I have a flat graph embedded in a plane

Question

I have a flat graph embedded in a plane (flat graph) and you want to look for its faces. The graph is not connected, but consists of several connected graphs that are not separately orientable (for example, a subgraph can be contained in the face of another graph) I want to find polygons (faces) that include a certain point 2d. Polygons are formed by faces of graphs. Since the number of persons is quite large, I would like to avoid them in advance. What is the general complexity of such a search and which C ++ library / coding method can be used to execute it.

Updated to clarify: I mean the xy plane here

Answer 1

You present an interesting task. A relatively simple solution is possible if the polygon is always convex, because in this case you only need to ask if an interesting point is on the same flank (left or right) of all sides of the polygon. Although I don’t know a particularly simple solution for the general case, the following code really works for any arbitrary polygon, as was indirectly used by the well-known Cauchy integral formula.

You don't have to be familiar with Cauchy to follow the code, as comments in 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 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 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 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;

}

, - , , , , . , , , , , . , , , , .

.