Page 1 of 3
Problem 165
Posted: Sun Jan 27, 2008 11:30 pm
by 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?
Re: Clarification on 165
Posted: Mon Jan 28, 2008 12:47 am
by 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).
clarification on problem 165
Posted: Mon May 26, 2008 3:17 pm
by 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)?
Re: clarification on problem 165
Posted: Mon May 26, 2008 4:37 pm
by jaap
Yes, if there are three or more lines that intersect in a single point, that intersection point should still be counted only once.
Re: Clarification on 165
Posted: Tue Nov 11, 2008 1:25 pm
by 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?
Re: Clarification on 165
Posted: Tue Nov 11, 2008 1:44 pm
by quilan
Try it with arbitrary precision and see what your results are.
Re: Clarification on 165
Posted: Tue Nov 11, 2008 1:55 pm
by 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.
Re: Clarification on 165
Posted: Tue Nov 11, 2008 2:11 pm
by hk
quilan wrote:Try it with arbitrary precision and see what your results are.
Or better still, try to do all in integers, using fractions.
Re: Clarification on 165
Posted: Thu Dec 11, 2008 12:09 am
by DaveNo1
hk wrote: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?
Re: Clarification on 165
Posted: Thu Dec 11, 2008 9:54 am
by stijn263
stijn263 wrote: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?
Re: Clarification on 165
Posted: Thu Dec 11, 2008 11:29 am
by 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.
Re: Clarification on 165
Posted: Thu Dec 11, 2008 11:56 am
by stijn263
karlo wrote:Because it's very easy to do a mistake while counting those distinct intersection points, (..)
Yup, that's why it's a difficult problem
Re: Clarification on 165
Posted: Thu Dec 11, 2008 12:43 pm
by hk
karlo wrote: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.
Re: Clarification on 165
Posted: Thu Dec 11, 2008 2:52 pm
by karlo
stijn263 wrote: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
Re: Clarification on 165
Posted: Tue Dec 16, 2008 6:42 am
by DNS
quilan wrote: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?
Re: Clarification on 165
Posted: Tue Dec 16, 2008 7:58 am
by jaap
DNS wrote: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:
Problem 165 wrote:How many distinct true intersection points are found among the 5000 line segments?
Re: Problem 165
Posted: Tue Aug 17, 2010 10:44 pm
by 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!
Re: Problem 165
Posted: Wed Aug 18, 2010 1:55 am
by rayfil
Smaug wrote:I get 1130, consistently, whether I use ...!
There must be something VERY wrong with your algo.
Re: Problem 165
Posted: Sat Dec 18, 2010 2:19 pm
by 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
Re: Problem 165
Posted: Sat Dec 18, 2010 9:28 pm
by 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.