Calculating the true astronomical North/South is very simple - find the longest way and cast a shadow.
Are there sources on how precise those directions in the Temples were? Are there special Jewish calculations? Is there a tradition of pointing to a certain landmark (a point on Mt. Olives) or aligning with the stars?
(for comparison, "The [Egyptian pyramids] tombs are aligned north-south with an accuracy of up to 0.05 degrees.")