Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

AppGameKit Classic Chat / Calculate if a point is inside an arbitrary shape?

Author
Message
Clonkex
Forum Vice President
14
Years of Service
User Offline
Joined: 20th May 2010
Location: Northern Tablelands, NSW, Australia
Posted: 27th Jul 2013 15:45
Link
Hi all,

I'm creating a procedural terrain system in AGK. I start by creating a series of points which each know the number of the one they are connected to in a clockwise direction. If you don't understand that don't worry, it's not important.

In order to render the terrain I need to be able to generate images from the series of points which form an enclosed arbitrary shape (can be concave or convex). Refer to the image below for an idea of what I'm on about:



What I need is a way to calculate whether a point is within the shape. I can't use any built-in AppGameKit method for this, such as GetSpriteHitTest(), because I'm not testing a sprite, I'm testing my own custom array data (a list of points). Also, I can't set it up as a Polygon shape because there's a limit of 12 points and I can't limit my terrain to 12 points and I can't split it up.

Any help would be much appreciated

Thanks,
Clonkex


Placement Editor Professional
Code Line Counter
Back to top
Profile PM Email
Van B
Moderator
22
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 27th Jul 2013 17:50
Link
If you get yourself a line to line intersection check, then you could calculate each pixel that way.

Like, if you take the centre of the shape, and check a line between that and the pixel location, count the number of border lines that intersect with it, and if that number is even, then the pixel is inside the shape.

You should be able to find a code example of a line intersect function, then convert it to AppGameKit - I think that would be very usefull to you with this project.

I got a fever, and the only prescription, is more memes.
Back to top
Profile PM Email
Clonkex
Forum Vice President
14
Years of Service
User Offline
Joined: 20th May 2010
Location: Northern Tablelands, NSW, Australia
Posted: 27th Jul 2013 18:04
Link
After I posted my question, I decided I'd better Google it. Turns out there's a fair amount of information about determining whether a point is inside an arbitrary polygon. There's two main methods of achieving this.

The first and simplest is the one I think you are describing. You run a ray through the point in any direction; if it intersects an odd number of lines, the point is inside; even and it's outside. Simple enough, but there's problems when you intersect exactly through a vertex - it'll count two intersections. There are ways around this, but they're complicated-ish.

The second method is the one I've been trying to get working for the past 2 hours. It's the winding number method. As far as I can gather, if you add all the signed angles from the point to each vertex continuing around, it'll end up as either a multiple of PI or 0, depending on whether the point is inside or out. Well, that's the theory. So far my code just ALWAYS results in a 0. I'll keep trying and get back to you with the code if I get it working.

Clonkex


Placement Editor Professional
Code Line Counter
Back to top
Profile PM Email
JimHawkins
15
Years of Service
User Offline
Joined: 26th Jul 2009
Location: Hull - UK
Posted: 27th Jul 2013 18:14
Link
If you don't have to do this it run-time, Windows can happily create convex and concave polygonal images complete with brush fill. You can then save the bitmap and load it into AGK.

-- Jim DO IT FASTER, EASIER AND BETTER WITH AppGameKit FOR PASCAL
Back to top
Profile PM Website
The Daddy
15
Years of Service
User Offline
Joined: 13th Jan 2009
Location: Essex
Posted: 27th Jul 2013 19:52
Link
The winding method splits you irregular polygon into triangles and detects if your point is in a triangle..if not move on, as a triangle is always a covex polygon...simpler to calculate....

This looks interesting as the polygons are very complex,...also gives C code so is easier to follow than solid math..

http://alienryderflex.com/polygon/

Good luck

www.bitmanip.com
All the juicy you could ever dream of!
Back to top
Profile PM Email Website
Clonkex
Forum Vice President
14
Years of Service
User Offline
Joined: 20th May 2010
Location: Northern Tablelands, NSW, Australia
Posted: 28th Jul 2013 01:21
Link
Quote: "If you don't have to do this it run-time, Windows can happily create convex and concave polygonal images complete with brush fill. You can then save the bitmap and load it into AGK."


Haha I know No, unfortunately it must be done at runtime.

Quote: "This looks interesting as the polygons are very complex,...also gives C code so is easier to follow than solid math..

http://alienryderflex.com/polygon/"


I had found that already, but thanks anyway I don't want to use the method described in that paper, simple though it is, because it has problems when the ray intersects vertices.

Hhh....back to work trying to figure out the winding number method...

Clonkex


Placement Editor Professional
Code Line Counter
Back to top
Profile PM Email
Clonkex
Forum Vice President
14
Years of Service
User Offline
Joined: 20th May 2010
Location: Northern Tablelands, NSW, Australia
Posted: 28th Jul 2013 03:15
Link
I DID IT!!

After literally 5 hours of work, 30 Chrome tabs, 10+ drawings of triangles in Paint, an on-screen protractor and Windows calculator, I can stick my mouse inside an arbitrary polygon and my code will tell me it's in there!

I ended up getting the winding number algorithm working perfectly. I tested with a convex and a concave shape it worked perfectly for both. This is the code:



The array containing the points is called "blobpoint". The "connectedto" variable in each blobpoint is the next vertex that this vertex is connected to. Luckily this code doesn't have to be particularly fast because I don't need it to work in realtime, although I'm pretty sure it would actually be fast enough for realtime anyway.

Very happy. I'll post a screenshot of what I needed this code for as soon as I finish it

Clonkex


Placement Editor Professional
Code Line Counter
Back to top
Profile PM Email
baxslash
Valued Member
Bronze Codemaster
17
Years of Service
User Offline
Joined: 26th Dec 2006
Location: Duffield
Posted: 28th Jul 2013 13:36
Link
That's great work Clonkex I might have to digest it properly later.

I notice you are using the hash sign '#' after your UDT array for floats. You don't need to use them if the type is defined IE:



this.mess = abs(sin(times#))
Back to top
Profile PM Email
Marl
13
Years of Service
User Offline
Joined: 19th Nov 2011
Location: Bradford, UK
Posted: 28th Jul 2013 13:46 Edited at: 28th Jul 2013 13:48
Link
Quote: "10+ drawings of triangles in Paint, an on-screen protractor and Windows calculator,"

It's often good to do stuff like this.

Finding code that does what you want is great, figuring out how it does what you want is better.

Nice job.
Back to top
Profile PM Email
Clonkex
Forum Vice President
14
Years of Service
User Offline
Joined: 20th May 2010
Location: Northern Tablelands, NSW, Australia
Posted: 29th Jul 2013 17:07
Link
Quote: "That's great work Clonkex"


Thanks

Quote: "I notice you are using the hash sign '#' after your UDT array for floats. You don't need to use them"


Now why would I want to do that? I ALWAYS use hashes on my floats (I have very strict coding rules I impose on myself, including spacing and use of comments) so I can easily identify floats and because I find consistency to be incredibly important in coding. Thanks for telling me, though

Quote: "figuring out how it does what you want is better."


Yes! I totally agree. As it turns out...

Quote: "Finding code that does what you want is great"


...I found a faster method pre-coded (in C++) online. I'm glad I worked it out myself because now I understand the inner workings of the code. My own code wasn't anywhere near fast enough so I had to take a deep breath and dive into all the complex maths involved in the faster, more efficient methods. I survived and have one of two faster methods working perfectly (I'm still debugging the other new method). Here's the code for the Crossing Number variant (without the issues I described in an earlier post here):



I like that one because it's small, fast and entirely self-contained. That's not quite the fastest that code could be because when I was getting it working I separated some of the variables into floats to make it divide correctly and haven't yet reduced the number of variable assignments.

It's still not quite fast enough for my liking, which forces me into the world of per-operation optimisation (like counting how many divisions are made). Unfortunately I don't know what are the slowest parts of DBPro (for example, are division operations unusually slow? Or is variable creation a big slow-down in repeated operations?) so making it faster will be a challenge and a half.

Anyway. That's what programming's about, right? And if I succeed with it all, it's not only very satisfying, it could potentially pay off enormously.

Clonkex


Placement Editor Professional
Code Line Counter
Back to top
Profile PM Email
Back to top

Login to post a reply

Server time is: 2024-11-24 18:24:40
Your offset time is: 2024-11-24 18:24:40