[ad_1]
As you’ll simply discover out, probably the most straight-forward resolution is to run a number of occasions an algorithm that checks whether or not there may be an intersection between the phase shaped by Point1 and Point2 (let’s name them p1 and p2) and those shaped by every of the vertices of the rectangle (let’s name them r1, r2, r3 and r4).
A clear implementation line-seg/line-seg intersection in C# (which may simply be transformed to JavaScript, which I believe is nearer to what you want) is the next:
Vector2? LSegsIntersectionPoint(Vector2 ps1, Vector2 pe1, Vector2 ps2, Vector2 pe2)
{
// Get A,B of first line - factors : ps1 to pe1
float A1 = pe1.y-ps1.y;
float B1 = ps1.x-pe1.x;
// Get A,B of second line - factors : ps2 to pe2
float A2 = pe2.y-ps2.y;
float B2 = ps2.x-pe2.x;
// Get delta and test if the traces are parallel
float delta = A1*B2 - A2*B1;
if(delta == 0) return null;
// Get C of first and second traces
float C2 = A2*ps2.x+B2*ps2.y;
float C1 = A1*ps1.x+B1*ps1.y;
//invert delta to make division cheaper
float invdelta = 1/delta;
// now return the Vector2 intersection level
return new Vector2( (B2*C1 - B1*C2)*invdelta, (A1*C2 - A2*C1)*invdelta );
}
Now, contemplating that you’ve got talked about to me within the feedback of your query that p1 is all the time contained in the rectangle, you’ll by no means have a couple of intersection between the phase shaped by p1 and p2, and the rectangle. So, you simply must repeat the above code for every 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 do not know when you plan to carry out such checking a whole lot of 1000’s of occasions, or if efficiency even is a matter for you. Anyhow, for completeness (and for enjoyable), discover that you simply even have mentioned in your query that your rectangle is axis aligned. This data, summed to the truth that p1 is all the time contained in the rectangle, can increase a a lot sooner resolution. Not essentially simpler to code (sorry for calling it “simpler”), however rather more environment friendly in case you might have a number of segment-rectangle checks to make. The trick right here is the next. You first calculate the min_x, min_y, max_x and max_y of your rectangle. Then, you need to use the next perform to first test the place p2 is in relation to the rectangle after which simply do the line-seg checks if the exact sides of the rectangle (by no means having to test greater than 2, whereas within the worst case the primary resolution needed to test 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 level of the phase 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)); } //Whether it is on the left
else if (p2.y < min_y) //Whether it is on 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. whether it is on 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 level of the phase is at proper/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)); } //Whether it is on the proper
else if (p2.y < min_y) //Whether it is on 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. whether it is on 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 level of the phase is at prime/backside of the AABB
{
if (p2.y < min_y) return LSegsIntersectionPoint(p1, p2, new Vector2(min_x, min_y), new Vector2(max_x, min_y)); //Whether it is on the backside
if (p2.y > max_y) return LSegsIntersectionPoint(p1, p2, new Vector2(min_x, max_y), new Vector2(max_x, max_y)); //Whether it is on the prime
}
return null;
}
However discover: that second resolution is simply sooner when you can calculate the min_x, min_y, max_x and max_y of your rectangle beforehand. In any other case, you’ll have to calculate these contained in the perform and that can make it slower. For example you utilize the very same code because the second resolution, however simply doing that calculation of minutes and maxs of the rectangle inside the perform:
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 remainder of the the second model continues right here
To be able to profile that, I created a rectangle the place r1 = (-2,-2), r2 = (2,-2), r3 = (2,2) and r4 = (-2,2), p1 = (0,0) after which randomly positioned p2 a bunch of occasions, all the time have its X and Y coordinates between -4 and 4. Listed below are the outcomes, the place N is the variety of iterations of the simulation:
Discover that, as anticipated, model 2 is mostly a lot sooner to run. The one exception is for N<=1000, when it’s roughly the identical factor. For better variety of iterations, nevertheless, it turns into a lot sooner. However as I’ve pointed, that is solely the case if the minutes and maxs of the rectangle are calculated beforehand, as a result of in the event that they must be calculated inside the perform (i.e. v03), then it turns into a lot slower.
[ad_2]
