Path to the point that is inside the polygon

[aglitchman]

Thank you for the library!

I'm trying to use the library in combination with the physics engine. Polygons for Navmesh have simplified geometry, so two cases often happen:

• I'm trying to find a path from inside the polygon (from the "wall").
• I'm trying to find a path into the polygon (into the "wall").
• Or both.

In these cases, of course, GetPath returns nothing.

What to do? Give me an idea.

Many thanks!

[ilyanikolaevsky]

First of all, I'm a little confused. Why do you need to get into the wall? Is the speed different inside the wall? The point is that the path can't go through the obstacles, that's what "obstacles" are. If you need to get into some obstacle, then maybe you'll need to delete that one polygon first. Do you perhaps have obstacles made of infinitely thin lines (borders of the polygons) and you might need to find a path inside some enclosed area too?

But if it's a special case, where you can go into one obstacle at the very end of the path then, in theory, you need to create a special "insertion" point on the boundary of the polygon. then find the path to/from this point and concatenate a direct line from the insertion point to the destination point after that. The insertion point can be the closest one to the real end point on the polygon border. The library works with points lying on the boundary of the polygons just fine (of course, only If you don't have polygon's inflation enabled).

That won't necessarily be the shortest path, but it's a somewhat good approximation.

You also can try experimenting with changing the code a little. In the PathFinder class currently there's a calculation of the point_is_inside array, and the points which are inside any of the polygons are just skipped. You can make that array two-dimentional and don't skip points that are inside. Then, you'll need to skip the polygons which have one endpoint inside in the CanAddSegment() function.

[aglitchman]

I apologise for the original question, as I'm still using the library as a user, without getting into its inner workings.

Let me describe a case. I started using Navmesh for pathfinding for the main character of the game and it turned out that players like to click on stationary objects (tree, chest and so on) as destinations. And these objects, of course, are present in Navmesh's polygon list and therefore Navmesh can't find the path to them.

Ideally, it would be nice if Navmesh could build a path to the closest point near a wall/chest/tree.

Now what I do is - if the destination point hits a polygon, I temporarily remove the polygon from the polygon list to find any meaningful path to the point.

You also can try experimenting with changing the code a little. In the PathFinder class currently there's a calculation of the point_is_inside array, and the points which are inside any of the polygons are just skipped. You can make that array two-dimentional and don't skip points that are inside. Then, you'll need to skip the polygons which have one endpoint inside in the CanAddSegment() function.

It seems as a great idea! I'll try.

[ilyanikolaevsky]

Without changing the library code, deleting the polygon might be a best solution.

Otherwise, once you've found that the destination point is inside a polygon, you can add a bunch of points on the side of the polygon and then find the shortest path from the source to any of the destination points. You can implement a new |PathFinder::GetPath| function, which takes in a vector of the dest points. Then it's easy to modify the underlying Dijkstra algorithm: Once you've found a distance to any of the destination points, you can stop the loop.

[ikilgor]

Hello ilyanikolaevsky thank you for you library! can you please help me with same problem? i changed code of AddExternalPoints now if start or dest point (IsInside == true) im iterating points_ and using closest, its worked for me, but can you plese help me find closest point not only from vertexes but from edges too? im failed to reconstruct lines between all vertexes not all my line's points lies on edges(some inside some outside polygon) i attached file

`//extpoints = points_;

    std::vector<std::pair<int, int>> tangents(polygons_.size());
    std::vector<bool> point_is_inside(points_.size(), false);

    for (int i = 0; i < points_.size(); ++i) {
        for (int j = 0; j < polygons_.size(); ++j) {
            if (polygons_[j].IsInside(points_[i])) {
                float d = 99999;
                int Closest = -1;
                Point Current = points_[i];
                for (int k = 0; k < polygons_[j].points_.size(); k++){
                    if (points_[i].Distance(polygons_[j].points_[k]) < d)
                    {                                                       
                        d = points_[i].Distance(polygons_[j].points_[k]);
                        Closest = k;
                    }
                }
                Point Changed = points_[i] = polygons_[j].points_[Closest];
                //printf("point %i;%i -> %i;%i\n", Current.x, Current.y, Changed.x, Changed.y);
                //point_is_inside[i] = true;                    
                break;
            }
        }
    }

    ext_points_ = points_;`

Anyway thanks you! and sorry for my english. forgit.txt

[ilyanikolaevsky]

Ok, so you need to find a closest point on all the sides of the polygon. (side note: you can add edges to all the vertices of the polygon, all the sides, and all the other polygons. The Dijkstra algorithm will find the shortest route correctly. The only issue is that you'll need to not check the node rays for intersection with the polygon the node lies inside of. So, instead of commenting out point_is_inside[i] = true, you might want to store j there instead and skip j-th polygon in CanAddSegments for that point).

To find the closest point on the side, you'll need to do a little bit of geometry and cast a perpendicular to the side from the point. The issue here is, however, that the closest point on the side might not have integer coordinates. Maybe it's fine to just round that to closest integers, but if your polygons are small, it might look bad.

The code might be something like this (probably separate it in a new function):

// p1, p2 - points forming a side segment
// p - source point.
// construct the line equation a*x+b*y+c = 0, s.t. a^2+b^2 = 1
double a = p2.y-p1.y;
double b = p1.x-p2.x;
double len = sqrt(a*a+b*b);
a /= len;
b /= len;
double c = -p1.x*a-p1.y*b;
// Find signed distance from p to the line.
len = p.x*a+p.y*b+c;
// Apply reverse perpendicular, scaled accordingly.
x = p.x-a*len;
y = p.y-b*len;
// {x,y} lies on a line. But may not lie on the segment.
// Check if vectors p1->p and p1->p2 are reverse collinear via vector multiplication, i.e. p1 lies between p and p2.
// Then p1 is the closest point on the segment.
if ((x-p1.x)*(p2.y-p1.y)-(y-p1.y)*(p2.x-p1.x) <= 0) return {p1.x, p1.y};
// The same but for p2.
if ((x-p2.x)*(p1.y-p2.y)-(y-p2.y)*(p1.x-p2.x) <= 0) return {p2.x, p2.y};
return {x, y};

[ikilgor]

Hello! thanks for answer(saved it for future)! but i used Inflate(1), store all points from sides in private std::vector<Point> in Polygon class and now when AddExternalPoints start or dest point IsInside == true im just calling new function Point Polygon::GetClosestPoint(const Point& a) const which iterating vector with precalculated points from inflated polygon. Many thanks!