0

Suppose you have have a rectangle, bottom-left point 0,0 and upper-right point is 100,100. Now two line intersects the rectangle. I have to find out the coordinate of the intersection point. I have done that. Now the problem is I can't tell whether it is inside the rectangle or not. I used double comparison. But I think it is giving me wrong answer. Suppose the intersection point is ( x , y ). I used this checking for comparison : if( x >= 0.0 && x <= 100.0 && y >= 0.0 && y <= 100.0 ). What should I do?

//this function generates line line genline( int x1 , int y1 , int x2 , int y2 ){ line l ; l.A = y2 - y1 ; l.B = x1 - x2 ; l.C = l.A * x1 + l.B * y1 ; return l ; } //this function checks intersection bool intersect( line m ,line n ) { int det = m.A * n.B - m.B * n.A ; if( det == 0 ){ return false ; } else { double x = ( n.B * m.C - m.B * n.C ) / ( det * 1.0 ) ; double y = ( m.A * n.C - n.A * m.C ) / ( det * 1.0 ) ; if( x >= 0.0 && x <= L && y >= 0.0 && y <= W ) { return true ; } else{ return false ; } } }

EDIT: Both the line are stretched to infinity.

Improve this question
14
  • Are you sure your intersection point calculation is correct? Can we see some more code? Commented Sep 21, 2011 at 3:08
  • Your rectangle test is fine. Please describe why you think it fails. Please give an example x,y value for which your test fails and you feel it should not. Commented Sep 21, 2011 at 3:09
  • "But I think it is giving me wrong answer" is not good enough. You need to describe exactly how it fails in your eyes. It's no good making us guess. Commented Sep 21, 2011 at 3:15
  • Please give an example x,y value for which your test fails and you feel it should not. Commented Sep 21, 2011 at 3:19
  • 1
    @caso One of the main things about algorithm competitions is that you're meant to be able to think up your own test cases. Commented Sep 21, 2011 at 3:24

3 Answers 3

Reset to default
0

Your math looks like it's right. By the way, If a line intersects something, it is always inside that something.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

This should be a comment, not an answer.
what happens if the y of intersection point is 99.999999... will the compiler round it up?
@caso It depends on the floating point math, the compiler wont necessarily round it up, it will try to store it as accurately as it can in a float or a double. Doubles give more precision than floats.
@caso You are being paranoid. Are you aware that floating point arithmetic has finite precision?
@quasiverse OP - "But I think it is giving me wrong answer" Me - "Your math looks like it's right."
|
0

Checking to see if a point is inside a rectangle is relatively easy. However, the challenge is to find the intersection between two line segments. There are a large number of corner cases to that problem and limited accuracy of floating point numbers play a huge roll here.

Your algorithm seems to be overly simplistic. For a deeper discussion about this topic you can look at this and this. This two parts article investigates the problem of finding the intersection of two lines using floating point numbers. Notice that they are about MATLAB not C++ though that does not change the problem and the algorithms are easily translatable to any language.

Depending on application, even with clever tricks floating point representation might not simply cut it for some geometry problems. CGAL is a C++ library dedicated to computational geometry that deals with these kind problems. When necessary it uses arbitrary precision arithmetic to handle degenerate cases.

Improve this answer

13 Comments

Just because it seems simplistic doesn't mean it's incorrect: community.topcoder.com/…
@quasiverse I included two links to a blog that discusses this issue in details. A quick look shows that the OP's algorithm does not consider a lot of cases. It is basically translation of the maths to code without considering numerical issues of floating-point representation. So yes, I do see a problem with that. The link you provide, unfortunately, does not deal the problem cases and is incomplete.
Looking at the links, half of it seems to be pictures and quite a bit of the code seems to be plot(stuff) but that's besides the point. The point is that the code is correct and more generally that things don't have to be complicated to be correct.
@quasiverse No the code is not correct. For example it fails in the case of a horizontal line segment intersecting a vertical line segment. The "det" will be always zero and it will report no intersection. This is a simple case and is not even a floating-point related problems.
I believe you are incorrect. Could you provide an example of a vertical and horizontal line for which it incorrectly does not identify an intersection?
|
0

When you're dealing with floating point (or double), testing for equality is naïve and will fail in edge cases. Every comparison you make should be in reference to "epsilon", an extremely small quantity that doesn't matter. If two numbers are within epsilon for each other, then they are considered equal.

For example, instead of "if(a == b)", you need:

bool isEqual(double a, double b, double epsilon = 1.E-10) { return fabs(a - b) <= epsilon; }

Pick a suitable value for epsilon depending on your problem domain.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.