Characterizing the key length and energy scales of intermolecular interactions, Lennard-Jones parameters, i.e., collision diameter and well depth, are prerequisites for predicting transport properties and rate constants of chemical species in dilute gases. Due to anisotropy in molecular structures, Lennard-Jones parameters of many polyatomic molecules are only empirically estimated or even undetermined. This study focuses on determining the effective Lennard-Jones parameters between a polyatomic molecule and a bath gas molecule from interatomic interactions. An iterative search algorithm is developed to find orientation-dependent collision diameters and well depths on intermolecular potential energy surfaces. An orientation-averaging rule based on characteristic variables is proposed to derive the effective parameters. Cross-interaction parameters for twelve hydrocarbons with varying molecular shapes, including long-chain and planar ones, interacting with four bath gases He, Ar, N-2, and O-2 are predicted and reported. Three-dimensional parametric surfaces are constructed to quantitatively depict molecular anisotropy. Algorithmic complexity analysis and numerical experiments demonstrate that the iterative search algorithm is robust and efficient. By using the latest experimental diffusion data, it is found that the proposed orientation-averaging rule improves the prediction of cross-interaction Lennard-Jones parameters for polyatomic molecules, including for long-chain molecules that challenge the consistency of previous methods. By introducing characteristic variables, the present study shows a new route to determining effective Lennard-Jones parameters for polyatomic molecules.