Hi !
Featured games (87)
games approved by the League of Dukes
Games in Showcase (669)
Games in Android Showcase (194)
games submitted by our members
Games in WIP (727)
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 2806 times)
0 Members and 1 Guest are viewing this topic.
Offline 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?


Offline 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.

Offline 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?

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline 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.
Offline 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 Wink

Pages: [1]
  ignore  |  Print  
You cannot reply to this message, because it is very, very old.

IanParcs (34 views)
2016-04-18 14:18:53

KaiHH (34 views)
2016-04-18 08:35:41

KaiHH (66 views)
2016-04-15 12:43:58

theagentd (64 views)
2016-04-14 02:16:17

theagentd (71 views)
2016-04-14 02:15:43

IanParcs (65 views)
2016-04-12 03:51:16

IanParcs (35 views)
2016-04-12 03:50:03

IanParcs (32 views)
2016-04-12 03:49:54

IanParcs (27 views)
2016-04-12 03:49:52

IanParcs (36 views)
2016-04-12 03:49:52
List of Learning Resources
by SilverTiger
2016-02-05 09:39:47

List of Learning Resources
by SilverTiger
2016-02-05 09:38:38

List of Learning Resources
by SilverTiger
2016-02-05 09:35:50

Rendering resources
by Roquen
2015-11-13 14:37:59

Rendering resources
by Roquen
2015-11-13 14:36:58

Math: Resources
by Roquen
2015-10-22 07:46:10

Networking Resources
by Roquen
2015-10-16 07:12:30

Rendering resources
by Roquen
2015-10-15 07:40:48 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‑
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!