Finding if a point is inside of an drawn area or not

[TikkaMasala]

Hi

I try to make a relatively simple program how to find if a point is inside an drawn area or not.

The problem is illustrated in the attached calculation sheet.

Thank you for your advices in advance.

[AlanStevens]

The attached has a simple routine to do what you want (I hope!).

It needs to be tested more extensively and should probably be vectorised, but I'll leave that to you.

Alan

[MikeArmstrong]

Nice work Alan. I started to write a routine going down a similar route to what you have and then realised I have actual work to do

[TikkaMasala]

Hi Alan

Thanks for your programmin work.

I tested your code a bit, but unfortunately at least one point resulted into incorrect answer,

see attached.

[MikeArmstrong]

Are you talking about the variables you manually inputted?

I think Alan's code works.

[AlanStevens]

No I've just tested it further myself and it's not correct! I'll have to think some more!

Alan

[MikeArmstrong]

The 2,90 point in question works though.

[Werner_E]

The point in question was the second point in the table (4/70).

[MikeArmstrong]

Sorry my mistake, I have just re-read Matti's comment and he said 'at least one point resulted into incorrect answer,', when I thought he said the 'last' point.

[AlanStevens]

Attempt number 2 attached!

Alan

Edit: I should add that I've assumed the points that define the area will always be entered in anticlockwise order around the boundary.

[Werner_E]

Edit: I should add that I've assumed the points that define the area will always be entered in anticlockwise order around the boundary.

anticlockwise? So you also assume the polygon being convex? Or at least you assume the polygon is not "selfcrossing", e.g. like the infinity sign or the number eight.

@Matti: From the text in your file it looks like you would be happy if you could test if a point is inside the smallest rectangle including all the points. Is this correct or did I misinterprete your text? If its correct that would be easy to achieve, otherwise I wouldn't call it "a more simple issue", as you did. 😉

The problem itself (if it really should be an exact point in polygon test) is well covered in the literature and indeed not that difficult. The problem and most work are the special cases. Most methods would take any straight line including the point in question and calculate the points of intersection with every side of the polygon (the intersection is with the line segment, not the endless line. By counting the numer of points to the "left" and to the "right" of the point in question it can be decided if the point is in or out. SOme special cases to consider are these

and I and II have to be treated differently.

So I guess its important that you tell us a bit more about what you exactly need, what you can tell about the polygon - obviously it had to be close in each case; can you guarantee it convex, not selfcrossing, points given in anticlockwise order, ...?

[AlanStevens]

Werner Exinger wrote:

Edit: I should add that I've assumed the points that define the area will always be entered in anticlockwise order around the boundary.

anticlockwise? So you also assume the polygon being convex? Or at least you assume the polygon is not "selfcrossing", e.g. like the infinity sign or the number eight.

No, I don't make these assumptions. Just that the points defining the boundary are entered anticlockwise. If the polygon crosses itself (like an infinity sign, say) the crossing point would need to be entered twice; once for the "lower" boundary, once for the "upper" one.

However, if it were a figure of 8, I'm not sure it would work! but then one could simply consider the region as two separate regions (perhaps!). I wonder of these extreme shapes are relevant for matti?

Stuart's method is neat, but gets point (1, 7) wrong, for example (this is on the vertical boundary).

Alan

[RichardJ]

Stuart's method is neat, but gets point (1, 7) wrong, for example (this is on the vertical boundary).

It could use some treaks to make it more robust. I doubt that really matters that much for this application though. Soil types do not have perfect categories anyway, so if a point is on a boundary between types then either type is equally valid.

[AlanStevens]

Richard Jackson wrote:

... Soil types do not have perfect categories anyway, so if a point is on a boundary between types then either type is equally valid.

Very true!

Alan

[RichardJ · Accepted solution]

Here's one that works for both points. This was written by Stuart, not by me. I just pulled it from my collection.

[Werner_E]

Thats a nice one - it counts the points of intersection above the point in question - if the number is odd the point is inside. But the algorithm doesn not take in account the special cases I mentioned in my post above. In cas one side of the polygon is vertical the routine throws an error and if the polygon is not convex and the point in question is exactly below an internal vertex of the polygon, the algorithm may yield a wrong result (special case I vs special cas II in the above post).

[RichardJ]

The vertical side might be an issue in this case. We'll see.

[Werner_E]

Yes, we sure need more information on what situation(s) we can depend on and whats actually needed. Stuarts routine sure can be made waterproof, and I guess the main problem would be the distinction between case I and II, not the vertical polygon side.

[MikeArmstrong]

Nice,

Well done to Stuart again.

[Werner_E]

Here is a testsheet to compare different algorithms with different data sets. I included Alan's second approach and Stuart's algorithm and hope I moved them over correctly. I also added one where I count how often a point is orbited by the polygon. This number should be zero for points outside the polygon. The algorithm seems to work pretty well also with non well behaved polygons, but still would need some work as some vertices are counted as in and some as out. The same goes for points lying on a polygon side. This is sure not an issue for the problem under discussion here, though.

[Werner_E]

Here is my second try. It seems that omitting the polygon sides which contain the point to be checked from building the angle sum and adding a tolerance to copy with roundoff error does the job. Now all points of the polygon (vertices and sides) are considered being inside.

EDIT: Only exception seems to be the point of intersection of the self crossing "infinity" (dataset 4).

[TikkaMasala]

Hi all,

It is nice to see that this problem has generated discussion.

The situation for which I need this inside/outside -test, was illustrated in the last section of the attachment in my original question (, but not very clearly, my apologizes for that...)

In principle, from a CPT (Cone penetration test) which is used for soil investigations, we get a large number of

sleeve resistance values fs and tip resistance values qt. Typical CPT test result is shown in attachment.

With these two values, the soil type can be defined using the charts presented in the second attached picture.

The main issue is to find, that in which area each fs/qt - qt -point hit.

My intention was that after this issue with one polygon is solved, I'll make a program that checks all the areas and defines in which area each point has hit. From those evaluations soil layers could be defined for all depths.

[Werner_E]

My intention was that after this issue with one polygon is solved, I'll make a program that checks all the areas and defines in which area each point has hit. From those evaluations soil layers could be defined for all depths.

That shouldn't be a big problem now. As you only have to deal with very few polygons, using any of the algorithms from this thread should do the job well enough. If you would have thousends of polygons, like determining which country/district/... a given point is on a map, other more time efficient algorithms might be necessary. I remember vaguely one which would slice the map in a way until all subspaces would be either trapezoids or triangles and was very efficient - don't recall any details, though.

[TikkaMasala]

I agree that this problem is now solved, thanks to all participants!