How to determine if A->B line resides in the polygon without hitting any walls?

Question

Okay, buckle up.

Given a Linestring which is constructed from Point A and B and a polygon C how can I assure that A->B line does not intersect with any walls in C or resides inside the C?

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/segment.hpp>

#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/linestring.hpp>
namespace bg = boost::geometry;
namespace bgm = boost::geometry::model;

typedef bgm::d2::point_xy<double> Point;
typedef bgm::polygon<Point> Polygon;
typedef boost::geometry::model::segment<Point> Segment;
Polygon wall;
Polygon passage;
boost::geometry::model::linestring<Point> AB{start, end}
bool isPassable = false;
bool intersecting = bg::intersects(AB, wall);
if (intersecting) {
    for (int i = 0; i < passage.outer().size(); i += 2) {
      Point p1 = passage.outer()[i];
      Point p2 = passage.outer()[i + 1];
      Segment passageSegment(p1, p2);
      Segment testSegment(start, end);
      if (bg::intersects(passageSegment, testSegment)) {
        isPassable = true;
        break;
      }
    }
} else {
    isPassable = bg::relate(AB, wall, boost::geometry::de9im::mask("T*F**F***"));
}

Due to privacy reasons, I cant show the full code but this is the point of interest anyways.

Our polygon in question

POLYGON((2 2,2 3.5,4 3.5,4 2,2 3.5,2 5.5,5 5.5,5 3.5,4 2,4 3.5,5 3.5,5 5.5,7.5 5.5,7.5 2,2 2)) 

passages

Passage: POINT(2.5 3.5) POINT(3 3.5)
Passage: POINT(4.25 3.5) POINT(4.75 3.5)
Passage: POINT(4 2.5) POINT(4 3)
Passage: POINT(5 4) POINT(5 5)

looks like this:

Where the green line is:

POINT(2.5 3.25) POINT(3 3.625)

After running the two relate functions see if this line is related to any walls, if it is not related, check if it is breaching any holes in passages, this works, actually. For the green line, I can get a true. Problem starts at:

this green line. As you can see it lies in the polygon. So in the first relate to the wall it should return true. but as there is no relation between the line and walls/passages, this one returns false even through it shouldn't. How can I handle this?

In official Boost doc

https://live.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/geometry/reference/algorithms/relate.html

I can see that

This method is actually used for the thing I want. See if the point of interest resides in the polygon. thanks for any help.

Answer 1

Your input polygon is invalid:

Polygon wall;
bg::read_wkt( //
    "POLYGON((2 2,2 3.5,4 3.5,4 2,2 3.5,2 5.5,5 5.5,5 3.5,4 2,4 3.5,5 3.5,5 "
    "5.5,7.5 5.5,7.5 2,2 2)) ",
    wall);

if (std::string reason; !bg::is_valid(wall, reason)) {
    std::cerr << "Invalid polygon: " << reason << "\n";
    return 1;
}

Prints Live On Coliru

Invalid polygon: Geometry has invalid self-intersections. A self-intersection point was found at (2, 3.5); method: t; operations: i/u; segment IDs {source, multi, ring, segment}: {0, -1, -1, 0}/{0, -1, -1, 3}

You can attempt to fix it automatically with bg::correct

for (std::string reason; !bg::is_valid(wall, reason); bg::correct(wall)) {
    std::cerr << "Invalid polygon: " << reason << "\n";
}

But it doesn't work for these problems. I strongly suspect you really want the thing to be a (multi-)linestring, or even just a list of segments.

Then to get the "within" check you'd use bg::within against the convex hull¹.

With those fixes I get:

Live On Coliru

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/multi_linestring.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/geometries/segment.hpp>
namespace bg  = boost::geometry;
namespace bgm = boost::geometry::model;

using Point    = bgm::d2::point_xy<double>;
using Polygon  = bgm::polygon<Point>;
using Segment  = boost::geometry::model::segment<Point>;
using Segments = std::vector<Segment>;
using String   = bgm::linestring<Point>;
using MString  = bgm::multi_linestring<String>;

int main() {
    String wall
        // {{2, 2}, {2, 3.5}, {4, 3.5}, {4, 2},   {2, 3.5},   {2, 5.5}, {5, 5.5},
        // {5, 3.5}, {4, 2}, {4, 3.5}, {5, 3.5}, {5, 5.5}, {7.5, 5.5}, {7.5, 2}, {2, 2}}
        //
        ;

    bg::read_wkt(
        "LINESTRING(2 2,2 3.5,4 3.5,4 2,2 3.5,2 5.5,5 5.5,5 3.5,4 2,4 3.5,5 3.5,5 "
        "5.5,7.5 5.5,7.5 2,2 2)",
        wall);

    for (std::string reason; !bg::is_valid(wall, reason); bg::correct(wall)) {
        std::cerr << "Invalid wall: " << reason << "\n";
    }

    Polygon hull;
    bg::convex_hull(wall, hull);

    std::cout << "Wall is " << bg::wkt(wall) << std::endl;
    std::cout << "Hull is " << bg::wkt(hull) << std::endl;

    //Segment AB({2.5, 3.25}, {3, 3.625});
    Segment AB({6, 3.5}, {6.25, 4});

    Segments passages{
        {{2.5, 3.5}, {3, 3.5}},
        {{4.25, 3.5}, {4.75, 3.5}},
        {{4, 2.5}, {4, 3}},
        {{5, 4}, {5, 5}},
    };

    bool isPassable = false;
    if (/*bool intersecting =*/bg::intersects(AB, wall)) {
        for (auto& passage : passages) {
            if (bg::intersects(passage, AB)) {
                isPassable = true;
                break;
            }
        }
    } else {
        bgm::linestring<Point> abls({AB.first, AB.second});
        isPassable = bg::within(abls, hull);
    }

    std::cout << "Is passable: " << std::boolalpha << isPassable << std::endl;
}

Printing

Wall is LINESTRING(2 2,2 3.5,4 3.5,4 2,2 3.5,2 5.5,5 5.5,5 3.5,4 2,4 3.5,5 3.5,5 5.5,7.5 5.5,7.5 2,2 2)
Hull is POLYGON((2 2,2 5.5,7.5 5.5,7.5 2,2 2))
Is passable: true

I would really suggest to simplify it further by actually deleting the passages from the original "wall" string. This is especially important to make your check correct. After all, when there are multiple intersections one of them being in a passage really doesn't change anything, but your code assumes there is always only one intersection.

BONUS

This take (still assuming the convex hull) should be correct for multiple intersections. Note also that it is became considerably simpler. And we assert that the passages actually lie on the walls.

I've added more test-cases to showcase different edge cases.

Live On Coliru

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/multi_linestring.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/geometries/segment.hpp>
namespace bg  = boost::geometry;
namespace bgm = boost::geometry::model;

using Point    = bgm::d2::point_xy<double>;
using MPoint   = bgm::multi_point<Point>;
using Polygon  = bgm::polygon<Point>;
using Segment  = boost::geometry::model::segment<Point>;
using Segments = std::vector<Segment>;
using String   = bgm::linestring<Point>;
using MString  = bgm::multi_linestring<String>;

int main() {
    String const wall{{2, 2},   {2, 3.5}, {4, 3.5},   {4, 2},   {2, 3.5},
                      {2, 5.5}, {5, 5.5}, {5, 3.5},   {4, 2},   {4, 3.5},
                      {5, 3.5}, {5, 5.5}, {7.5, 5.5}, {7.5, 2}, {2, 2}};

    Polygon hull;
    bg::convex_hull(wall, hull);

    std::cout << "Wall is " << bg::wkt(wall) << std::endl;
    std::cout << "Hull is " << bg::wkt(hull) << std::endl;

    MString const passages{
        {{2.5, 3.5}, {3, 3.5}},
        {{4.25, 3.5}, {4.75, 3.5}},
        {{4, 2.5}, {4, 3}},
        {{5, 4}, {5, 5}},
    };

    assert(passages.size() == 4);
    assert(bg::within(passages, wall));

    for (auto AB : {
             String{{2.5, 3.25}, {3, 3.625}},
             String{{6, 3.5}, {6.25, 4}},
             String{{3.5, 3.25}, {4, 3.625}},
             String{{3.5, 1.25}, {4, 1.625}},
             String{{3.5, 1.75}, {4, 2.125}},
         }) {
        std::cout << "\n---- Test AB " << bg::dsv(AB) << " ----\n";

        MPoint w_isect, p_isect;
        bg::intersection(wall, AB, w_isect);
        bg::intersection(passages, AB, p_isect);
        std::cout << "Intersecting wall:" << bg::dsv(w_isect)
                  << " Passage:" << bg::dsv(p_isect) << std::endl;

        bool const isPassable =                       //
            (w_isect.empty() && bg::within(AB, hull)) //
            || (w_isect.size() == p_isect.size());

        std::cout << "Is passable: " << isPassable << " ("
                  << (bg::disjoint(AB, hull) ? "disjoint" : "")
                  << (bg::within(AB, hull) ? "within" : "") //
                  << ")" << std::endl;
    }
}

Printing

Wall is LINESTRING(2 2,2 3.5,4 3.5,4 2,2 3.5,2 5.5,5 5.5,5 3.5,4 2,4 3.5,5 3.5,5 5.5,7.5 5.5,7.5 2,2 2)
Hull is POLYGON((2 2,2 5.5,7.5 5.5,7.5 2,2 2))

---- Test AB ((2.5, 3.25), (3, 3.625)) ----
Intersecting wall:((2.83333, 3.5)) Passage:((2.83333, 3.5))
Is passable: 1 (within)

---- Test AB ((6, 3.5), (6.25, 4)) ----
Intersecting wall:() Passage:()
Is passable: 1 (within)

---- Test AB ((3.5, 3.25), (4, 3.625)) ----
Intersecting wall:((3.83333, 3.5)) Passage:()
Is passable: 0 (within)

---- Test AB ((3.5, 1.25), (4, 1.625)) ----
Intersecting wall:() Passage:()
Is passable: 1 (disjoint)

---- Test AB ((3.5, 1.75), (4, 2.125)) ----
Intersecting wall:((4, 2.125), (3.91667, 2.0625), (4, 2.125), (3.83333, 2)) Passage:()
Is passable: 0 ()

---

¹ (If your shapes are more complex than depicted and can have concave edges, then you need to adapt for that still).