However, I did this before and it is a city owned unattended machine.
Someone could have placed a skimmer on the machine that captures your credit card information. The fact that the machine is unattended makes this a definite possibility. This could have been done since the last time you used it without the city or any users catching on. This could also occur at a gas station, which you mentioned you had visited in the last few weeks.
If you used your card online, check the news or the company's website to make sure the site wasn't compromised. Also, talk to your bank about when the charges were made. The theft could have occurred shortly before that. However, it's also conceivable that your information was stolen a while ago and only recently used.
Have you used your credit card online from a public computer/wi-fi network or over an unencrypted connection? If not, have you logged into other accounts that use the same account information or could possibly expose your credit card details if those accounts were comprised? Some people store financial information in their email, so this is another avenue for your information to be compromised.
If you receive financial statements or documents with other personal information on them in paper form, do you shred them thoroughly or burn them before disposing of them? Regardless of how "swanky" your community might be, there are people who will look through trash to find such information. Arguably, a more upscale community would be more vulnerable to this because an identity thief knows there is more information available there.
Otherwise, it can be very difficult to pinpoint exactly when/where your information was compromised. I know it's not the answer you want to hear, but unfortunately, finding the exact time/location of the theft may be impossible.