Check if a line is entirely inside a polygon

Game Mechanics
#1

Hi guys,

I think I came up with a pathfinding algorithm. May not be the best, but I’d like to try to implement it.
The only problem is that it needs to check if a line is completely inside a polygon. It is not allowed to cross the edges even the littlest bit, touching them is ok though.

I can check on which side of a line a given point is, if a line intersects a polygon, basically everything, but brother Google couldn’t tell me how to check if a line is completely surrounded by a polygon.
Is there no possible way to accomplish this?

Thanks!

#2

Look into javas geometry classes as they can do this but slow. Basic way would be to check if the lines bounds, (square bounding box) intersects the polygons bounds. Then, check if the line intersects each line in the polygon.

#3

If you are just using simple concave convex polys, what about simply checking if both end-points of the line segment are within the polygon?

http://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html

#4

If a polygon is convex, any line between two points inside it is entirely in the polygon. If the polygon is not convex, test to see that at least one is inside the polygon and the line does not intersect an edge. This is an intersection test between two line segments, which is about 12 lines of code. You can always decompose a concave polygon into multiple convex polygons. A special case with plenty of implementations is called triangulation. (It should be obvious what type of polygons it makes.) Checking if a point is inside a triangle is easy. There are also algorithms for any type of polygon, but I am not sure which is faster.

Edit: The path finding method you described involves something called a navigation mesh and may be called region based pathfinding. Good old Amit probably wrote about or linked to something about it.

#5

Thanks guys, it’s working!

[quote=“Several_Kilo-Bytes,post:4,topic:44035”]
Yes, I tried my own navigation mesh pathfinding algorithm. It was crap though :wink: