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?

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.