Test Whether A Point Is In A Polygon Or Not

[Rick Rothstein]

Hi Rick,

first thanks for sharing your code, it has been very useful to me. Similar to theCloud, i work with aircraft center of gravity and needed a function similar to yours. However I had some problems:
1- when a point was on a vertical boundarie
2- when a point was on an horizontal boundarie
3- when comparing two Double variable (b = Ycoord)...so I replace Double by Single and it works for now...I might need to use Double in the future, we'll see how it goes

For point numbers 1 and 2, I would refer you to my Note #3. You should not be overly fixated on points lying on the boundary of your polygon. Too many things can affect whether a point actually lies on the boundary. VB's floating point math is not infinite in scale, so the numbers have a limited precision (15 decimal places) and each number in a calculation theoretically degrades the accuracy of the calculated number to the point that you can never be sure if the calculated coordinate really lies on the boundary or not. For example, let's assume point is actually on the boundary... what is the significance if that is considered inside or outside the polygon on a practical level. Given that a theoretical boundary line for a polygon has zero thickness, then if the point was a millionth, trillions, zillions or whatever further away, it would be considered outside the polygon... similarly, if the point were as millionth, trillions, zillions or whatever closer in, it would be considered inside the polygon. At a practical level, either of those points (the further out one or the closer in one) could be considered the same point (what is the practical significance of two points that are a trillions of a inch, millimeter or whatever units of measurement?) So whether a real boundary point calculates inside or outside of the polygon should have absolutely no real world significance at all.

As for changing Doubles to Singles... I would not do that as it lessens the accuracy of all calculations that take place in the routine increasing the chance that a point in the vicinity of the boundary, but not truly "next to" or "on" it might calculate to the wrong side. Rather than making Doubles into Singles, leave them as Doubles and when comparing them, round each of the values down to the same number of decimal place (you choose the number of decimal places that is significant to you) and then compare those rounded down values instead.

]

[hugohonda]

For point numbers 1 and 2, I would refer you to my Note #3. You should not be overly fixated on points lying on the boundary of your polygon. Too many things can affect whether a point actually lies on the boundary. VB's floating point math is not infinite in scale, so the numbers have a limited precision (15 decimal places) and each number in a calculation theoretically degrades the accuracy of the calculated number to the point that you can never be sure if the calculated coordinate really lies on the boundary or not. For example, let's assume point is actually on the boundary... what is the significance if that is considered inside or outside the polygon on a practical level. Given that a theoretical boundary line for a polygon has zero thickness, then if the point was a millionth, trillions, zillions or whatever further away, it would be considered outside the polygon... similarly, if the point were as millionth, trillions, zillions or whatever closer in, it would be considered inside the polygon. At a practical level, either of those points (the further out one or the closer in one) could be considered the same point (what is the practical significance of two points that are a trillions of a inch, millimeter or whatever units of measurement?) So whether a real boundary point calculates inside or outside of the polygon should have absolutely no real world significance at all.

As for changing Doubles to Singles... I would not do that as it lessens the accuracy of all calculations that take place in the routine increasing the chance that a point in the vicinity of the boundary, but not truly "next to" or "on" it might calculate to the wrong side. Rather than making Doubles into Singles, leave them as Doubles and when comparing them, round each of the values down to the same number of decimal place (you choose the number of decimal places that is significant to you) and then compare those rounded down values instead.

Hi Rick,

first, thanks for your quick reply. I like your idea with using the round function with Doubles...I implemented it and it works great now.

As for my point numbers 1 and 2, I understand everything you mentioned and you are absolutely right. The thing is, I'm plotting different weight (y axis) and center of gravity (x axis) of an aircraft into a "Flight Envelope" and all point needs to be inside the envelope otherwise it isn't safe to fly. In order to find if a specific aircraft configuration (weight and CG) is dangerous to fly, I had to modify the code as mentioned before.

I know that the specific aircraft configuration touching the boundary, theoretically, won't be exactly on the line because like you mentioned, "a line has no thickness" but it will give me, I think, a very accurate aircraft configuration at which it is dangerous to fly.

I don't know if i'm clear but this is why i'm concerned about boundary.

I tested my code with many case scenarios and all of them give me a good result so far

thanks again!

[Rick Rothstein]

As for my point numbers 1 and 2, I understand everything you mentioned and you are absolutely right. The thing is, I'm plotting different weight (y axis) and center of gravity (x axis) of an aircraft into a "Flight Envelope" and all point needs to be inside the envelope otherwise it isn't safe to fly. In order to find if a specific aircraft configuration (weight and CG) is dangerous to fly, I had to modify the code as mentioned before.

You are talking about aircraft and you are worried about what amounts to infinitesimally small fractions of an inch? I think you are being overly trusting in the supposed accuracy of numerical calculations on a computer. All floating point calculations on a computer are approximations Unless your numbers have power of 2 factors, the conversion from the decimal system we work in to the binary system computers use will involve rounding errors out at the 15th or 16th decimal place which will propagate with each calculation you do with those numbers... that is why the "which side of the line with no thickness" problem is an issue at all... small changes out in the 15th or 16th decimal place are more than enough to move a calculated point onto either side of a line with no thickness. Just so you know, what I discussed about points near the border applies to all borders, not just horizontal or vertical ones. If you really want to be "safe" (your word, not mine), you should shrink your polygon by some percentage that you are comfortable with so that it does not matter which side of a boundary line a boundary point falls on.