# Fastest way to test if point inside a shape.

This topic is 4115 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

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

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 15
• 13
• 9
• 12
• 10
• ### Forum Statistics

• Total Topics
631442
• Total Posts
3000091
×