Jump to content
  • Advertisement
Sign in to follow this  

[java] How to detect if a line is intersecting a rectangle?

This topic is 4721 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a problem with a simple thing I didn't believe would cause me so much trouble. I have a JPanel on which I can draw lines. Each line is defined by an object which holds the (x,y) coordinates. So now I have an "eraser" tool, and I want to erase those lines. The whole thing should work like this: I set eraseMode = true, and the mouse pointer turns into a 10x10 square. When the mouse is dragged on the panel, it should delete every line that intersects with the mouse's square. So I thought I would use the simplest (but not most optimal) solution, and have two for loops, i and j. i goes from 0 to 9, and j from 0 to 9, and they make a combination of 100 different points from which at least one needs to be on the line to get the line deleted. The line is defined by (m1.x,m1.y) and (m2.x,m2.y), and my formula for detecting if the point (i,j) is on the line is: int lambda = i*(m2.y - m1.y) - j*(m2.x - m1.x) + m1.y*m2.x - m1.x*m2.y; if (lambda == 0) deleteLine(m1,m2); The problem is that the line rarely gets deleted. I checked with various values getting println'd and as far as I could figure, the problem is this formula is not getting called enough times. In most cases the value of lambda is "close" to 0, but it almost never is exactly zero. Which would mean that the function gets called, let's say, 10 times per second, so I would have to drag the mouse real slow to archieve something. I also tried deleting the line when lambda is between (-100, 100) but I only ended up deleting lines that were not underneith the 10x10 square. So could someone help me with this? I basically want to check if a line defined by two points intersects a rectangle, and if it does then delete that line.

Share this post


Link to post
Share on other sites
Advertisement
Here is my suggestion for what it is worth.
1. Find the slope of the line.
double slope = (m1.y - m2.y)/(m1.x - m2.x);
2. Then create a loop that starts at the beginning of the line and takes points from the line and checks to see if it is in the rectangle.
for (int i = 0; i*slope + m1.y < m2.y; i++)//cycles through the line
3. Now create a Rectangle2D object that will hold the rectangle of the eraser.
Rectangle2D rectangle = new Rectangle2D.Double (eraser.x,eraser.y,eraser.width,eraser.height);

I think you need to import java.awt.geom.Rectangle2D.
4. In the body of the loop check to see if the point is in the rectangle.
if (rectangle.contains(m1.x+i,m1.y+(int)(i*slope))
deleteLine(m1,m2);
So, it should look something like:

Rectangle2D rectangle = new Rectangle2D.Double (eraser.x,eraser.y,eraser.width, eraser.height);

for (int i = 0; i*slope + m1.y < m2.y; i++)
{
if (rectangle.contains(m1.x+i,m1.y+(int)(i*slope))
{
deleteLine(m1,m2);
break;
}
}


Hope that is as clear as mud.

Share this post


Link to post
Share on other sites
If you have the slope, and at least one point you can create a function, more or less that will map all the points on the line, to y values of x. Then all you have to do is call the function with the values from the eraser's left edge, to the eraser's right edge until the function produces an x,y pair that is in the region of the eraser.

The trouble is then how many samples do you want ot take? 10? 100? How close is close enough?

Just so you know mathematically: Point slope:

y - y2 = M(x - x2)

Add y2 to both sides: Y Intercept form

f(x) = y = M(x - x2) + y2

And slope is defined as:

M = (y2 - y1)/(x2 - x1)

Where (x1,x2) and (x2,y2) Are end points of the line.

Let eraser.leftX = 0, and eraser.rightX = 10

for( int i=eraser.leftX; i<eraser.rightX+1; i++ ) {
int lineY = f(i);
if( lineY <= eraser.topY && lineY >= eraser.bottomY ) {
return true;
}
}

return false;

This is pretty much what BobTheElder said. I thought it might make it a little clearer with some nmeumonic names, and the mathematics -- to help you remember algebra 1 stuff.

Share this post


Link to post
Share on other sites
Thanks for your advices, I solved the problem in a bit different way, without having to calculate anything. From the Java Gaming forum I've found out that Java already has an in-built function for this. There is a Rectangle and a Line object, and the Rectangle has an intersectsLine() method. Who would've thought of that [wink]

This is the entire code that I needed. It works perfectly:
public boolean cutsPath(int sx, int sy, int fx, int fy)
{
Rectangle rect = new Rectangle(sx,sy,fx-sx,fy-sy);
Line2D.Float line = new Line2D.Float(m1.x,m1.y,m2.x,m2.y);
return rect.intersectsLine(line);
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!