Tuesday, October 30, 2007

Crossing Segment Intersections

I've been away from Project Euler for several months, and decided to try some of the new problems for fun. Not being shy about a challenge I just chose the most recent one. Couple hours and implementations later, and the solution remains out of reach.

It didn't even seem that difficult, really. My first two tries were completely from my gut. One was a brute force stab with sorting in one dimension: usually these attempts just help me get a feel for the problem. With 5000 lines that means over 12 million intersection test - sorting and early exit dropped it down to about 4 million. Certainly within range of brute forcing on modern processors.

The intersection test itself seemed to be problem. So, I used a little topology to devise a test based strictly on triangle area, given the connected graph of the four points. Got a different result, but it was close enough to the last one to give a sense of accomplishment. (It's really fast and merits further research.)

Where could the problem be? I searched the web for algorithms - seems line sweeping is all the rage. Quickly, I plugged a couple different intersection tests into my first attempt. Two more different answers!

Have to put the problem aside for now...

2 comments:

Rasser said...

I did the first half of the problem after seeing you post!

Introduction to Algorithms had a suitable intersection checker algorithm after using some homebrewed cutting down heuristic.

Now the only problem is finding the number of unique intersections.

I don't like getting floats!

Rickey Bowers Jr. said...

I've been calculating all intersections without regard for multiple lines crossing at the same point! So, if three lines intersect at the same point, I am calculating three crossings: (AB,AC,BC). With so many lines this must be happening quite frequently.