Getting Every Point on a Line

Hello!

I'm a java beginner and have recently encountered a problem that I have not been able to solve or find a solution to.

Hopefully this is also in the correct sub-forum.

In my program I have specified a **Line2D.double(x1, y1, x2, y2)** and I want to check if a circle object of mine collides with it. Therefore I'm currently trying to achieve this by checking how long distance the circle center-point is from any point on the line.

To do this I want to create a **Point[i]** object, containing every Point on the line. I know that such a point can be given by **y=k*x+m** and that I can calculate k through **k=(y2-y1)/(x2-x1)** and m through **m = k*x1+y1**. What I do not know is how to decide what X to use for properly calculating y to create one point on every pixel displayed by drawing the Line2D object.

So, I wonder, **how can I get every point on the line stored in a Point[i]?** *(or, is there any simpler (I assume there are many more effective methods, but I still don't have the knowledge of doing anything too fancy) way of checking collision between a line and a circle?)* The method used to get every point on the line needs to work even if k is approaching Infinity.

Re: Getting Every Point on a Line

Can you use geometry? The closed point will be one where the circle's radius is at right angles to the line.

Is the distance to that point < radius?

Re: Getting Every Point on a Line

Hm... I don't quite understand how I would know what point is closest by checking angles. Could you explain that more?

The radius is of course what I'm using though. Currently I want to check if the distance from the circle center point to any of the points on the line is shorter than the circle radius. If it is, it is a collision. But for that I need to get every point on that line.

Re: Getting Every Point on a Line

Quote:

distance from the circle center point to any of the points on the line

The point on the line at right angles to the radius would be the closest. Given two points on a right angle (circle center and any point on the line) can you compute the third point at the right angle where the radius crosses the line? Would there be trig functions to solve that?

Re: Getting Every Point on a Line

I think I understand what you mean, and I also think there are trig functions enough to do that, so I will go ahead and try. It definitely seems better than my method, only problem is that I have very little experience in trigonometry so far.

If anyone could tell me how to get all the points on the line without using exterior points, if I, say, would want to draw a replica of the original line using point objects, one for every pixel that were to be drawn, that would be great too. In the meantime I'll be trying angles.

Re: Getting Every Point on a Line

Quote:

how to get all the points on the line

You only need the one point that's at right angles to the radius.

Also look at using protagoras's theorem with the equation for the line.

Re: Getting Every Point on a Line

Ah, I think I'm starting to get it now. I'm not a native english speaker so I interpreted "right angle" as "correct angle", instead of an angle of 90 degrees, which I assume is what you meant. Thanks!

Re: Getting Every Point on a Line

Sorry. Yes I meant right angle to be one of 90 degrees.

Some more thoughts on seeing the problem.

From the center of the circle, extend a line on the y axis until it crosses the line and a line on the x axis until it crosses the line. Given the equation for a line and a point on the line you can compute the x value for where the y line crosses and the y value for where the x line crosses. Now you have a triangle with three known sides. The line from the center of the circle perpendicular to the line should be able to be computed.

Re: Getting Every Point on a Line

Hm... yes, I will definitely take an even closer look at this tomorrow. I'm having thoughts about what to do when the circle is close to the edges of my line though, as the line, and ultimately lines, I will have to check on are finite, like walls in a room as to say. Perhaps that can be solved by adding rules for the corner cases and extending the "wall" lines to be practically infinite.

That would not be needed if I could just add every point on the lines to variable and run the distance check on every such point. Perhaps though that is not needed/possible/unnecessarily difficult. Anyways, I guess I'm too tired to think more of it for now. So I'll get some sleep and check back tomorrow.

Re: Getting Every Point on a Line

If you use a little math, it's possible to derive a simpler way to check if a circle and a line intersect.

The equation for a circle is (in Cartesian coordinates):

(x-a)^2 + (y-b)^2 = r^2

The equation for a line is (again in Cartesian coordinates):

y = mx + c

To intersect means that the x/y pairs are the same, so start by assuming they will intersect. This allows us substitute one equation into the other:

(x-a)^2 + (mx + c - b)^2 = r^2

The only variable left is x, so let's solve for x.

x^2 - 2ax + a^2 + (mx)^2 - 2(c-b)mx + (c-b)^2 = r^2

(m+1) x^2 - 2a(c-b)m x + a^2 + (c-b)^2 = r^2

This is a simple quadratic formula, and it has 3 possible outcomes: there's no real solution, there's one unique real solution, and there's two unique real solutions. These corresponds to the 3 possible outcomes for a line/circle intersection.

Once you have the x solutions (if any), plug them back into line equation and solve for y.

If you want to check for a line-segment/circle intersection, once you have the solutions for line/circle intersection just check to see if the intersection points are on the line segment (simple distance test will do).

Re: Getting Every Point on a Line

Line2D has a ptLineDist(Point2D) method that takes care of the awkwardness involved in the fact that Line2D is a line **segment**. There's a whole bunch of methods with very similar functionality: basically a circle intersects a line segment if and only if the distance from the line segment to the center of the circle is less than or equal to the radius of the circle.

[Edit] wrongness removed...

Re: Getting Every Point on a Line

When in doubt read the manual.

Re: Getting Every Point on a Line

Well, it seems I was able to work it out, thanks to awesome help!

Thank you very much :)

Re: Getting Every Point on a Line