Determining online system user eligibility for receiving content using a polygon representing a physical location associated with the content

1. A method comprising:

determining a polygon having a plurality of edges bounding a representation of a physical location on a map, the physical location associated with a content item maintained by an online system;

for each edge of the plurality of edges,

determining edge data describing a position of the edge on the map, the edge data comprising a plurality of edge coordinates representing a plurality of points of the edge on the map,

generating an index comprising a set of edge coordinates representing a position of each endpoint of the edge along a specified axis of the map, and

storing the edge data and index into an edge data store with an identifier associated with the polygon;

receiving, from a client device associated with a user of the online system, location information describing a geographic location of the client device;

determining a location point representing a position of the geographic location on the specified axis of the map based on the location information;

determining which of the plurality of edges of the polygon to retrieve, where each edge is determined to be retrieved when the edge spans the location point along the specified axis of the map;

retrieving, from the edge data store, edge data associated with each of the edges of the polygon that were determined to be retrieved;

determining whether the client device is at the physical location based at least in part on the retrieved edge data; and

responsive to determining the client device is at the physical location, providing the content item to the client device for presentation to the user.

2. The method of claim 1 , wherein querying the edge data store using a set of indexed edge coordinates comprises identifying an edge associated with a plurality of edge coordinates representing a position of each endpoint of the edge on opposite sides of the location point along the specified axis of the map.

3. The method of claim 1 , wherein determining whether the client device is at the physical location based at least in part on the retrieved edge data comprises:

comparing a position of the location point on an additional axis of the map perpendicular to the specified axis and a position of each edge of the retrieved edge data on the additional axis of the map; and

determining the client device is at the physical location if an odd number of edges of the retrieved edge data includes a point on one side of the location point on the additional axis of the map perpendicular to the specified axis.

4. The method of claim 1 , further comprising:

computing a number of edges of the retrieved edge data intersected by a ray from a position of the geographic location on the map along an axis of the map perpendicular to the specified axis; and

determining the client device is at the physical location if an odd number of edges of the retrieved edge data are intersected by the ray.

5. The method of claim 4 , further comprising determining the client device is not at the physical location if an even number of edges of the retrieved edge data are intersected by the ray or no edge of the retrieved edge data is intersected by the ray.

6. The method of claim 1 , further comprising:

responsive to determining the client device is not at the physical location, determining whether the client device is within at least a threshold distance of the physical location based at least in part on a proximity of a representation of the geographic location on the map to an edge of the plurality of edges; and

responsive to determining the client device is within at least the threshold distance of the physical location, providing the content item to the client device for presentation to the user.

7. The method of claim 6 , wherein determining whether the client device is within at least the threshold distance of the physical location comprises:

determining a location boundary surrounding the representation of the geographic location on the map, the location boundary comprising an area on the map corresponding to a geographic area having a specified radius around the geographic location;

determining whether the location boundary intersects an edge boundary on the map; and

responsive to determining the location boundary intersects the edge boundary, determining the client device is within at least the threshold distance of the physical location.

8. The method of claim 1 , wherein the physical location is selected from a group consisting of: a building, a street address, a set of geographic coordinates, a neighborhood, a landmark, and any combination thereof.

9. A method comprising:

receiving, from a client device associated with a user of an online system, location information describing a geographic location of the client device;

determining a location point representing a position of the geographic location on a specified axis of the map based on the location information;

determining which of a plurality of edges of one or more polygons to retrieve, the one or more polygons representing one or more physical locations on the map, where each edge is determined to be retrieved when the edge spans the location point along the specified axis of the map;

retrieving stored edge data associated with each of the edges of the one or more polygons that were determined to be retrieved;

computing a value associated with the retrieved edge data based at least in part on a number of edges of the retrieved edge data associated with a polygon of the one or more polygons; and

determining whether the client device is at a physical location represented by the polygon based at least in part on the value associated with the retrieved edge data.

10. The method of claim 9 , further comprising responsive to determining the client device is at the physical location, providing a content item associated with the physical location to the client device for presentation to the user.

11. The method of claim 9 , further comprising determining the client device is at the physical location if a ray from a position of the geographic location on the map along an axis perpendicular to the specified axis of the map intersects an odd number of edges of the retrieved edge data of the polygon on the map.

12. The method of claim 9 , further comprising determining the client device is not at the physical location if a ray from a position of the geographic location on the map along an axis perpendicular to the specified axis of the map intersects an even number of edges of the retrieved edge data of the polygon on the map.

13. The method of claim 9 , further comprising determining the client device is not at the physical location if a ray from a position of the geographic location on the map along an axis perpendicular to the specified axis of the map does not intersect an edge of the retrieved edge data of the polygon on the map.

14. The method of claim 9 , further comprising:

responsive to determining the client device is not at the physical location, determining whether the client device is within at least a threshold distance of the physical location based at least in part on a proximity of a representation of the geographic location on the map to an edge of retrieved edge data of the polygon; and

responsive to determining the client device is within at least the threshold distance of the physical location, providing a content item associated with the physical location to the client device for presentation to the user.

15. The method of claim 14 , wherein determining whether the client device is within at least the threshold distance of the physical location comprises:

determining a location boundary surrounding a representation of the geographic location on the map, the location boundary comprising an area on the map corresponding to a geographic area having a specified radius around the geographic location;

determining whether the location boundary intersects an edge boundary of an edge of retrieved edge data of the polygon on the map; and

responsive to determining the location boundary intersects the edge boundary, determining the client device is within at least the threshold distance of the physical location.

16. A computer program product comprising a computer readable storage medium having instructions encoded thereon that, when executed by a processor, cause the processor to;

determine a polygon having a plurality of edges bounding a representation of a physical location on a map, the physical location associated with a content item maintained by an online system;

for each edge of the plurality of edges,

determine edge data describing a position of the edge on the map, the edge data comprising a plurality of edge coordinates representing a plurality of points of the edge on the map,

generate an index comprising a set of edge coordinates representing a position of each endpoint of the edge along a specified axis of the map, and

store the edge data and index into an edge data store with an identifier associated with the polygon;

receive, from a client device associated with a user of the online system, location information describing a geographic location of the client device;

determine a location point representing a position of the geographic location on the specified axis of the map based on the location information;

determining which of the plurality of edges of the polygon to retrieve, where each edge is determined to be retrieved when the edge spans the location point along the specified axis of the map;

retrieve, from the edge data store, edge data associated with each of the edges of the polygon that were determined to be retrieved;

determine whether the client device is at the physical location based at least in part on the retrieved edge data; and

responsive to determining the client device is at the physical location, provide the content item to the client device for presentation to the user.

17. The computer program product of claim 16 , wherein querying the edge data store using a set of indexed edge coordinates comprises identifying an edge associated with a plurality of edge coordinates representing a position of each endpoint of the edge on opposite sides of the location point along the specified axis of the map.

18. The computer program product of claim 16 , wherein determine whether the client device is at the physical location based at least in part on the retrieved edge data comprises:

compare a position of the location point on an additional axis of the map perpendicular to the specified axis and a position of each edge of the retrieved edge data on the additional axis of the map; and

determine the client device is at the physical location if an odd number of edges of the retrieved edge data includes a point on one side of the location point on the additional axis of the map perpendicular to the specified axis.

19. The computer program product of claim 16 , wherein the computer readable storage medium further has instructions encoded thereon that, when executed by the processor, cause the processor to:

compute a number of edges of the retrieved edge data intersected by a ray from a position of the geographic location on the map along an axis of the map perpendicular to the specified axis; and

determine the client device is at the physical location if an odd number of edges of the retrieved edge data are intersected by the ray.

20. The computer program product of claim 19 , wherein the computer readable storage medium further has instructions encoded thereon that, when executed by the processor, cause the processor to determine the client device is not at the physical location if an even number of edges of the retrieved edge data are intersected by the ray or no edge of the retrieved edge data is intersected by the ray.

21. The computer program product of claim 16 , wherein the computer readable storage medium further has instructions encoded thereon that, when executed by the processor, cause the processor to:

responsive to determining the client device is not at the physical location, determine whether the client device is within at least a threshold distance of the physical location based at least in part on a proximity of a representation of the geographic location on the map to an edge of the plurality of edges; and

responsive to determining the client device is within at least the threshold distance of the physical location, provide the content item to the client device for presentation to the user.

22. The computer program product of claim 21 , wherein determine whether the client device is within at least the threshold distance of the physical location comprises:

determine a location boundary surrounding the representation of the geographic location on the map, the location boundary comprising an area on the map corresponding to a geographic area having a specified radius around the geographic location;

determine whether the location boundary intersects an edge boundary on the map; and

responsive to determining the location boundary intersects the edge boundary, determine the client device is within at least the threshold distance of the physical location.

23. The computer program product of claim 16 , wherein the physical location is selected from a group consisting of: a building, a street address, a set of geographic coordinates, a neighborhood, a landmark, and any combination thereof.