Camera calibration without grid Ususally a grid pattern (circles or squares) is used for camera calibration. Features (circles or corners) are detected in a function (e.g. findCirclesGrid in OpenCV) and passed to the a camera calibration  function (e.g. calibrateCamera in OpenCV) together with corresponding object points (object coordinates).


Is it possible to calibrate a camera with circles which are "randomly" spread on a plane (object coordinates known)?
If yes, how does it affect the feature detection, i.e. findCirclesGrid? Is it less accurate?
If yes, how does it affect the calibrateCamera function? Can all parameters such as distortion for example still be computed?
Yes.  Any known pattern can be used for camera calibration, if you know the ground-truth shape.  You just need to have a number of points where you know (a) their location in the image and (b) their location in the physical world.  The procedure is simplest with a grid, so if you're choosing a pattern, might as well stick to that standard (why not?).

Questions about implementation and OpenCV are off-topic here, though.