this post was submitted on 01 Dec 2023
17 points (100.0% liked)
NotAwfulTech
358 readers
1 users here now
a community for posting cool tech news you don’t want to sneer at
non-awfulness of tech is not required or else we wouldn’t have any posts
founded 1 year ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
Update on 18.
It's not cheating if it's something you learned and forgot from a university course
So, I have made my code a million times faster. My original algorithm counted every square of area individually, plus a bunch of other inefficient things.My new algorithm now uses some swanky computational geometry to calculate the enclosed area. It took a bit of scribbling on a paper pad to get this right. Some notes:
So, here's what I did. I looked at some old lecture notes I had on programming competition computation geometry implementation details. I copied and pasted some code that implemented a counter-clockwise check and one that calculated the area of a simple polygon. That's pretty much all I needed.
Now my code runs in a few milliseconds.
There is almost definitely a more elegant way to do what I did for this iteration but I'm happy to leave that to someone else to figure out (or copy paste from reddit or something).
18
The beauty is you don't need to keep track of the corners at all: ultimately the area contributed by the perimeter is ( 1/2 * perimeter ) + 1. The short justification is that is if was just ( 1/2 * perimeter ), for every inside corners you overcount by 1/4 and for every outside corner you undercount. And there is exactly 4 more outside corners that inside ones, always. You can justify that by having an arrow follow the eddges, utlmately the arrow must make 1 full turn, each outside corner adds 1/4 turn. each inside corner removes 1/4 turn.I knew there was a better way! Thanks!
perhaps
A more elegant proof might show that starting with a rectangle, you have 4 corners contributing 1/4. You can push out parts of the edges of the rectangle to generate more corners, but they will always be in pairs of opposite types.