Skip to main content
Rollback to Revision 2 - Edit approval overridden by post owner or moderator
Source Link
MAnd
  • 4.9k
  • 3
  • 25
  • 43

*This can also be done by checking only two lines of the rectangle; by checking an X that is made inside the rect. Say, the top left is (x1,y1), and the bottom right is (x2,y2). Then only checking the line segments (x1,y1)-(x2,y2) and (x1,y2)-(x2,y1). In this case, if r1 is the top left and r2 is the top right, r3 is the bottom left and r4 is the bottom right.

Vector2? LSegRec_IntersPoint_v01(Vector2 p1, Vector2 p2, Vector2 r1, Vector2 r2, Vector2 r3, Vector2 r4)
{
    Vector2? intersection = null;
    intersection = LSegsIntersectionPoint(p1,p2,r1,r4);
    if(intersection == null) intersection = LSegsIntersectionPoint(p1,p2,r3,r2);
    return intersection;
}

*This can also be done by checking only two lines of the rectangle; by checking an X that is made inside the rect. Say, the top left is (x1,y1), and the bottom right is (x2,y2). Then only checking the line segments (x1,y1)-(x2,y2) and (x1,y2)-(x2,y1). In this case, if r1 is the top left and r2 is the top right, r3 is the bottom left and r4 is the bottom right.

Vector2? LSegRec_IntersPoint_v01(Vector2 p1, Vector2 p2, Vector2 r1, Vector2 r2, Vector2 r3, Vector2 r4)
{
    Vector2? intersection = null;
    intersection = LSegsIntersectionPoint(p1,p2,r1,r4);
    if(intersection == null) intersection = LSegsIntersectionPoint(p1,p2,r3,r2);
    return intersection;
}

*This can also be done by checking only two lines of the rectangle; by checking an X that is made inside the rect. Say, the top left is (x1,y1), and the bottom right is (x2,y2). Then only checking the line segments (x1,y1)-(x2,y2) and (x1,y2)-(x2,y1). In this case, if r1 is the top left and r2 is the top right, r3 is the bottom left and r4 is the bottom right.

Vector2? LSegRec_IntersPoint_v01(Vector2 p1, Vector2 p2, Vector2 r1, Vector2 r2, Vector2 r3, Vector2 r4)
{
    Vector2? intersection = null;
    intersection = LSegsIntersectionPoint(p1,p2,r1,r4);
    if(intersection == null) intersection = LSegsIntersectionPoint(p1,p2,r3,r2);
    return intersection;
}

*This can also be done by checking only two lines of the rectangle; by checking an X that is made inside the rect. Say, the top left is (x1,y1), and the bottom right is (x2,y2). Then only checking the line segments (x1,y1)-(x2,y2) and (x1,y2)-(x2,y1). In this case, if r1 is the top left and r2 is the top right, r3 is the bottom left and r4 is the bottom right.

Vector2? LSegRec_IntersPoint_v01(Vector2 p1, Vector2 p2, Vector2 r1, Vector2 r2, Vector2 r3, Vector2 r4)
{
    Vector2? intersection = null;
    intersection = LSegsIntersectionPoint(p1,p2,r1,r4);
    if(intersection == null) intersection = LSegsIntersectionPoint(p1,p2,r3,r2);
    return intersection;
}
added 3724 characters in body
Source Link
MAnd
  • 4.9k
  • 3
  • 25
  • 43

TheAs you will easily find out, the most straight-forward solution is to run multiple times an algorithm that checks whether there is an intersection between the segment formed by Point1 and Point2 (let's call them p1 and p2) and the ones formed by each of the vertices of the rectangle (let's call them r1, r2, r3 and r4).

Now, considering that you have mentioned to me in the comments of your question that p1 is always inside the rectangle, you will never have more than one intersection between the segment formed by p1 and p2, and the rectangle. So, you just have to repeat itthe above code for each sides of the rectangle, like with:

Vector2? intersection1LSegRec_IntersPoint_v01(Vector2 p1, Vector2 p2, Vector2 r1, Vector2 r2, Vector2 r3, Vector2 r4)
{
    Vector2? intersection = null;
    intersection = LSegsIntersectionPoint(p1,p2,r1,r2);
Vector2 intersection2   if(intersection == null) intersection = LSegsIntersectionPoint(p1,p2,r2,r3);
Vector2 intersection3   if(intersection == null) intersection = LSegsIntersectionPoint(p1,p2,r3,r4);
Vector2 intersection4   if(intersection == null) intersection = LSegsIntersectionPoint(p1,p2,r4,r1);
    return intersection;
}

HoweverI don't know if you plan to perform such checking hundreds of thousands of times, noteor if performance even is an issue for you. Anyways, for completeness (and for fun), notice that a line segment can intersect at 0you also have said in your question that your rectangle is axis aligned. This information, 1 or 2 sides of asummed to the fact that p1 is always inside the rectangle, can raise a much faster solution. Not necessarily easier to code (not only onesorry for calling it "easier"), but nevermuch more than two)efficient in case you have a lot of segment-rectangle checks to make.

Therefore The trick here is the following. You first calculate the min_x, we can do all at oncemin_y, max_x and optimizing itmax_y of your rectangle. Then, by doing something likeyou can use the following function to first check where p2 is in relation to the rectangle and then just do the line-seg checks if the precise sides of the rectangle (this part I didn'tnever having to check because I'm not in homemore than 2, so it may have one or two misspeling or somethingwhile in the worst case the first solution had to check all 4):

List<Vector2>Vector2? LSegRec_IntersectionPointLSegRec_IntersPoint_v02(Vector2 p1, Vector2 p2, Vector2float r1min_x, Vector2float r2min_y, Vector2float r3max_x, float max_y)
{
    Vector2? r4intersection;

    if (p2.x < min_x) //If the second point of the segment is at left/bottom-left/top-left of the AABB
    {
  List<Vector2> final_results =    if (p2.y > min_y && p2.y < max_y) { return LSegsIntersectionPoint(p1, p2, new List<Vector2>Vector2(min_x, min_y), new Vector2(min_x, max_y)); } //If it is at the left
  Vector2 partial_result;     else if (p2.y < min_y) //If it is at the bottom-left
        {
  partial_result          intersection = LSegsIntersectionPoint(p1, p2,r1 new Vector2(min_x,r2 min_y), new Vector2(max_x, min_y));
            if (partial_resultintersection !=== null) final_results.Addintersection = LSegsIntersectionPoint(partial_resultp1, p2, new Vector2(min_x, min_y), new Vector2(min_x, max_y));
            return intersection;
  partial_result      }
        else //if p2.y > max_y, i.e. if it is at the top-left
        {
            intersection = LSegsIntersectionPoint(p1, p2,r2 new Vector2(min_x,r3 max_y), new Vector2(max_x, max_y));
            if (partial_resultintersection !=== null) final_results.Addintersection = LSegsIntersectionPoint(partial_resultp1, p2, new Vector2(min_x, min_y), new Vector2(min_x, max_y));
            return intersection;
        }
    }
    
    else if (final_resultsp2.Countx <> 2max_x) #//If thisthe second point of the segment is useful,at sinceright/bottom-right/top-right of the AABB
    {
        if we(p2.y already> foundmin_y 2&& intersectionp2.y points< max_y) { return LSegsIntersectionPoint(p1, wep2, don'tnew needVector2(max_x, tomin_y), keepnew checkingVector2(max_x, max_y)); } //If it is at the right
        else if (p2.y < min_y) //If it is at the bottom-right
        {
    partial_result        intersection = LSegsIntersectionPoint(p1, p2,r3 new Vector2(min_x,r4 min_y), new Vector2(max_x, min_y));
            if (partial_resultintersection !=== null) final_results.Addintersection = LSegsIntersectionPoint(partial_resultp1, p2, new Vector2(max_x, min_y), new Vector2(max_x, max_y));
  }          return intersection;
        }
        else //if(final_results p2.County <> 2)max_y, #i.e. thisif it is usefulat the top-left
        {
            intersection = LSegsIntersectionPoint(p1, sincep2, ifnew weVector2(min_x, alreadymax_y), foundnew 2Vector2(max_x, max_y));
            if (intersection points== null) intersection = LSegsIntersectionPoint(p1, wep2, don'tnew needVector2(max_x, tomin_y), keepnew checkingVector2(max_x, max_y));
            return intersection;
        }
    }
    
    else //If the second point of the segment is at top/bottom of the AABB
    {
    partial_result =   if (p2.y < min_y) return LSegsIntersectionPoint(p1, p2,r4 new Vector2(min_x,r1 min_y), new Vector2(max_x, min_y)); //If it is at the bottom
        if (partial_resultp2.y !=> nullmax_y) final_results.Addreturn LSegsIntersectionPoint(partial_resultp1, p2, new Vector2(min_x, max_y), new Vector2(max_x, max_y)); //If it is at the top
    }
    
    return final_results;null;
    
}

The code above repeatsBut notice: that second solution is only faster if you can calculate the min_x, min_y, max_x and max_y of your rectangle beforehand. Otherwise, you will have to calculate those inside the function "LSegRec_IntersectionPoint" for each sideand that will make it slower. Let's say you use the exact same code as the second solution, but just doing that calculation of mins and maxs of the rectangle within the function:

Vector2? LSegRec_IntersPoint_v03(Vector2 p1, Vector2 p2, Vector2 r1, Vector2 r2, Vector2 r3, Vector2 r4)
{
    Vector2? intersection;
    float min_x = Mathf.Min(r1.x, r2.x, r3.x, r4.x);
    float min_y = Mathf.Min(r1.y, r2.y, r3.y, r4.y);
    float max_x = Mathf.Max(r1.x, r2.x, r3.x, r4.x);
    float max_y = Mathf.Max(r1.y, r2.y, r3.y, r4.y);

... then the rest of the the second version continues here

In order to profile that, but only if thereI created a rectangle where r1 = (-2,-2), r2 = (2,-2), r3 = (2,2) and r4 = (-2,2), p1 = (0,0) and then randomly positioned p2 a bunch of times, always have its X and Y coordinates between -4 and 4. Here are notthe results, where N is the number of iterations of the simulation:

enter image description here

Notice that, as expected, version 2 intersection points already foundis generally much faster to run. AtThe only exception is for N<=1000, when it is roughly the endsame thing. For greater number of iterations, however, it returns a listbecomes much faster. But as I've pointed, that's only the case if the mins and maxs of the intersection pointsrectangle are calculated beforehand, because if they have to be calculated within the function (be it 1 or 2, you will not miss anyi.e. v03), then it becomes much slower.

The most straight-forward solution is to run multiple times an algorithm that checks whether there is an intersection between the segment formed by Point1 and Point2 (let's call them p1 and p2) and the ones formed by each the vertices of the rectangle (let's call them r1, r2, r3 and r4).

Now you just have to repeat it for each sides of the rectangle, like:

Vector2 intersection1 = LSegsIntersectionPoint(p1,p2,r1,r2);
Vector2 intersection2 = LSegsIntersectionPoint(p1,p2,r2,r3);
Vector2 intersection3 = LSegsIntersectionPoint(p1,p2,r3,r4);
Vector2 intersection4 = LSegsIntersectionPoint(p1,p2,r4,r1);

However, note that a line segment can intersect at 0, 1 or 2 sides of a rectangle (not only one, but never more than two).

Therefore, we can do all at once and optimizing it, by doing something like the following (this part I didn't check because I'm not in home, so it may have one or two misspeling or something):

List<Vector2> LSegRec_IntersectionPoint(Vector2 p1, Vector2 p2, Vector2 r1, Vector2 r2, Vector2 r3, Vector2 r4)
{
  List<Vector2> final_results = new List<Vector2>();
  Vector2 partial_result;

  partial_result = LSegsIntersectionPoint(p1,p2,r1,r2);
  if(partial_result != null) final_results.Add(partial_result);

  partial_result = LSegsIntersectionPoint(p1,p2,r2,r3);
  if(partial_result != null) final_results.Add(partial_result);

  if(final_results.Count < 2) # this is useful, since if we already found 2 intersection points, we don't need to keep checking
  {
    partial_result = LSegsIntersectionPoint(p1,p2,r3,r4);
    if(partial_result != null) final_results.Add(partial_result);
  }

  if(final_results.Count < 2) # this is useful, since if we already found 2 intersection points, we don't need to keep checking
  {
    partial_result = LSegsIntersectionPoint(p1,p2,r4,r1);
    if(partial_result != null) final_results.Add(partial_result);
  }

  return final_results;

}

The code above repeats the function "LSegRec_IntersectionPoint" for each side of the rectangle, but only if there are not 2 intersection points already found. At the end, it returns a list of the intersection points (be it 1 or 2, you will not miss any).

As you will easily find out, the most straight-forward solution is to run multiple times an algorithm that checks whether there is an intersection between the segment formed by Point1 and Point2 (let's call them p1 and p2) and the ones formed by each of the vertices of the rectangle (let's call them r1, r2, r3 and r4).

Now, considering that you have mentioned to me in the comments of your question that p1 is always inside the rectangle, you will never have more than one intersection between the segment formed by p1 and p2, and the rectangle. So, you just have to repeat the above code for each sides of the rectangle with:

Vector2? LSegRec_IntersPoint_v01(Vector2 p1, Vector2 p2, Vector2 r1, Vector2 r2, Vector2 r3, Vector2 r4)
{
    Vector2? intersection = null;
    intersection = LSegsIntersectionPoint(p1,p2,r1,r2);
    if(intersection == null) intersection = LSegsIntersectionPoint(p1,p2,r2,r3);
    if(intersection == null) intersection = LSegsIntersectionPoint(p1,p2,r3,r4);
    if(intersection == null) intersection = LSegsIntersectionPoint(p1,p2,r4,r1);
    return intersection;
}

I don't know if you plan to perform such checking hundreds of thousands of times, or if performance even is an issue for you. Anyways, for completeness (and for fun), notice that you also have said in your question that your rectangle is axis aligned. This information, summed to the fact that p1 is always inside the rectangle, can raise a much faster solution. Not necessarily easier to code (sorry for calling it "easier"), but much more efficient in case you have a lot of segment-rectangle checks to make. The trick here is the following. You first calculate the min_x, min_y, max_x and max_y of your rectangle. Then, you can use the following function to first check where p2 is in relation to the rectangle and then just do the line-seg checks if the precise sides of the rectangle (never having to check more than 2, while in the worst case the first solution had to check all 4):

Vector2? LSegRec_IntersPoint_v02(Vector2 p1, Vector2 p2, float min_x, float min_y, float max_x, float max_y)
{
    Vector2? intersection;

    if (p2.x < min_x) //If the second point of the segment is at left/bottom-left/top-left of the AABB
    {
        if (p2.y > min_y && p2.y < max_y) { return LSegsIntersectionPoint(p1, p2, new Vector2(min_x, min_y), new Vector2(min_x, max_y)); } //If it is at the left
        else if (p2.y < min_y) //If it is at the bottom-left
        {
            intersection = LSegsIntersectionPoint(p1, p2, new Vector2(min_x, min_y), new Vector2(max_x, min_y));
            if (intersection == null) intersection = LSegsIntersectionPoint(p1, p2, new Vector2(min_x, min_y), new Vector2(min_x, max_y));
            return intersection;
        }
        else //if p2.y > max_y, i.e. if it is at the top-left
        {
            intersection = LSegsIntersectionPoint(p1, p2, new Vector2(min_x, max_y), new Vector2(max_x, max_y));
            if (intersection == null) intersection = LSegsIntersectionPoint(p1, p2, new Vector2(min_x, min_y), new Vector2(min_x, max_y));
            return intersection;
        }
    }
    
    else if (p2.x > max_x) //If the second point of the segment is at right/bottom-right/top-right of the AABB
    {
        if (p2.y > min_y && p2.y < max_y) { return LSegsIntersectionPoint(p1, p2, new Vector2(max_x, min_y), new Vector2(max_x, max_y)); } //If it is at the right
        else if (p2.y < min_y) //If it is at the bottom-right
        {
            intersection = LSegsIntersectionPoint(p1, p2, new Vector2(min_x, min_y), new Vector2(max_x, min_y));
            if (intersection == null) intersection = LSegsIntersectionPoint(p1, p2, new Vector2(max_x, min_y), new Vector2(max_x, max_y));
            return intersection;
        }
        else //if p2.y > max_y, i.e. if it is at the top-left
        {
            intersection = LSegsIntersectionPoint(p1, p2, new Vector2(min_x, max_y), new Vector2(max_x, max_y));
            if (intersection == null) intersection = LSegsIntersectionPoint(p1, p2, new Vector2(max_x, min_y), new Vector2(max_x, max_y));
            return intersection;
        }
    }
    
    else //If the second point of the segment is at top/bottom of the AABB
    {
        if (p2.y < min_y) return LSegsIntersectionPoint(p1, p2, new Vector2(min_x, min_y), new Vector2(max_x, min_y)); //If it is at the bottom
        if (p2.y > max_y) return LSegsIntersectionPoint(p1, p2, new Vector2(min_x, max_y), new Vector2(max_x, max_y)); //If it is at the top
    }
    
    return null;
    
}

But notice: that second solution is only faster if you can calculate the min_x, min_y, max_x and max_y of your rectangle beforehand. Otherwise, you will have to calculate those inside the function and that will make it slower. Let's say you use the exact same code as the second solution, but just doing that calculation of mins and maxs of the rectangle within the function:

Vector2? LSegRec_IntersPoint_v03(Vector2 p1, Vector2 p2, Vector2 r1, Vector2 r2, Vector2 r3, Vector2 r4)
{
    Vector2? intersection;
    float min_x = Mathf.Min(r1.x, r2.x, r3.x, r4.x);
    float min_y = Mathf.Min(r1.y, r2.y, r3.y, r4.y);
    float max_x = Mathf.Max(r1.x, r2.x, r3.x, r4.x);
    float max_y = Mathf.Max(r1.y, r2.y, r3.y, r4.y);

... then the rest of the the second version continues here

In order to profile that, I created a rectangle where r1 = (-2,-2), r2 = (2,-2), r3 = (2,2) and r4 = (-2,2), p1 = (0,0) and then randomly positioned p2 a bunch of times, always have its X and Y coordinates between -4 and 4. Here are the results, where N is the number of iterations of the simulation:

enter image description here

Notice that, as expected, version 2 is generally much faster to run. The only exception is for N<=1000, when it is roughly the same thing. For greater number of iterations, however, it becomes much faster. But as I've pointed, that's only the case if the mins and maxs of the rectangle are calculated beforehand, because if they have to be calculated within the function (i.e. v03), then it becomes much slower.

Source Link
MAnd
  • 4.9k
  • 3
  • 25
  • 43
Loading