How to determine if A->B line resides in the polygon without hitting any walls?
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
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.
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:
#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.
#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).
- C typedef name conflict
- How to use 32-bit pointers in 64-bit application?
- problems with scanf input stream
- Is it guaranteed to be safe to perform memcpy(0,0,0)?
- Need help understanding pointer to a type of n elements in C (int (*p)[10])?
- Local variables performance vs global in example
- How to Print SOAP Message Request Body generated using GSOAP when calling service
- Big Number Subtraction in C
- Docker custom program stop
- GTK4 Windows Multiple File Choosing
- Cannot get lldb to read file input through redirect
- Modeling nested lists in C
- Linker and Memory map for shared memory in autosar embedded environment
- Why is only the numerator cast to float to obtain a float quotient while dividing two integers?
- $gcc problemMatcher doesn't show all errors or warnings
- What registers to save in the ARM C calling convention?
- What does ** do in C language?
- How to install pywin32 module in windows 7
- How to differentiate a Cypher clause from an SQL clause in C?
- How do I check if my executable is running for a service or for a normal program?
- How to fix a simple error in Atmel studio
- Given day, month, year calculate day in year
- Definition of int64_t
- Can we have multiple c files to define functions for one header file?
- Check if array is ASCII
- What does C or GCC do when implicit function declaration exists
- How can I programmatically find the CPU frequency with C
- Can I use a binary literal in C or C++?
- Want to Convert Integer to String without itoa function
- How to permanently configure VSCode to use cl.exe without launching it from the Developer Command Prompt?