Problem 165

[quilan]

If an endpoint lies on an intersection of two other lines, does that mean that the intersection is invalid?

Example w/ three lines:
(-1,0)-(1,0)
(0,-1)-(0,1)
(0,0)-(1,1)

Would (0,0) not count as a distinct intersection point?

[daniel.is.fischer]

The first two lines properly intersect at (0,0), so it counts. If the first segment wasn't there, (0,0) would not count (unless other segments would properly intersect there).

[viv_ban]

In problem 165 it has been asked "to identify distinct true intersection points". Does that mean concurrency of lines has to be taken into consideration (if any)?

[jaap]

Yes, if there are three or more lines that intersect in a single point, that intersection point should still be counted only once.

[DNS]

Using different precision to check is a point belong to the segment I obtain different results (all are incorrect).
Only == (long double) ...1680
abs(.-.)< 1E-15 ...1560
abs(.-.)< 1E-9 ...1557
abs(.-.)< 5E-9 ...1544
abs(.-.)< 1E-8 ...1518
abs(.-.)< 5E-8 ...1398
What precision should I use? Or my way is wrong?

[quilan]

Try it with arbitrary precision and see what your results are.

[DNS]

It seems funny, but in the example (3 segment) "not-true" intersection point (22,40) after my brute-force calculation (line-line intersection) deflects from (22,40) by ~1E-15. When I use (x_calc < x_seg) condition, it passed, but really should be x_calc==s_seg. So, I confused.

[hk]

Try it with arbitrary precision and see what your results are.

Or better still, try to do all in integers, using fractions.

[DaveNo1]

Or better still, try to do all in integers, using fractions.

I used fractions, and every manual check says that it produces valid results, but something still appears to be wrong.

With only 100 line Segments I get 1112 Intersections. Is that a correct value?

[stijn263]

Problem 165 can go wrong on many points. Just to name a few:
-> Are you checking wether more than 2 lines intersect at a point ?
-> What about linesegments that are exactly the same (perhaps partly)?
-> Do you store intersection points using floats or integer fractions?

[karlo]

Because it's very easy to do a mistake while counting those distinct intersection points, I do believe that an intermediate result (the first 100 segments for example) would be very useful.
EDIT:
@DaveNo1: I get 1112 for 100 segments too, but I didn't solve the problem, so my result may be wrong:( Anyway I see now that hk is right: the answer for 100 wouldn't help too much.

[stijn263]

Because it's very easy to do a mistake while counting those distinct intersection points, (..)

Yup, that's why it's a difficult problem

[hk]

Because it's very easy to do a mistake while counting those distinct intersection points, I do believe that an intermediate result (the first 100 segments for example) would be very useful.

That would not guarantee that some possible issues would have been covered and in that sense is useless.

[karlo]

Problem 165 can go wrong on many points. Just to name a few:
-> What about linesegments that are exactly the same (perhaps partly)?

Can't see why this makes a difference. Maybe I don't understand what you mean exactly. Even if two segments are the same, that doesn't affect the number of distinct points. Still getting a wrong answer

[DNS]

If an endpoint lies on an intersection of two other lines, does that mean that the intersection is invalid?

Example w/ three lines:
(-1,0)-(1,0)
(0,-1)-(0,1)
(0,0)-(1,1)

Would (0,0) not count as a distinct intersection point?

If we change the last segment onto (-1,-1)-(1,1), such that in (0,0) point intersect 3 segments. How many times should I add the point?

I see no confirmation for 1112 points for 100 seg-s. I found 1119 points of true itersection and noone of non-true. Am I wrong?

[jaap]

If we change the last segment onto (-1,-1)-(1,1), such that in (0,0) point intersect 3 segments. How many times should I add the point?

Once:

How many distinct true intersection points are found among the 5000 line segments?

[Smaug]

I get 1130, consistently, whether I use extended precision or fractions represented as numerator/denominator throughout. I don't even do any division on the fractions!

[rayfil]

I get 1130, consistently, whether I use ...!

There must be something VERY wrong with your algo.

[Lord_Farin]

Is there anyone willing to take a look at my code, since I have reworked the algorithm today, improving my Fraction class where necessary, but without obtaining the green check. Quite simply, I'm stuck. Thanks in advance

[sivakd]

Does your fraction class represent the value in float or use integers for n and d (n/d)? For me the later form worked. This is one of those problems where I just scrapped the whole program and started fresh to avoid so many bugs.