Intel® Software Network

My program has found 1622 intersections in 21 sec.
However I am not 100% sure in correctness of my program now. Since it's difficult to manually compare output of one program with output of another program, I propose following method for quick verification/comparison of results.
The idea is to compute some "hash" of results. Hash must be stable to following reorderings:
A B
C D
must yield the same hash as:
D C
B A

But not stable to following reorderings:
A B
C D
must not yield the same hash as:
A C
B D

Here is algorithm I currently use:
char hash [4] = {};
for (size_t i = 0; i != results.size(); i += 1)
{
line_t const* line1 = results[i].line1;
line_t const* line2 = results[i].line2;
for (int t = 0; t != 4; t += 1)
hash[t] ^= (line1->name[t] + line2->name[t]);
}
}
printf("count=%u (%u)\n", results.size(), *(unsigned*)sample);

My output is:
count=1622 (1711155)

Post your time and result (number of intersections and hash).

Suggestions on how to improve input data generation process and hash calculation are welcome.

Simple optimization reduced time to 6247ms.

Drop in single pragma omp. Time is 1731ms.

Another approach is to run the output through sort and then compare the sorted outputs.

hi Dmitriy Vyukov

My program has found 5352 intersections in 6 sec.

My brute force implementation says there are 4788 intersections...

Well, this will definitely produce better results, however one will have to attach own results and download others results, then pass them through some utility, and somebody has to develop that utility first...
What I would prefer is something much more "lightweight". Probably good variant will be to sort results and then calculate SHA1.

Can you post your results please? I want to verify visually whether I've missed any intersections. I'll let you know what I find out. Here's mine (linux)...

Thanks.

Cool! I like this :)

For knapsack it was easier, if you have higher value and your solution is feasible then you are on the safe side. For line segments it's unclear which solution is "more right".
My first attempt also yield some 4 thousands intersections, however then I re-implement it more carefully and it yield only 1622. It's not to say that my answer is correct, I am totally unsure that it is correct.

I would be nice if somebody will construct input file with several tens of different corner cases and manually calculate correct answer... AMD Threadfest was much contestant-friendlier in this aspect - they initially provide a number of input datasets, pre-calculated correct results, simple reference implementation of the program and precisely describe input data generation process, so that contestants was able to concentrate on the problem itself...

that won't work if one implementation prints
AAAA BBBB

and another prints
BBBB AAAA

Maybe you can use this...

I found in your output following intersection:
k?#! ;:)!

The coordinates are:
k?#!      3 0 37          -10 -16 20
;:)!      3 181 10        -9 184 -6

They do not seem to intersect at all. Look at their "y" (second) coordinates: 0 - -16 and 181 - 184. How they can intersect?

Btw, I've found error in my code, now my result is: count=1858 (1699850).
I think it's in the common interests to agree on result for at least one problem :)

Attached my current output with 1858 intersections.

I believe these are the correct values:
k?#!: (3, 181, 10) - (-11, 184, -10)
;:)!: (3, 181, 10) - (-9, 184, -6)

The points intersect at (3, 181, 10)

Damn! Sorry for that. I used case-insensitive search.
Then I have to verify why I did not include "k?#! ;:)!" into results.
I think for the next input file I will use only alphanum chars ('A-Z', '0-9'), it will be enough to generate up to 1.5M segments.

All of your solutions were also found by my program. There are additional intersections that you've missed:
For example, here's one that I've verified:
4&$! DI&!

4&$!: (34, 115, 36) - (48, 125, 50)
DI&!: (68, 113, 32) - (48, 125, 50)

Looks to me like you've missed the ones that have common end-points...

Thank you!
I will verify why my program misses it, as well as "k?#! ;:)!".
Hope will get at least 2 people with equal results.

Cool! I get: count=4788 (1047121)

Excellent! :)

It was float tolerance error. I made tolerance in the wrong direction, so all corner cases (segment end is intersection point) were stripped.

=C)! 199 164 110 199 174 106
^9)! 199 156 110 199 166 94

This will lead to the straight-line bugs me。
My answer now is 4788 too。 thanks。

Here too: 4788 hits :D

But with my serial brute force algorithm I get 351.508s...... thats depressing! :P

Allright! I removed a push_back operation to store the intersection and it goes down to ~6secs.