Aspects and implementations of the present disclosure relate to modeling of positional uncertainty of moving objects using precomputed polygons, for example, for the purposes of computing autonomous vehicle (AV) trajectories. An example method includes: receiving, by a data processing system of an AV, data descriptive of an agent state of an object; generating a polygon representative of the agent state; identifying extreme vertices of the polygon along a longitudinal axis parallel to a heading direction of the object or along a lateral axis orthogonal to the heading direction; and applying, based on the extreme vertices, at least one expansion transformation to the polygon along the longitudinal axis or the lateral axis to generate a precomputed polygon.