Sign in to follow this  
soivex

Fastest way to test if point inside a shape.

Recommended Posts

Hello there. I have a random 2D shape stored as array of points (connected spline with approx. 400 points). My task is to create filled texture of the given shape. So how i doing it now: i'm calculating the bounding rectange and start checking for each point if it inside my shape or not. How i done this "checking": i'm creating a line and count how many times my line intersects the shape. But shape consist of up to 400 points, and i need to check for intersection many times, as a result it's working too slow. May be there is some faster way to check if my points is inside a shape? Thanks!

Share this post


Link to post
Share on other sites
The process you are performing is called rasterization. A typical approach is to sort your points from top to bottom, then for each scanline determine what portion should be drawn, and which shouldn't, by computing the intersection of a horizontal line with the segments of the shape that are present at that height (which is easily determined since you sorted the points.

Share this post


Link to post
Share on other sites
I don't know if this is faster, but it certainly is elegant. So, check out the Separating Axis Theorem. This tutorial discusses it in regards to shape-on-shape collision. To do it with points, you only have to test the axes from the shape, the point adds no additional axes to test.

Share this post


Link to post
Share on other sites
I think this is in the context of his jigsaw game. So, the pieces will not be convex by a long shot. His algo is not exactly the rasterisation algo, but since he will be working on a bitmap, rasterising the piece would be the way to go imho. Or splitting the outline spline into small segments, render the segments into a buffer, then floodfill the interior to find the pixels inside.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this