Java-Gaming.org Hi !
 Featured games (91) games approved by the League of Dukes Games in Showcase (754) Games in Android Showcase (229) games submitted by our members Games in WIP (842) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
 Home Help Search Login Register
Pages: [1]
 ignore  |  Print
 Check if a line is entirely inside a polygon  (Read 5202 times) 0 Members and 1 Guest are viewing this topic.
dermetfan
 « Posted 2013-09-06 01:41:46 »

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!

StumpyStrust
 « Reply #1 - Posted 2013-09-06 02:01:49 »

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.

davedes
 « Reply #2 - Posted 2013-09-06 02:05:50 »

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
http://stackoverflow.com/questions/217578/point-in-polygon-aka-hit-test

 Games published by our own members! Check 'em out!
Several Kilo-Bytes

Senior Devvie

Medals: 11

 « Reply #3 - Posted 2013-09-06 02:29:33 »

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.
dermetfan
 « Reply #4 - Posted 2013-09-08 18:00:52 »

Thanks guys, it's working!
The path finding method you described involves something called a navigation mesh and may be called region based pathfinding.
Yes, I tried my own navigation mesh pathfinding algorithm. It was crap though

Pages: [1]
 ignore  |  Print

 DesertCoockie (36 views) 2018-05-13 18:23:11 nelsongames (80 views) 2018-04-24 18:15:36 nelsongames (73 views) 2018-04-24 18:14:32 ivj94 (755 views) 2018-03-24 14:47:39 ivj94 (85 views) 2018-03-24 14:46:31 ivj94 (626 views) 2018-03-24 14:43:53 Solater (101 views) 2018-03-17 05:04:08 nelsongames (182 views) 2018-03-05 17:56:34 Gornova (408 views) 2018-03-02 22:15:33 buddyBro (1068 views) 2018-02-28 16:59:18
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org