Combine those ideas and you're in pretty good shape:
- Diode from "+12V" (can go from 7 to 14 volts extremes) to a large capacitor (maybe 10,000+ uF at 25 volts)
- From the capacitor to a voltage regulator similar to what you showed, with an output of 6 or 8 volts, to the Arduino Vin
- The Arduino regulator takes it from there to 5V
Google "Car Computer" and "Power Supply" and you'll get LOTS of hits... Those guys are doing it for a long time now.