Getting distance of a point in a 2d triangle without calculating perpendicular..

Alright, so I’m trying to move a ball to it’s closest location along a line that it hits. But my dist.y is saying it’s extremely far away even when I’m right next to the line. Can anyone tell me whats going on?

Here is the code:

public Vector2f LineVsCircleCollision(Vector2f lineA, Vector2f lineB, Vector2f circle, float rad)
	{
		Vector2f line = new Vector2f(0,0);     // the line vector
		Vector2f.sub(lineB, lineA, line);
	    Vector2f circ = new Vector2f(0,0);     // the vector of the origin line point to the circle center
	    Vector2f.sub(circle, lineA, circ);
	    
	    // project the circle vector onto the line vector
	    float proj = Vector2f.dot(line,circ) / Vector2f.dot(line,line);

	    if(proj < 0)   proj = 0;
	    else if(proj > 1)   proj = 1;

	    // apply the projected position to our vector, and offset it by our origin
	    Vector2f nearest = new Vector2f(0,0);
	    line.scale(proj);
	    Vector2f.add(line, lineA, nearest);

	    // 'nearest' is now the point on the line nearest the circle
	    //  see if the distance between this point and the circle center is greater than the radius.
	    //   if the radius is larger, the circle intersects

	    Vector2f dist = new Vector2f(0,0);
	    Vector2f.sub(circle, nearest, dist); // the vector between the circle and the nearest point on the line
	    
	    System.out.println("hit: " + (Vector2f.dot(dist,dist) <= (rad*rad)));
	    System.out.println("x: " + dist.x + " y: " + dist.y);
    	return dist;
	}

I think your problem with the large y values could be that you are scaling the line, but since the circle radius is perpendicular to the line you should be interested in scaling the normalized normal instead.

I´m wondering about the projection though… It´s not supposed to be

Line DOT circ / Line DOT line, right? Isn´t projection

Line DOT circ / Line^2? Or am I missing something…?

Alright, so I got this code, and it doesn’t seem to work on all the angles. Like the ball jumps back when touching the top, the sides seem to work fine in that the ball goes right up to the wall of the square , and the bottom it jumps back up to where the top jumps back to. Can someone tell me what I’m doing wrong?

public Vector2f GetClosestPoint(Vector2f start, Vector2f end, Vector2f pos){
		Vector2f start_to_point = new Vector2f(0,0);
		Vector2f.sub(pos,start,start_to_point);
		
		Vector2f start_to_end = new Vector2f(0,0);
		Vector2f.sub(end, start, start_to_end);

		float t =  Vector2f.dot(start_to_point,  start_to_end) / start_to_end.lengthSquared();            // The normalized "distance" from a to
		                                      //   your closest point
	
		return new Vector2f(start.x + start_to_end.x*t, start.y + start_to_end.y*t );
		                                      // Add the distance to A, moving
		                                      //   towards B
	}

I assume this is looking at a line that goes from start to end and is finding the closest point to pos? What library is your Vector2f coming from? The ones I googled (jME, slick, and java3d) don’t have 3 parameter static sub methods. Also can you describe a bit more about where it fails? I’m finding it a bit hard to follow.

it’s 4 lines, making up a square, actually. The lib is LWJGL, and it fails when the ball touches the top, and bottom lines. The side lines work just as they should.

Okay, I got it to work right as intended, but now I’m having trouble with the next step, making it so it pushes the ball slightly out the the line based on the direction it came from (so it’ll slide on the wall if it keeps trying to go the same directional vector) IE:



ball -> || <- wall
       / |


This is the working code I have that gets the player right on the edge of any angle:

public Vector2f GetClosestPoint(Vector2f start, Vector2f end, Vector2f p){
		Vector2f start_to_point = new Vector2f(0,0);
		Vector2f.sub(p,start,start_to_point);				//Storing vector A->P

		Vector2f start_to_end = new Vector2f(0,0);
		Vector2f.sub(end, start, start_to_end);				//Storing vector A->B

		float t =  Vector2f.dot(start_to_point,  start_to_end) / start_to_end.lengthSquared();            // The normalized "distance" from a to
		                                      //   your closest point
		System.out.println("t: " + t );
			
		start_to_end.scale(t);
		Vector2f fin = new Vector2f(0,0);
		Vector2f.add(start, start_to_end, fin);

		System.out.println("fin.x: " + fin.x + " fin.y: " + fin.y);
		
		return new Vector2f(fin.x, Math.abs(fin.y));
	}

Also, keep in mind that I do have the ball’s velocity vector stored, so if I need that I can easily get it.

At the bottom of the code snippet in this THREAD are formulations for reflection…read the comments.

Line DOT Line = xx + yy = Line^2, right?

Okay, I got it. Thank you all for your help ;D


public Vector2f GetClosestPoint(Vector2f start, Vector2f end, Vector2f one, Vector2f two, Vector2f p, Vector2f m){
		Vector2f start_to_point = new Vector2f(0,0);
		Vector2f.sub(p,start,start_to_point);				//Storing vector A->P
		//start_to_point.normalise();
		Vector2f start_to_end = new Vector2f(0,0);
		Vector2f.sub(end, start, start_to_end);				//Storing vector A->B
		//start_to_end.normalise();

		float t =  Vector2f.dot(start_to_point,  start_to_end) / start_to_end.lengthSquared();            // The normalized "distance" from a to
		                                      //   your closest point
		System.out.println("t: " + t );
		
		start_to_end.scale(t);
		Vector2f fin = new Vector2f(0,0);
		Vector2f.add(start, start_to_end, fin);
		
		System.out.println("fin.x: " + fin.x + " fin.y: " + fin.y);
		
		Vector2f one_to_two = new Vector2f(0,0);
		Vector2f.sub(two,  one, one_to_two);
		
		Vector2f normal = new Vector2f(0,0);
		normal = new Vector2f(-one_to_two.y, one_to_two.x);
		normal.normalise();
		System.out.println("n.x: " + normal.x + " n.y: " + normal.y);
		
		normal.scale(movementSpeed * 10);
		
		Vector2f.add(fin, normal, fin);
		
		
		return new Vector2f(fin.x, Math.abs(fin.y));
	}

Looks like I spoke too soon. whenever a line isn’t in the center it messes up, and I for the life of me can’t figure out how to fix it. Code is in my post above, can anyone tell me why it’s acting so strange?

Okay, it now works no matter where you are:


public Vector2f GetClosestPoint(Vector2f start, Vector2f end, Vector2f one, Vector2f two, Vector2f p, Vector2f m){
	      Vector2f start_to_point = new Vector2f(0,0);
	      Vector2f.sub(p,one,start_to_point);            //Storing vector A->P
	      //start_to_point.normalise();
	      Vector2f start_to_end = new Vector2f(0,0);
	      Vector2f.sub(two, one, start_to_end);            //Storing vector A->B
	      //start_to_end.normalise();

	      float t =  Vector2f.dot(start_to_point,  start_to_end) / start_to_end.lengthSquared();            // The normalized "distance" from a to
	                                            //   your closest point
	      System.out.println("t: " + t );
	      
	      start_to_end.scale(t);
	      Vector2f fin = new Vector2f(0,0);
	      Vector2f.add(one, start_to_end, fin);
	      
	      System.out.println("fin.x: " + fin.x + " fin.y: " + fin.y);
	      
	      Vector2f one_to_two = new Vector2f(0,0);
	      Vector2f.sub(two,  one, one_to_two);
	      one_to_two.scale(0.5f);
	      Vector2f normal = new Vector2f(0,0);
	      normal = new Vector2f(-one_to_two.y, one_to_two.x);
	      if(p.x < 0 && p.y < 0){
	    	  if(Math.abs(p.x) < Math.abs(two.x)) normal = new Vector2f(one_to_two.y, -one_to_two.x);
	      }
	      
	      if(p.x > 0 && p.y > 0){
	    	  if(p.x < one.x && p.x < two.x) normal = new Vector2f(one_to_two.y, -one_to_two.x);
	      }
	     
	      normal.normalise();
	      System.out.println("n.x: " + normal.x + " n.y: " + normal.y);
	      
	      normal.scale(movementSpeed * 30);
	      
	      Vector2f.add(fin, normal, fin);
	      
	      if(p.y > 0.0f) return new Vector2f(fin.x, Math.abs(fin.y));
	      return new Vector2f(fin.x, -Math.abs(fin.y));
	   }

Thank you all for your help. :>

That´s right of course! Just got me a bit confused. :slight_smile:

Nevermind, I fixed it.

Alright, so I got this code that is suppose to find me the nearest point on a quad, but it seems to not calculate the quad properly. It seems to think it’s tilted when it’s not. or rather it’s calculating a line between the quads min.x,min.y and max.x, max.y points, but not the min.x, max.y or max.x, min.y points.

My question is how do I make this code calculate the quad as a whole?

public Vector3f GetClosestPoint(Vector3f start, Vector3f end, Vector3f point){
          Vector3f fin = new Vector3f(0,0,0);

          Vector3f start_to_point = new Vector3f(0,0,0);
          Vector3f.sub(point,start,start_to_point);            //Storing vector A->P
          Vector3f start_to_end = new Vector3f(0,0,0);
          Vector3f.sub(end, start, start_to_end);            //Storing vector A->B

          float t =  Vector3f.dot(start_to_point,  start_to_end) / start_to_end.lengthSquared();            // The normalized "distance" from a to
          start_to_end.scale(t); 
          Vector3f.add(start, start_to_end, fin);

          return new Vector3f(fin);
    }

There is no such thing as ‘closest point to quad’ , just like there is no direct calculation for ‘closest point to car’.

A quad is comprised of two triangles, for which you can actually calculate the closest point on the triangle, to any other point.

The code I’m using in my collision detection code is this:

(note: Vector3f is part of the LWJGL library, so if you want the src to that you’ll have to find it on their site, but it’s self explaining, and error free.)

(Note2:Tri is a class composed of three of LWJGL’s Vector3fs. v1, v2, and v3.)

  public Vector<Tri> getTrisTouching(Vector3f pos, float radius){
    		Vector<Tri> tempVec = new Vector<Tri>();
    		for(int i = 0; i < tris.size(); i++){
    			Tri t = tris.get(i);
    
    			Vector3f one_to_point = new Vector3f(0,0,0);
    			Vector3f.sub(pos,t.v1,one_to_point);            //Storing vector A->P
    	     
    			Vector3f one_to_two = new Vector3f(0,0,0);
    			Vector3f.sub(t.v2,t.v1, one_to_two);            //Storing vector A->B
    	      
    			Vector3f one_to_three = new Vector3f(0,0,0);
    			Vector3f.sub(t.v3, t.v1, one_to_three);            //Storing vector A->C
    	      
    			float q1 =  Vector3f.dot(one_to_point,  one_to_two) / one_to_two.lengthSquared();            // The normalized "distance" from a to
    			float q2 =  Vector3f.dot(one_to_point,  one_to_three) / one_to_three.lengthSquared();            // The normalized "distance" from a to
    	      
    			
    			
    			if (q1 > 0 && q2 > 0 && q1 + q2 < 1){
    				tempVec.add(t);
    			}
    		}	
    		
    		return tempVec;
    	}

My question is how do I correctly see if a point in space is touching one of my triangles?

The easiest way is to create vectors from each triangle vertex to your point (so the differences between the vertices and the point). Then you can use the dot product to get the angles between these vectors, sum all the angles, and if they’re < 360 then it’s inside the triangle. That’s not very fast, but it should be fine for most situations.If I recall you actually need to use the cross product too to see if the points is on the correct side of a side. I think this is called the “same side” technique.

You can also use barycentric coordinates to do it, which involves extending each side of the triangle into its own plane, and seeing if the point lies in any of those planes (if it does it’s outside). You should be able to Google that one, it’s faster but more complicated to implement.

Like this, right?

Vector3f one_to_point = new Vector3f(0,0,0);
			Vector3f.sub(pos,t.v1,one_to_point);            //Storing vector A->P
			
			Vector3f two_to_point = new Vector3f(0,0,0);
			Vector3f.sub(pos,t.v2,two_to_point);            //Storing vector B->P
			
			Vector3f three_to_point = new Vector3f(0,0,0);
			Vector3f.sub(pos,t.v3,three_to_point);            //Storing vector C->P
			
			float angle = Vector3f.dot(one_to_point, two_to_point);
			angle += Vector3f.dot(two_to_point, three_to_point);
			angle += Vector3f.dot(three_to_point, one_to_point);

Yeah, but you also need to check the cross product to make sure it’s on the right side. Like this (broken into two functions to preserve code).


public boolean isPointInTriangle( Vector3f p, Vector3f a, Vector3f b, Vector3f c )
{
    return ( pointsAreOnSameSide(p, a, b, c) && pointsAreOnSameSide(p, b, a, c) && pointsAreOnSameSide(p, c, a, b) );
}

public boolean pointsAreOnSameSide( Vector3f p1, Vector3f p2, Vector3f a, Vector3f b )
{
    Vector3f diffba = new Vector3f(0,0,0);
    Vector3f.sub( b, a, diffba );
    Vector3f diffp1a = new Vector3f(0,0,0);
    Vector3f.sub( p1, a, diffp1a );
    Vector3f diffp2a = new Vector3f(0,0,0);
    Vector3f.sub( p2, a, diffp2a );

    Vector3f cross1 = Vector3f.cross(diffba, diffp1a);
    Vector3f cross2 = Vector3f.cross(diffba, diffp2a);

    return ( Vector3f.dot( cross1, cross2 ) >= 0 );
}

Holy god LWJGL vectors are lame? Why no myVec.sub(otherVec) etc. You really need to pass everything into static functions? Stupid. Why not put both in there?

You can try the barycentric version too, which looks like it’s what you were trying. I just took this code from the internets and made it LWJGL-ready, so I don’t know if it works.


public boolean isPointInTriangle( Vector3f p, Vector3f a, Vector3f b, Vector3f c )
{
    Vector3f v0 = new Vector3f(0,0,0);
    Vector3f.sub( c, a, v0 );
    Vector3f v1 = new Vector3f(0,0,0);
    Vector3f.sub( b, a, v1);
    Vector3f v2 = new Vector3f(0,0,0);
    Vector3f.sub( p, a, v2 );

    float dot00 = Vector3f.dot(v0, v0);
    float dot01 = Vector3f.dot(v0, v1);
    float dot02 = Vector3f.dot(v0, v2);
    float dot11 = Vector3f.dot(v1, v1);
    float dot12 = Vector3f.dot(v1, v2);

    float inverse = 1.0f / (dot00 * dot11 - dot01 * dot01);
    float u = (dot11 * dot02 - dot01 * dot12) * inverse;
    float v = (dot00 * dot12 - dot01 * dot02) * inverse;

    return (u >= 0) && (v >= 0) && (u + v < 1);
}

Looks like in your original version you missed a step of dot producting (note I’m not whiz at this way of doing it either). Honestly looking at the two versions side-by-side the speed difference looks negligible. So I’d say do it the way you want. :slight_smile: