points inside a shape
- Thread starter anhnha
- Start date
If the shape is convex, then there are some very efficient algorithms out there. But your example is not convex so you are much more limited in your choice of options.
One method is to start at your point and move to some other reference point and count the number of times you cross the boundary taking that journey. If you cross the boundary an even number of times, then your starting point is on the same side of the shape (inside or outside) as the reference point, while if you cross the boundary an odd number of times you are on the opposite side. You just need to choose a reference point a point that you know whether it is inside or outside. Finding a point outside is easy because you can just go through your vertices and find the maximum x and y coordinates and then choose the point <xmax+1,ymax+1>.
One method is to start at your point and move to some other reference point and count the number of times you cross the boundary taking that journey. If you cross the boundary an even number of times, then your starting point is on the same side of the shape (inside or outside) as the reference point, while if you cross the boundary an odd number of times you are on the opposite side. You just need to choose a reference point a point that you know whether it is inside or outside. Finding a point outside is easy because you can just go through your vertices and find the maximum x and y coordinates and then choose the point <xmax+1,ymax+1>.
The 'best/most efficient' way depends on how the object data structure information is stored as graphic primitives.
Here is a good list of scan conversion methods http://www.cs.berkeley.edu/~ddgarcia/cs184/r3/
Here is a good list of scan conversion methods http://www.cs.berkeley.edu/~ddgarcia/cs184/r3/
Thanks for the inputs.
Actually, I am doing image processing. The shape here is arbitrary. First, I get the coordinates of outline points and save them into an array called pointArray.
After that I want to find the coordinates of all points inside the shape and save them into an other array for further processing.
WBahn's method is OK but there seems to be a lot of work to do here.
1. Convert the arbitrary shape into a polygon (need to derive a lot of line equations)
2. Scan and find intersections, count the number of intersections on each side
I also thought about another algorithm "flood fill" but there is also problem.
1. Outline and we get all points of the shape
2. Seed a points inside the shape and then use flood fill algorithm to find coordinates of points inside the shape
However, there is a problem with this method.
Assuming that there is a noise inside the shape and after outline step we get two shapes (big and small one) as in the picture.
If I use "flood fill" method, I couldn't get the coordinates of points inside the small shape.
PS. I can get the coordinates of points on the shape. Now the problem is about getting coordinates of points inside that shape.
Actually, I am doing image processing. The shape here is arbitrary. First, I get the coordinates of outline points and save them into an array called pointArray.
After that I want to find the coordinates of all points inside the shape and save them into an other array for further processing.
WBahn's method is OK but there seems to be a lot of work to do here.
1. Convert the arbitrary shape into a polygon (need to derive a lot of line equations)
2. Scan and find intersections, count the number of intersections on each side
I also thought about another algorithm "flood fill" but there is also problem.
1. Outline and we get all points of the shape
2. Seed a points inside the shape and then use flood fill algorithm to find coordinates of points inside the shape
However, there is a problem with this method.
Assuming that there is a noise inside the shape and after outline step we get two shapes (big and small one) as in the picture.
If I use "flood fill" method, I couldn't get the coordinates of points inside the small shape.
PS. I can get the coordinates of points on the shape. Now the problem is about getting coordinates of points inside that shape.
Apparently I misunderstood what you were asking for in the OP, but now I'm really not sure.
I thought you had a set of random points, some of which were inside the shape and some of which were outside the shape, and you wanted an algorithm to identify the points that are inside.
What are the "points" that you are talking about here?
How many points are we talking about, both border points and points that must be filtered?
I thought you had a set of random points, some of which were inside the shape and some of which were outside the shape, and you wanted an algorithm to identify the points that are inside.
What are the "points" that you are talking about here?
How many points are we talking about, both border points and points that must be filtered?
Hi,
Assuming that in the picture, I have coordinates of all points (border points) on the larger black curve.
Now I want to get the coordinates of all points inside the larger black curve.
What is the algorithm to do that?
Your algorithm is OK.
I have another idea is using "flood fill" to find the coordinates of all points inside the larger
black curve but it doesn't work in case of there is a small curve inside the larger one.
Assuming that in the picture, I have coordinates of all points (border points) on the larger black curve.
Now I want to get the coordinates of all points inside the larger black curve.
What is the algorithm to do that?
Your algorithm is OK.
I have another idea is using "flood fill" to find the coordinates of all points inside the larger
black curve but it doesn't work in case of there is a small curve inside the larger one.
Hello,
Hire a very very tiny mouse
This is tricky for some general shape with no constraint on how it can fold and twist and turn. For example, take a general closed spiral curve and try to solve whether or not a point is inside the spiral. That would be easy knowing it is a spiral with the end closed, but what if the closure could be anywhere in the spiral...then we'd have to figure out if the point lies in a passageway after the closure or before it, which tells us if it is really completely enclosed.
So it sounds like we would have to start from the point and search in all directions looking for a doorway. If we find a doorway then we have to explore that region too looking for other doorways. Almost like trying to find your way out of a maze. If you dont find your way out ever, then the point must be inside, otherwise it is not.
Maybe it would work to somehow transform the shape itself before starting. This would mean searching the shape one time and assigning field numbers to areas inside/outside. This might involve approaching the shape from all angles on the outside searching for entrances.
I suppose this deserves more thought.
Hire a very very tiny mouse
This is tricky for some general shape with no constraint on how it can fold and twist and turn. For example, take a general closed spiral curve and try to solve whether or not a point is inside the spiral. That would be easy knowing it is a spiral with the end closed, but what if the closure could be anywhere in the spiral...then we'd have to figure out if the point lies in a passageway after the closure or before it, which tells us if it is really completely enclosed.
So it sounds like we would have to start from the point and search in all directions looking for a doorway. If we find a doorway then we have to explore that region too looking for other doorways. Almost like trying to find your way out of a maze. If you dont find your way out ever, then the point must be inside, otherwise it is not.
Maybe it would work to somehow transform the shape itself before starting. This would mean searching the shape one time and assigning field numbers to areas inside/outside. This might involve approaching the shape from all angles on the outside searching for entrances.
I suppose this deserves more thought.
Exactly my question.
I add: is the shape a closed curve? Is the concept of "pixel" valid here?
Hello again,
I believe that what Mr. Al said is the "flood fill" algorithm. I tried that algorithm and there is some problems because mostly there is noise inside the shape.
@atferrari
What are the "points" that you are talking about here?
As I said in post #10:
The border point coordinates are already known.
Goal: find and save the coordinates of all points inside that border
How many points are we talking about, both border points and points that must be filtered?
Not sure if I understand your question.
I add: is the shape a closed curve? Is the concept of "pixel" valid here?
Yes and yes. I am doing image processing and the shape is a closed curve (with pixel not closed mathematically because they are digital not analog).
I believe that what Mr. Al said is the "flood fill" algorithm. I tried that algorithm and there is some problems because mostly there is noise inside the shape.
@atferrari
What are the "points" that you are talking about here?
As I said in post #10:
The border point coordinates are already known.
Goal: find and save the coordinates of all points inside that border
How many points are we talking about, both border points and points that must be filtered?
Not sure if I understand your question.
I add: is the shape a closed curve? Is the concept of "pixel" valid here?
Yes and yes. I am doing image processing and the shape is a closed curve (with pixel not closed mathematically because they are digital not analog).
Are these points that you are trying to find points that are in some data structure, some of which are inside the border and some of which are outside the border, and you are trying to identify the subset of points that are inside the border? If so, then it would seem like using a flood fill approach would be hugely inefficient since you would have to check every pixel within the borders against the list of points. And you still have to do the computations to detect when you hit a boundary. Instead, why not just check the list of points themselves directly against the boundaries as you walk outward from that point?
Why wouldn't math work? If you have the X Y coordinates of points that define the boundary then you HAVE what is contained therein.
100, 100 is a boundary and there exists another that is 120, 100
Automatically all X coordinates between 100 and 120 with a Y value of 100 can be included. Logic checks on positions with more than two X VALUES FOR EACH Y VALUE will give you other sets to include on those lines.
You only need to compute one coordinate mathematically as you step through the other coordinate at a rate of 1.
If this is what is being called fill then excuse my old bones
100, 100 is a boundary and there exists another that is 120, 100
Automatically all X coordinates between 100 and 120 with a Y value of 100 can be included. Logic checks on positions with more than two X VALUES FOR EACH Y VALUE will give you other sets to include on those lines.
You only need to compute one coordinate mathematically as you step through the other coordinate at a rate of 1.
If this is what is being called fill then excuse my old bones
@WBahn:
Are these points that you are trying to find points that are in some data structure, some of which are inside the border and some of which are outside the border, and you are trying to identify the subset of points that are inside the border?
Actually, I have two data structures but if I can solve one, the other also OK.
Data structure 1:
I have two arrays saving coordinates of points.
Array 1: containing coordinates of all borders points
Array 2: containing coordinates of all points including outside, border and inside points
Goal: sort out all points inside the border in array 2
Data structure 2:
I have only one array saving the coordinates of border points.
Goal: find and save the coordinates of all points inside that border
Note: in two cases, I can know before one point inside that border (if you need that)
If so, then it would seem like using a flood fill approach would be hugely inefficient since you would have to check every pixel within the borders against the list of points. And you still have to do the computations to detect when you hit a boundary.
With flood fill (already know one point inside the border), from this point I enlarge and save all points inside the border.
That way, I only have to check all points inside the border against border points).
Instead, why not just check the list of points themselves directly against the boundaries as you walk outward from that point?
Not sure how you would do that?
@Kermit2:
I believe your algorithm only works for simple shape not arbitrary one. I need to try if there is a flaw here.
However, it also seems inefficient as there is lots of scan here.
Are these points that you are trying to find points that are in some data structure, some of which are inside the border and some of which are outside the border, and you are trying to identify the subset of points that are inside the border?
Actually, I have two data structures but if I can solve one, the other also OK.
Data structure 1:
I have two arrays saving coordinates of points.
Array 1: containing coordinates of all borders points
Array 2: containing coordinates of all points including outside, border and inside points
Goal: sort out all points inside the border in array 2
Data structure 2:
I have only one array saving the coordinates of border points.
Goal: find and save the coordinates of all points inside that border
Note: in two cases, I can know before one point inside that border (if you need that)
If so, then it would seem like using a flood fill approach would be hugely inefficient since you would have to check every pixel within the borders against the list of points. And you still have to do the computations to detect when you hit a boundary.
With flood fill (already know one point inside the border), from this point I enlarge and save all points inside the border.
That way, I only have to check all points inside the border against border points).
Instead, why not just check the list of points themselves directly against the boundaries as you walk outward from that point?
Not sure how you would do that?
@Kermit2:
I believe your algorithm only works for simple shape not arbitrary one. I need to try if there is a flaw here.
However, it also seems inefficient as there is lots of scan here.
Consider the following:
You have an array consisting of the red points.
That array defines a bunch of line segments. Make an ordered list of line segments that are ordered according to the smallest y-coordinate of the two points that make up the line segment.
You also find the largest x-coordinate of any point on the border and then add something, anything, to it. That will be the x-coordinate of the right end of the green line.
Now consider the point at the left end of the green line -- that's the point we are trying to determine whether or not it is inside the shape. So we construct the green line whose left end is at the point and whose right end is at the fixed max x-coordinate and is horizontal.
We now walk through our ordered array of line segments until we reach the first point that starts out higher than the y-coordinate of the green line (since that, and all subsequent segments, will be above the green line entirely). This the figure above that means we will only examine nine line segments. We can immediately eliminate any segments for with the second coordinate is also below the line. That leaves us with only six line segments to examine in detail. We now call a function that determines if the green line segment intersects a give border line segment. This will give false for the left most and true for the remaining five. Since this number is odd, we know that the point is located inside the shape (since we know that the right end of the green line is outside the shape).
The special cases that need to be considered involve line segments that lie exactly on the green line. Examine each possibility separately and decide if the algorithm above will produce the correct result of if it needs to be tweaked.
You have an array consisting of the red points.
That array defines a bunch of line segments. Make an ordered list of line segments that are ordered according to the smallest y-coordinate of the two points that make up the line segment.
You also find the largest x-coordinate of any point on the border and then add something, anything, to it. That will be the x-coordinate of the right end of the green line.
Now consider the point at the left end of the green line -- that's the point we are trying to determine whether or not it is inside the shape. So we construct the green line whose left end is at the point and whose right end is at the fixed max x-coordinate and is horizontal.
We now walk through our ordered array of line segments until we reach the first point that starts out higher than the y-coordinate of the green line (since that, and all subsequent segments, will be above the green line entirely). This the figure above that means we will only examine nine line segments. We can immediately eliminate any segments for with the second coordinate is also below the line. That leaves us with only six line segments to examine in detail. We now call a function that determines if the green line segment intersects a give border line segment. This will give false for the left most and true for the remaining five. Since this number is odd, we know that the point is located inside the shape (since we know that the right end of the green line is outside the shape).
The special cases that need to be considered involve line segments that lie exactly on the green line. Examine each possibility separately and decide if the algorithm above will produce the correct result of if it needs to be tweaked.
A point is inside the shape if a line from that point to infinity in any direction crosses the boundary an odd number of times. This might allow you to simplify WBahn's suggestion a little. Here's one suggestion for a line crossing algorithm
http://stackoverflow.com/questions/...lliding-only-check-if-they-are-intersecting-n
Just as aside, one way of sorting points for easier searching in some cases is to interleave the X and Y digits, so, represent all coordinates as say 4 digits (pad with leading zeros) and then add to a sorted list as xd1yd1xd2yd2xd3yd3xd4yd4 so the coordinate 0001,9990 becomes
09090910. This has the effect of putting coordinates that are "near" each other close together in the list and allows quick elimination of points which are far away from the area of concern.
http://stackoverflow.com/questions/...lliding-only-check-if-they-are-intersecting-n
Just as aside, one way of sorting points for easier searching in some cases is to interleave the X and Y digits, so, represent all coordinates as say 4 digits (pad with leading zeros) and then add to a sorted list as xd1yd1xd2yd2xd3yd3xd4yd4 so the coordinate 0001,9990 becomes
09090910. This has the effect of putting coordinates that are "near" each other close together in the list and allows quick elimination of points which are far away from the area of concern.
Last edited:
How is that any different than my suggestion (see Post #3 for the original suggestion)?
Interesting. Does it really help in this case? If I am starting from the bottom and working up (in terms of boundary points), it would seem that any point that is below the green line (the y-coordinate of the point under consideration) must be evaluated regardless of it's x-coordinate since I could find coordinates for the other point that would either force it to intersect or force it to not intersect. But I wonder if interleaving the y-coordinates and sorting on that might be useful.... Have to think about that.
@anhnha While these suggestions about ways to make the algorithm more efficient are definitely worth exploring at some point, the first thing you need to do is just get an algorithm that works on sufficiently small data sets (and a dozen or so boundary points and a dozen or so candidate points are probably good to start with -- hand pick them to cover all of the possible situations you can think of, including when points are exactly in line with the various types of vertices). For that, you don't need to sort your list of boundary points at all, just simply check if the green line intersects each boundary segment and count the number of times it does. If you haven't got that approach working, then there is no point in trying to make it more efficient until you do.
Didn't say it was (and TBH didn't read the whole thread). I first wrote algorithms of this type in 1987 and have repeated the exercise a number of times since. I was just chipping-in my experience, not trying to steal anyone's thunder.
As for: does that sort technique help, well it depends hence why I put it in as an aside. If one were to define a bounding rectangle around the shape then it possibly helps to speed up eliminating points that are outside the shape. Many of the possible optimisations have an overhead and hence whether they really speed things up is often dependent on set size, it could cost more than it is worth to use an optimisation on a small set.
