Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 14 of 14

Thread: Getting Every Point on a Line

  1. #1
    Junior Member
    Join Date
    Jul 2012
    Posts
    16
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default 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.


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,010
    Thanks
    52
    Thanked 2,276 Times in 2,247 Posts

    Default 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?
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Jul 2012
    Posts
    16
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default 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.

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,010
    Thanks
    52
    Thanked 2,276 Times in 2,247 Posts

    Default Re: Getting Every Point on a Line

    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?
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    Jul 2012
    Posts
    16
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default 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.

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,010
    Thanks
    52
    Thanked 2,276 Times in 2,247 Posts

    Default Re: Getting Every Point on a Line

    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.
    If you don't understand my answer, don't ignore it, ask a question.

  7. #7
    Junior Member
    Join Date
    Jul 2012
    Posts
    16
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default 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!

  8. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,010
    Thanks
    52
    Thanked 2,276 Times in 2,247 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  9. #9
    Junior Member
    Join Date
    Jul 2012
    Posts
    16
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default 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.

  10. #10
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default 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).

  11. #11
    Super Moderator pbrockway2's Avatar
    Join Date
    Jan 2012
    Posts
    939
    Thanks
    6
    Thanked 202 Times in 178 Posts

    Default 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...

  12. #12
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,010
    Thanks
    52
    Thanked 2,276 Times in 2,247 Posts

    Default Re: Getting Every Point on a Line

    When in doubt read the manual.
    If you don't understand my answer, don't ignore it, ask a question.

  13. #13
    Junior Member
    Join Date
    Jul 2012
    Posts
    16
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default 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

  14. #14
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,010
    Thanks
    52
    Thanked 2,276 Times in 2,247 Posts

    Default Re: Getting Every Point on a Line

    What was your solution?
    If you don't understand my answer, don't ignore it, ask a question.

Similar Threads

  1. Replies: 10
    Last Post: September 16th, 2011, 07:49 PM
  2. Reading a file line by line using the Scanner class
    By JavaPF in forum File Input/Output Tutorials
    Replies: 0
    Last Post: April 17th, 2009, 07:34 AM
  3. Reading a file line by line using the Scanner class
    By JavaPF in forum Java Code Snippets and Tutorials
    Replies: 0
    Last Post: April 17th, 2009, 07:34 AM
  4. How to Read a file line by line using BufferedReader?
    By JavaPF in forum File Input/Output Tutorials
    Replies: 0
    Last Post: May 19th, 2008, 06:32 AM
  5. How to Read a file line by line using BufferedReader?
    By JavaPF in forum Java Code Snippets and Tutorials
    Replies: 0
    Last Post: May 19th, 2008, 06:32 AM