How to find if a point is inside of a polygon using Racket

Question

I am working an a project that, given a specific latitude and longitude coordinate, outputs the neighborhood that the point resides in. I have the latitude and longitude coordinates that make up the boundaries of several neighborhoods within a city. I have to read the neighborhood data from a file, and also read the test-points from a file. I am using the Racket programming language.

So far I have been able to read the files and create a list of points for each neighborhood, and now I am stuck. I wanted to create a polygon for each neighborhood, and then have a method that checks to see if a point lies inside that polygon. However, I cannot figure out how to do that using Racket.

Can anyone help me find out how to solve if a point is inside that polygon, or perhaps a better way to go about solving the problem?

Unlive

Is it a convex or a concave polygon? Or is it only a simple rectangle? – Lindie

They are all concave polygons, sorry I didn't even think to mention that. – Unlive

Answer 1

I won't post any code for now because I don't want to solve the homework/assignment. However, I'll post some hints.

Look at the following picture:

How can we know that C is between the edges OA and OB and D is outside? It simple: we compare some angles: if the angle between OC and OA is smaller than the angle between OB and OA then C is clearly closer to OA than OB is.

Now, how do we get the angle knowing only some vectors? We can use the cosine which is monotonous: it decreases with the increasing argument. Thus, the cosine of the angle between OC and OA is greater than the cosine of the angle between OB and OA which is in turn greater that the cosine of the angle between OD and OA.

Next step is to figure out how to compute the cosine. The vector dot product helps: it's value is cosine of angle times greater than the product of operand's lengths. That is:

cos(OC; OA) = dotproduct(OC; OA) / (length(OA) * length(OC))

The dotproduct in 2D is simple:

dotproduct(OC; OA) = (C.x - O.x) * (A.x - O.x) + (C.x - O.x) * (A.x - O.x)

Combining all of the above you should have a simple test to check whether your point is in the same situation as C or as D: closer to one edge than the previous edge or not.

Now, you'll have to repeat this for every edge of the polygon and you're done. You can do this with a fold if the test is a predicate.

Note: this only works if the polygon is convex. For a concave polygon you'll need to add more tests.

Second note: In the figure, what will happen if D or C or both are below the OA line? Think about this and check if it means some more changes to the above fold method.

Last note: In a few weeks I'll post a complete code for that, assuming the assignment is over. Also, at that time I'll answer the question in the above note.

Lindie

This is excellent thank you so much. I will take a closer look at this following the holiday but I understand the tests and have a plan. For reference, here is an image of the nieghborhood map to show you the types of shapes I will be working with. imgur.com/eZRa1fD – Unlive

You'll need to split the poligons into convex ones, in order for this to work. You can use a triangle mesh. – Lindie

Answer 2

You need to start by collecting the segments of your polygon. For the point P, you need determine if the horizontal ray starting from the point P intersects the side (segment). If you count how many segments the point's horizontal ray intersects, then an odd number will be inside, and an even number will be outside.

  (define (point-in-polygon? point polygon)
    (odd? 
     (for/fold ([c 0]) ([seg polygon])
       (+ c (if (ray-cross-seg? point seg) 1 0))))))

I have a complete solution in https://github.com/StevenACoffman/lat-long-kata-racket

An alternative Ray Casting Algorithm in Racket is https://rosettacode.org/wiki/Ray-casting_algorithm#Racket as well as in 35 other programming languages.

A more detailed walkthrough is available: https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/

Marindamarinduque