MATH math math.

This is a simple problem if you apply a two coordinate grid system to it.
As example. A point inside your boundary is defined with an X and Y coordinate. Keeping the Y coordinate the same you will have two boundary coordinates, one of which is smaller than your point in X value and one which is larger in X value. Keeping your X coordinate the same you will have two boundary coordinates , one of which is smaller than your point in Y value and one which is larger.
IF THESE TWO CONDITIONS ARE NOT BOTH TRUE the point is NOT inside your boundary.
For a more complicated shape such as a circle with a smaller circle inside the logic becomes harder, but can be done with checks on odd or even amounts of points which are larger or smaller. Always though, the rule above will remain true.
MATH math math

 

Hi,

Does the line to infinity algorithm really work? I dont think so if i understand you guys right.
The reason i dont believe it works is because you can cross the boundary an even or odd number of times with either a closed surface or an open surface. But as i suggested earlier, you can check your algorithm using two shapes:
1. An open ended spiral
2. A closed ended spiral

If it works for both of these shapes then it probably works for any shape, as long as you dont assume too much about the spiral shape (can have some straight lines or curved lines).

Of course the ultimate test is using a maze with some closed chambers. If you can find your way out of the maze from any point, and determine that you definitely cant get out of the maze from some points, then you probably have a good algorithm. A maze inside another maze would be a really good test, where the first maze can be anywhere in side the second larger maze, and either in contact with the first maze or not in contact with it, and inside any starting chamber.

One algorithm that would work is to generate finite length lines in all directions. That would probably take a lot of time though. This would be similar to a flood fill but mathematically would not be the same unless the shape was discretized, which also brings up that issue.

Wall Following...
Another algorithm comes to mind is to follow the lines that make up the shape with a point while keeping track of the original starting point on the shape. If you can circle back to reach the original point without having to make any 'jumps' then the test point must be inside. To start you would draw perhaps a horizontal line from the point to one of the 'walls' of the shape. The intersection would be the starting point on the wall. Now following the wall around and round until it either reaches an end point (wall line ends abruptly) or it leads back to the original point. If you come to a junction, you must turn in the same direction as the relation of the original start point and the internal test point, so if the test point was to the left when you started then you must always turn left when you reach a junction. However, if you do reach a junction and then reach an end point, you have to double back and turn right at the junction and then follow the left hand rule again unless you find another junction, etc.
Example: two circles connected by a pipe, where one circle might be open, starting inside the known closed circle. Drawing a horizontal line from the test point to the circle wall to the right, the test point is therefore on the left, so always turn left if you hit a junction and then follow the junction rule. Following the circle around and then though one wall of the pipe leads to the other circle, then around that circle, then for a closed second circle we would get led back to the pipe second wall, then back to the original circle, then back to the original point, so here we know the second circle is closed too so we know the test point is inside the shape. If the second circle was open however, we would have ended up at an end point of the wall of the circle and with no junction points behind us, that means the second circle is open so the point is not inside, at least from the point of view of the starting point at the right side of the test point. If this happens then we must go back to the test point and start traveling in the other direction and do the same thing but always turn right. If that too ends up with an end point with no junctions behind us, then the test point is not inside. If we end up back at the starting point, then it is inside.
This is just a quick thought so it may require a little more thought to get it to work, but that seems complete so far.
For example, for an open spiral inside a larger circle which does not touch the spiral, we'd have to create another starting point by allowing the horizontal test line to extend through all walls of the shape. There is a chance we might have to generate a vertical test line too though, or in certain cases it may work better with a vertical line.

The issue of discetization also comes up. To speed up the algorithm we probably have to assume some small step, which then puts a limit on the resolution of the shapes we can deal with.

 

MATH math math.

This is a simple problem if you apply a two coordinate grid system to it.
As example. A point inside your boundary is defined with an X and Y coordinate. Keeping the Y coordinate the same you will have two boundary coordinates, one of which is smaller than your point in X value and one which is larger in X value. Keeping your X coordinate the same you will have two boundary coordinates , one of which is smaller than your point in Y value and one which is larger.
IF THESE TWO CONDITIONS ARE NOT BOTH TRUE the point is NOT inside your boundary.

This is only the case if the shape is convex. Look at any of the examples that the TS has posted. Look at the example I posted.

For a more complicated shape such as a circle with a smaller circle inside the logic becomes harder, but can be done with checks on odd or even amounts of points which are larger or smaller.

You don't need to have shapes within shapes to cause this more complicated situation to arise. Consider the figure below.

What you describe for the more complicated shape is nothing more than the boundary crossing algorithm that was recommended clear back in Post #3, except you are quadrupling the amount of computation because you are telling them to check to the left, to the right, up, and down. You only need to check in ONE arbitrary direction.

 

Hi,

Does the line to infinity algorithm really work? I dont think so if i understand you guys right.
The reason i dont believe it works is because you can cross the boundary an even or odd number of times with either a closed surface or an open surface. But as i suggested earlier, you can check your algorithm using two shapes:
1. An open ended spiral
2. A closed ended spiral

If the shape is open, then there IS no "inside" of the shape to check for -- or rather both "inside" and "outside" are the same thing. The TS is only talking about closed shapes.


If it works for both of these shapes then it probably works for any shape, as long as you dont assume too much about the spiral shape (can have some straight lines or curved lines).

Of course the ultimate test is using a maze with some closed chambers. If you can find your way out of the maze from any point, and determine that you definitely cant get out of the maze from some points, then you probably have a good algorithm. A maze inside another maze would be a really good test, where the first maze can be anywhere in side the second larger maze, and either in contact with the first maze or not in contact with it, and inside any starting chamber.

One algorithm that would work is to generate finite length lines in all directions. That would probably take a lot of time though. This would be similar to a flood fill but mathematically would not be the same unless the shape was discretized, which also brings up that issue.

Wall Following...
Another algorithm comes to mind is to follow the lines that make up the shape with a point while keeping track of the original starting point on the shape. If you can circle back to reach the original point without having to make any 'jumps' then the test point must be inside. To start you would draw perhaps a horizontal line from the point to one of the 'walls' of the shape. The intersection would be the starting point on the wall. Now following the wall around and round until it either reaches an end point (wall line ends abruptly) or it leads back to the original point. If you come to a junction, you must turn in the same direction as the relation of the original start point and the internal test point, so if the test point was to the left when you started then you must always turn left when you reach a junction. However, if you do reach a junction and then reach an end point, you have to double back and turn right at the junction and then follow the left hand rule again unless you find another junction, etc.
[/QUOTE]

Huh?

Consider a square with a point outside the square, say to the left of it and centered vertically on it. Draw a horizontal line from the point to the right until you hit the square. Now go around the square until you get back to the starting point. No problem, so does this mean that this point must be inside the square?

If you draw a line from the point in question to any vertex, then you can track the angle swept out as you move from one vertex to the next. After going around all of the boundary vertices, you Once you complete the trip around the shape, the net angle subtended will be either 0° or 360°. If the former then you are outside and if the latter you are inside. But this is a very inefficient algorithm because it requires that you visit every vertex for every candidate point.

 

Hello again,

Yes i had mentioned that this needs more thought, but i believe that the wall following algorithm is a precursor to a quicker method. The problem seems to be one of surface area, which has n^2 complexity while a boundary only has n^1 complexity. This would seem to make it faster.
For example, for the point outside the square we would have found two paths to follow, not just one, and both ways would have led us around the very same path just in opposite directions. If this logic was added to the wall following algorithm, then that would have eliminated the detached square.
Granted this still needs more thought, but i would hate to have to scan the entire surface area looking for a hole in one of the walls, and i dont want to have to assume any type of boundary curve such as all straight lines. If we did have straight lines however then this would search pretty quickly because then only the endpoints would be of importance. If the sides were made up of cubic splines then that would help too, making it much faster, but im not sure what the OP wants to impose here as to the allowed shapes and curves.

 

Yes i had mentioned that this needs more thought, but i believe that the wall following algorithm is a precursor to a quicker method. The problem seems to be one of surface area, which has n^2 complexity while a boundary only has n^1 complexity. This would seem to make it faster.

What is the 'n' in your complexity claim? To be meaningful, it must be either the number of points that have to be graded as being inside vs. outside or it has to be the number of points in the boundary definition. If it is the area vs. perimeter, then that only matters if the algorithm for a large square is going to take disproportionately long than the algorithm for a small square. The only algorithm (that I'm aware of) that has been proposed that would fall into this category is the flood fill algorithm, which is a particularly poor way do go about this.

For example, for the point outside the square we would have found two paths to follow, not just one, and both ways would have led us around the very same path just in opposite directions. If this logic was added to the wall following algorithm, then that would have eliminated the detached square.

And if the point was inside the square you would have found two paths to follow, not just one, and both ways would have led you around the very same path just in opposite directions. So how does that help. And what is this "detached square"?

Granted this still needs more thought, but i would hate to have to scan the entire surface area looking for a hole in one of the walls, and i dont want to have to assume any type of boundary curve such as all straight lines. If we did have straight lines however then this would search pretty quickly because then only the endpoints would be of importance. If the sides were made up of cubic splines then that would help too, making it much faster, but im not sure what the OP wants to impose here as to the allowed shapes and curves.

The TS was actually pretty explicit about the allowed shape. He stated that the first thing he does is store the points that define the shape into an array. That, plus the picture provided by the TS, means that we may restrict the discussion to closed shapes that are defined by the N line segments connecting an ordered set of N points in a 2-D plane.

 

Hello,

Thanks for clarifying that the shape is defined by an array of points. That helps for sure. Did the OP also state that straight line connections would be ok too, or perhaps something like cubic splines instead? That would matter of course.

As to your second paragraph, for the point outside the square we would find TWO paths to follow because it would find TWO points from the horizontal line test:
1. A point on the line that makes up the left side of the square
2. A point on the line that makes up the right side of the square.

whereas for the point inside the square, there is only one line to the right so we would only find one point and that would be the point on the right side of the square. Going farther to the right would not reveal any more points unless the square was also inside another square, but we would not have to pursue that line of thought unless we found that the first square was open somewhere, which would have led to an end point with no junctions behind us to pursue.
This doesnt mean the algorithm is complete yet however, as i tried to make clear, but your kind of thinking is what could lead to a good solution. Of course you are always free to look for other ideas too.

The complexity issue i mentioned comes from a simple view of how complex area is vs circumference (or border). For a square shape described by 10 points on each side, there are 100 points inside the square (including the border) and only 38 points on the border itself, a ratio of 0.38. Thus the border is less complex than the area. For 100 points on each side, there are 10000 points inside and 398 inside, for a ratio of 0.0398. For 1000 points on each side there are 1000000 points on the inside and 3998 on the border, for a ratio of 0.00398. So the border is approximately N*4 while the area is N^2. The ratio is thus approximately 4/N, which means the border can have significantly less points.

 

As to your second paragraph, for the point outside the square we would find TWO paths to follow because it would find TWO points from the horizontal line test:
1. A point on the line that makes up the left side of the square
2. A point on the line that makes up the right side of the square.

whereas for the point inside the square, there is only one line to the right so we would only find one point and that would be the point on the right side of the square. Going farther to the right would not reveal any more points unless the square was also inside another square, but we would not have to pursue that line of thought unless we found that the first square was open somewhere, which would have led to an end point with no junctions behind us to pursue.
This doesnt mean the algorithm is complete yet however, as i tried to make clear, but your kind of thinking is what could lead to a good solution. Of course you are always free to look for other ideas too.

I think I need to see a diagram of what you are trying to convey, because I'm just not seeing it through words alone.

The complexity issue i mentioned comes from a simple view of how complex area is vs circumference (or border). For a square shape described by 10 points on each side, there are 100 points inside the square (including the border) and only 38 points on the border itself, a ratio of 0.38. Thus the border is less complex than the area. For 100 points on each side, there are 10000 points inside and 398 inside, for a ratio of 0.0398. For 1000 points on each side there are 1000000 points on the inside and 3998 on the border, for a ratio of 0.00398. So the border is approximately N*4 while the area is N^2. The ratio is thus approximately 4/N, which means the border can have significantly less points.

But this is only applicable if you are going to examine every point -- and it also requires a Manhattan geometry (i.e., strictly vertical or horizontal border segments) -- which means something akin to the flood fill approach which everyone has been saying NOT to use.

 

Years ago I wrote a program in LISP for AutoCAD solving the same problem. The simplest way to do it is separating the involving shape in vectors. Converting each side of the shape into a vector, and analyzing whether the point in question lies either to the left or to the right of each vector, depending also on the angle of the previous vector being analyzed (is it more or less than 180° ?).

Hint: The trick lies in considering resulting sign of vector multiplication.

If the sides are arches, a special function has to be considered, but it's still the very same problem with the same solution in the end.

Need I say more?

 

I'm not sure, but I think part of what you are talking about (the part about considering the sign of vector multiplication) is dealing with whether two line segments intersect. If you take two vectors (the boundary segment and the vector from the start of the segment to the point in question) then taking the cross product will give you a vector in the z-direction whose sign depends on which side of the boundary vector the point is on. You then repeat using your end point that is known to be outside the shape. If the two z-vectors have opposite signs, then the two endpoints are on opposite sides of the boundary vector. But that's not enough to see if they intersect. You must repeat the process using the line segment originating at the point in question to see if the two endpoints of the boundary vector are on opposite sides. If so, then the two segments intersect.

So that's four cross products that have to be taken, but cross products in 2-D aren't very onerous and since they only involve two multiplications and one addition each.

 

The way I remember I wrote that program involved analyzing (assuming there were no adjacent sides to the polygon that had an angle greater than 180° between them, as a first approach) if the point always lied to the left (if the shape was drawn counter-clockwise) or to the right (if the shape was drawn clockwise) of each vector. That is why multiplying the previous vector with the current one was important. The resulting sign would tell you if the side was turning left or right, relative to the previous side.
If the shape had sides with an angle greater than 180° then the analysis would be reversed on the side being processed. But the logic was essentially the same.
Of course, the first condition that had to be met was to determine if the shape enveloping the point in question was geometrically defined as closed.

 

The way I remember I wrote that program involved analyzing (assuming there were no adjacent sides to the polygon that had an angle greater than 180° between them, as a first approach)

Ah, but that is a key, and invalid, assumption! If that assumption holds, then the shape is convex and, as pointed out in Post #3, you can greatly simplify the process. But the shapes in question do not have to be convex.

If the shape had sides with an angle greater than 180° then the analysis would be reversed on the side being processed. But the logic was essentially the same.

I'm not sure I buy this. I'll have to think about it. In my mind I'm thinking of a zig-zag wall and how reversing things would yield the desired results. I'm not convinced it would.

 

...I'm not sure I buy this. I'll have to think about it. In my mind I'm thinking of a zig-zag wall and how reversing things would yield the desired results. I'm not convinced it would.

Let me take a look at my so-last-century code and I'll be back with a more convincing answer.

 

Let me take a look at my so-last-century code and I'll be back with a more convincing answer.

Sounds good. And if I get a chance I'll sketch out the scenario I have in mind that is bothering me.

 

Alright W, my friend. I've always liked a good challenge, especially in areas in which I'm supposed to be good at. Let's just hope that I don't say something stupid here...


Here's my algorithm, from many years ago.

Limitations:

1. The shape is composed of straight lines only. Shapes with arches (or bulges, as we AutoCAD geeks like to call them) can be processed using this same algorithm, but additional steps are required.
2. The shape has no intersecting sides. Otherwise "islands" in the shape would be created and things would be very messy to process.

Let's start with this shape, with some points added for analysis:

​

Step one: Determine if the shape is drawn either clockwise or counter-clockwise. This is easily done by first choosing an arbitrary vertex, and then converting all of the sides into vectors, as shown.

​

We then multiply the first vector with the second one, and then the second one with the third, and the third with the fourth, and so on. In the end we add all the results of these multiplications and the resulting sign of their addition will tell us the direction in which it is drawn.

Step Two: For each point being analyzed, find the closest side in the shape to that point. Draw a vector from the point that is perpendicular to that side.

​

Step Three: Multiply the point-to-side vector with its corresponding closest-side-vector. The result's sign will tell you if the point is inside or outside the shape, depending if the shape was drawn clockwise or counter-clockwise.

Are you persuaded now?

 

Cmartinez: In Step 1, you don't specify when to stop. When you multiply side n with side 1?

 

Cmartinez: In Step 1, you don't specify when to stop. When you multiply side n with side 1?

Good point. Yes, as you've just said, you stop when you multiply the last side with the first one.

 

I think I need to see a diagram of what you are trying to convey, because I'm just not seeing it through words alone.



But this is only applicable if you are going to examine every point -- and it also requires a Manhattan geometry (i.e., strictly vertical or horizontal border segments) -- which means something akin to the flood fill approach which everyone has been saying NOT to use.

Hello again,

Yes, i dont think you've understood the basic procedure. Also not sure how you can equate following walls with a flood fill.
Granted it may need more thought, but this method does not put any restrictions on the shape.
BTW, a "junction point" is a point where two sides join, such as a shape made with two circles that intersect. These two circles would have two junction points unless they were the same size with centers in the exact same position.
I'll try to get around to making some drawings.

 

I think I agree that this works, but it seems like a very different algorithm than the one you described previously. In that algorithm, you talked about reversing things if the angle was more than 180° for a given vertex, yet here you don't mention anything about that at all.

Also, Step 2 seems computationally expensive. Once you know which vector a given point is closest two, coming with the normal vector to it isn't too bad, but how much computation is involved in deciding which vector it is closest to? And what about points for which the normal vector to the nearest boundary vector doesn't intersect the boundary segment at all? How do you deal with those?

 

Hello again,

Yes, i dont think you've understood the basic procedure. Also not sure how you can equate following walls with a flood fill.

The point I'm making about the flood fill has nothing to do with following walls, it has to do with the claim that working with the boundaries is O(n) and working with the area is O(n²). That would apply to a flood fill algorithm. It does not apply to any of the other algorithms, such as counting the number of boundary segments crossed in going from a candidate point to "infinity", that have been recommended.