Circle - Segment intersection - Printable Version

Circle - Segment intersection - Printable Version

+- SA-MP Forums Archive (https://sampforum.blast.hk)
+-- Forum: SA-MP Scripting and Plugins (https://sampforum.blast.hk/forumdisplay.php?fid=8)
+--- Forum: Scripting Help (https://sampforum.blast.hk/forumdisplay.php?fid=12)
+--- Thread: Circle - Segment intersection (/showthread.php?tid=447689)

Circle - Segment intersection - PeppeAC - 01.07.2013

How to check if a circle of radius R and center (A, B) intersects a segment from P1(X1, Y1) to P2(X2, Y2)?

I know how to check if a circle intersect a straight line, but not a segment.

Re: Circle - Segment intersection - Antonio144 - 01.07.2013

pawn Код:

/*
pA,pB - line segments
pC - circle center
radius - well...radius 
*/
stock LineIntersectCircle(Float:pA[2], Float:pB[2], Float:pC[2], Float:radius)
{
    new Float: a = (pB[0]-pA[0])*(pB[0]-pA[0])+(pB[1]-pA[1])*(pB[1]-pA[1]);
    new Float: b = 2*((pB[0]-pA[0])*(pA[0]-pC[0])+(pB[1]-pA[1])*(pA[1]-pC[1]));
    new Float: c = pC[0]*pC[0]+pC[1]*pC[1]+pA[0]*pA[0]+pA[1]*pA[1]-2*(pC[0]*pA[0]+pC[1]*pA[1]) - radius*radius;
    new Float: konst = b*b-4*a*c;
    if(konst <= 0) return 0;
    else
    {
        new Float: e = floatsqroot(konst);
        new Float: u1 = (-b+e)/(2*a);
        new Float: u2 = (-b-e)/(2*a);
        if((u1>=0 || u1>=1) && (u2<=0 || u2<=1)) return 1;
    }
    return 0;
}

This should do it.

Re: Circle - Segment intersection - PeppeAC - 01.07.2013

Quote:

Originally Posted by Antonio144

pawn Код:

/*
pA,pB - line segments
pC - circle center
radius - well...radius 
*/
stock LineIntersectCircle(Float:pA[2], Float:pB[2], Float:pC[2], Float:radius)
{
    new Float: a = (pB[0]-pA[0])*(pB[0]-pA[0])+(pB[1]-pA[1])*(pB[1]-pA[1]);
    new Float: b = 2*((pB[0]-pA[0])*(pA[0]-pC[0])+(pB[1]-pA[1])*(pA[1]-pC[1]));
    new Float: c = pC[0]*pC[0]+pC[1]*pC[1]+pA[0]*pA[0]+pA[1]*pA[1]-2*(pC[0]*pA[0]+pC[1]*pA[1]) - radius*radius;
    new Float: konst = b*b-4*a*c;
    if(konst <= 0) return 0;
    else
    {
        new Float: e = floatsqroot(konst);
        new Float: u1 = (-b+e)/(2*a);
        new Float: u2 = (-b-e)/(2*a);
        if((u1>=0 || u1>=1) && (u2<=0 || u2<=1)) return 1;
    }
    return 0;
}

This should do it.

I think that
if(konst <= 0) return 0;
should be
if(konst < 0) return 0;
Because if konst = 0 there is one intersection.

And...
if((u1>=0 || u1>=1) && (u2<=0 || u2<=1)) return 1;
equals
if(u1 >= 1 && u2 <= 0) return 1;

Are you sure this is correct?

Re: Circle - Segment intersection - Antonio144 - 01.07.2013

Yes konst should be <0
And yes i made a mistake when i was copying code.
it should be
if((u1>=0 || u1<=1) && (u2>=0 || u2<=1))

I did some testing and this is what it returned
BC = 0
DE = 1
FG = 1
IH = 0
JK = 1
LM = 1

For IH konst is -0.745452 and it returned 0. That is because float can have only 7 digits and that is not enough for precise calculation. I don't know if there is double or long double implementation for pawn.

LM is not intersecting the circle but it is still returning 1. I need t work on that.

Re: Circle - Segment intersection - PeppeAC - 01.07.2013

It should be:
if(u1>=0 && u1<=1 && u2>=0 && u2<=1)

because:
if((u1>=0 || u1<=1) && (u2>=0 || u2<=1))
is always true.

However thanks, I think it should work

Re: Circle - Segment intersection - Antonio144 - 01.07.2013

Oh yeah, my bad.
I got the LM line segment to return right:

pawn Код:

stock LineIntersectCircle(Float:pA[2], Float:pB[2], Float:pC[2], Float:radius)
{
    new Float: a = (pB[0]-pA[0])*(pB[0]-pA[0])+(pB[1]-pA[1])*(pB[1]-pA[1]);
    new Float: b = 2*((pB[0]-pA[0])*(pA[0]-pC[0])+(pB[1]-pA[1])*(pA[1]-pC[1]));
    new Float: c = pC[0]*pC[0]+pC[1]*pC[1]+pA[0]*pA[0]+pA[1]*pA[1]-2*(pC[0]*pA[0]+pC[1]*pA[1]) - radius*radius;
    new Float: konst = b*b-4*a*c;
    printf("konst = %f",konst);
    if(konst < 0) return 0;
    else
    {
        new Float: e = floatsqroot(konst);
        new Float: u1 = (-b+e)/(2*a);
        new Float: u2 = (-b-e)/(2*a);
        if((u1<0 || u1>1) && (u2<0 || u2>1))
        {
            if((u1<0 && u2<0) || (u1>1 && u2>1)) return 1;
            else return 0;
        }
        else return 1;
    }
}

Also I made a function that returns (X,Y) where the line is entering and/or exiting the circle, if you need that.

Re: Circle - Segment intersection - PeppeAC - 01.07.2013

I think that:

Код:

stock LineIntersectCircle(Float:pA[2], Float:pB[2], Float:pC[2], Float:radius)
{
    new Float: a = (pB[0]-pA[0])*(pB[0]-pA[0])+(pB[1]-pA[1])*(pB[1]-pA[1]);
    new Float: b = 2*((pB[0]-pA[0])*(pA[0]-pC[0])+(pB[1]-pA[1])*(pA[1]-pC[1]));
    new Float: c = pC[0]*pC[0]+pC[1]*pC[1]+pA[0]*pA[0]+pA[1]*pA[1]-2*(pC[0]*pA[0]+pC[1]*pA[1]) - radius*radius;
    new Float: konst = b*b-4*a*c;
    if(konst >= 0)
    {
        new Float: e = floatsqroot(konst);
        new Float: u1 = (-b+e)/(2*a);
        new Float: u2 = (-b-e)/(2*a);
        if(0 <= u1 <= 1 && 0 <= u2 <= 1) return 1;
    }
    return 0;
}

Is the correct version.