Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (604) Games in Android Showcase (171) games submitted by our members Games in WIP (654) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Check if a line is entirely inside a polygon  (Read 2153 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

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

You cannot reply to this message, because it is very, very old.

 SHC (37 views) 2015-08-01 03:58:20 Jesse (24 views) 2015-07-29 04:35:27 Riven (44 views) 2015-07-27 16:38:00 Riven (24 views) 2015-07-27 15:35:20 Riven (27 views) 2015-07-27 12:26:13 Riven (18 views) 2015-07-27 12:23:39 BurntPizza (39 views) 2015-07-25 00:14:37 BurntPizza (48 views) 2015-07-24 22:06:39 BurntPizza (33 views) 2015-07-24 06:06:53 NoxInc (40 views) 2015-07-22 22:16:53
 theagentd 51x wessles 49x basil_ 33x KaiHH 26x orangepascal 25x Riven 22x ags1 18x mooman219 17x bornander 15x KudoDEV 13x princec 11x pquiring 11x CelestialCreator 11x klaus 10x Jesse 9x Spasi 8x
 List of Learning Resourcesby gouessej2015-07-09 11:29:36How Do I Expand My Game?by bashfrog2015-06-14 11:34:43List of Learning Resources2015-05-31 05:37:30Intersection Methodsby Roquen2015-05-29 08:19:33List of Learning Resources2015-05-05 10:20:32How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21
 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