Aspects of the disclosure relate to controlling a vehicle having an autonomous driving mode or an autonomous vehicle. For instance, a polygon representative of the shape and location of a first object may be received. A polyline contour representation of a portion of a polygon representative of the shape and location of a second object may be received. The polyline contour representation may be in half-plane coordinates and including a plurality of vertices and line segments. Coordinates of the polygon representative of the first object may be converted to the half-plane coordinate system. A collision location between the polyline contour representation and the polygon representative of the first object may be determined using the converted coordinates. The autonomous vehicle may be controlled in the autonomous driving mode to avoid a collision based on the collision location.