An embedded-friendly method to determine whether a point lies within an area

Minimising the complexity required to check whether a given point lies within a pre-defined area is key for systems with limited computation. Provided we know the coordinates of the point and the coordinates of the vertices defining the area, we can express the problem geometrically as a point-in-polygon—of which there are a handful of well-established solutions.

We can mathematically simplify the problem, given the following:

• The area shape is a convex polygon

• The algorithm utilises the area vertices in a clockwise direction

The assumptions above largely constitute the limitations associated with the proposed methodology. Practically, the only limitation of consequence is that the zone must be convex. This constraint can be largely mitigated by defining several areas to approximate the desired complex shape. Let’s start by geometrically labelling our problem:

We have our zone vertices defined in a clockwise direction as Z0 … Z3 and our point P. With these definitions in place, we can evaluate the cross product between pairs of vertices and the point:

The result provides the following context for our algorithm:

The figure below illustrates the cross-product multiplication resulting in a positive value when the point is outside the defined zone:

Likewise, a resulting negative value will be produced from anticlockwise vectors when the point lies within the area:

From here, we simply iterate through each of our vertices in a clockwise direction. If none of the resulting cross-product calculations are positive, then our point can be considered to lie within the area. To help understand the proposed methodology programmatically, a Python script can be downloaded below: