CODEWITHSUNDEEP
algorithm
Quantaliinuxite
Quantaliinuxite

Reputation: 3223

Algorithm to find which polygon a point belongs to given the coordinate of a polygon

The real life problem is something like this: Given the borders of different countries as a series of coordinate forming polygons, and given a point A with a longitude and a latitude, determine which country contains the point A.

A rough drawing of the problem looks something like this: Schematic drawing

Is there an algorithm that would allow me to determine which country the given point belongs to? We can assume that the country border are given as triples (longitude,latitude,ISO2).

Upvotes: 3

Views: 457

Answers (2)

Codor
Codor

Reputation: 17605

As described here, various methods can be used, which depend on the representation of the polygon. One possibility is to send a ray in a fixed direction from the point for which to decide containment and count the number of intersection with the polygon; if the number is even, the point is outside of the polygon and inside the polygon otherwise.

Upvotes: 1

Sorin
Sorin

Reputation: 11968

A simple test would be to take a line starting from the query point going to infinity in some direction (say positive x). Then intersect it with all the line segments forming your polygon.

If you have an odd number of intersections then your point is inside the polygon. If you have an even number of intersections, then the point is outside.

This works for any non-self-intersecting polygon.

Upvotes: 0

Related Questions