[snippet]LineIntersectsCircle

[D4RK_G4ND4LF]

Checks if a line (or line segment) given by the points (x1, y1) and (x2, y2) intersects a circle with center (h, k) and radius r

library LineIntersectsCircle

function GetDistanceFromLineToPoint takes real x1, real y1, real x2, real y2, real h, real k returns real
    local real r
    local real distance = SquareRoot((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
    if distance <= 0.00 then
        //if points are the same the line would be a plane I guess
        //but it's more useful this way
        return SquareRoot((x1-h)*(x1-h)+(y1-k)*(y1-k))
    endif
    set r = (x2-x1)*(k-y1)-(h-x1)*(y2-y1)
    if r < 0.00 then
        return -r/distance
    endif
    return r/distance
endfunction

function IsLineIntersectingCircle takes real x1, real y1, real x2, real y2, real h, real k, real r returns boolean
    return GetDistanceFromLineToPoint(x1, y1, x2, y2, h, k) <= r
endfunction

endlibrary

 

[Anachron]

//WARNING! FUNCTION WILL NOT WORK WITH x1 == x2 AND y1 == y2 BECAUSE IT WILL DIVIDE BY ZERO!

Then catch the error and solve it?

 

[D4RK_G4ND4LF]

Then catch the error and solve it?

I think it is up to the user to make sure his input fits to the functions (you also can't use SquareRoot with negative values)
I am just warning that division by zero is not allowed in case the user did not pay attention
also for the functions with x/y-parameters I implemented such a check

the function with m and n as parameter is for speed reasons
for unitgroup filters the IsUnitOnLineFromTo would be much easier to use but it would calculate m and n multiple times
to get around this I want the user be able to pass m and n directly as a parameter
checking m every time it is passed to the function would cause unnecessary performance loss

anyway the unsimplified function is just to make it easier to understand how the equatations work and not for anything else
maybe it was unclear
I will clearify it
edit: done
and also moved the old functions down here to avoid confusion

Old functions

//This function will not work if x1 == x2 or y1 == y2 because it will divide by zero
//Its only purpose is to show where the equatations come from
//Use the functions above because they are optimized and safe
function Unsimplified takes real h, real k, real x1, real y1, real x2, real y2, real r returns boolean
    local real m1 = (y1-y2)/(x1-x2) //slope of line 1 through the given points
    local real m2 = -1/m1           //slope of line 2 perpendicular on the first line
    local real b1 = y1 - m1*x1      //y-intercept of line 1
    local real b2 = k - m2*h      //y-intercept of line 2
    local real x = (b2-b1)/(m1-m2)  //x-coordinate of intersection point of line 1 and 2
    local real y = m2*x + b2        //y-coordinate of intersection point of line 1 and 2
    return r*r >= (h-x)*(h-x) + (k-y)*(k-y)  //Check distance between intersection point and to-check point
endfunction

//Make sure that the slope m is not equal to zero so we don't divide by zero
function IsCircleIntersectingLineOld takes real h, real k, real m, real b, real r returns boolean
    local real x = (k + h/m - b)/(m + 1/m)
    set k = m*x + b - k
    return r*r >= (x-h)*(x-h) + k*k
endfunction

//this function automatically checks if the slope is valid
function IsCircleIntersectingLineSimpleOld takes real h, real k, real x1, real y1, real x2, real y2, real r returns boolean
    if x1 == x2 then
        return r*r >= (h-x1)*(h-x1)
    endif
    if y1 == y2 then
        return r*r >= (k-y1)*(k-y1)
    endif
    return IsCircleIntersectingLineOld(h, k, (y1-y2)/(x1-x2), y1 - (y1-y2)/(x1-x2)*x1, r)
endfunction

The old function might be faster if m and b stay constant (make sure to avoid division by zero).

If you port this code to C/C++ be aware of the fact that sin is a lot slower than +, -, *, / (60 to 130 times in my tests).

 

[Nestharus]

Uh... put the unsimplified forms above the thing as not a resource or submit them as a tutorial or something. You shouldn't have extra weirdness in your resource : P.

Also, you should only have IsPointOnLine and IsPointOnLineFrom >.<. The IsUnitOnLine could just as easily use IsPointOnLine, so it's virtually an extra function that'll probably never be used = ).

And darn... you beat me to it >.<... I was going to write this today or tomorrow, haha. Also... you should be able to handle the same coordinates.. if coordinates are the same, just return true, otherwise do all your math and return that >.>.... a person shouldn't have to check if their unknown coordinates are equal to each other before they use your function.

And I don't think some of the units in your picture are on the line (their x,y coordinates don't equal an x,y coord on the line) : P. If you wanted to do that sort of thing, do another script for it (intersections). DoesCircleIntersectLine, DoesRectangleIntersectLine, DoesLineIntersectLine? The units would use DoesCircleIntersectLine. It would also be nice if you did DoesEllipseIntersectLine and DoesSquareIntersectLine (square/circle for a little more optimal problems since circles would be used a lot for units and squares for buildings/towers).

You should also make a snippet GetLineSlope that converts x1,y1 x2,y2 into a slope and you should explain what m means in case someone doesn't know.

 

[azlier]

IT DISPLEASES ME.

Why is it not contained in a library?

 

[D4RK_G4ND4LF]

IT DISPLEASES ME.

Why is it not contained in a library?

isn't this a JASS section?
why does it have to be vJASS?

Uh... put the unsimplified forms above the thing as not a resource or submit them as a tutorial or something. You shouldn't have extra weirdness in your resource : P.

true

And darn... you beat me to it >.<... I was going to write this today or tomorrow, haha.

I'm sorry but somehow I knew you were going for this next

You should also make a snippet GetLineSlope that converts x1,y1 x2,y2 into a slope

well...imho unnecessary wrappers but if you say so...

 

[Nestharus]

What is this slope intercept stuff?

Your library needs to contain minimal functions specific to the library. As it stands now, it is cumbersome and just bleh...

I also talked to you about line widths. You need to have a line width of one, otherwise it's not a line is it? With a line width > 1, it turns into a rectangle, and we already have snippets for checking to see if a point is in a rectangle : P.

Well, I guess you could include width, but the width at that point is no longer a line is it? It also adds extra calculations that you normally wouldn't need.

You can do different sets of functions then:
IsPointOnLine
IsPointInRectangularLine

k?

This still needs lots of work.

Also LineFrom or w/e should be LineSegment, and really most people would be checking for LineSegments now wouldn't they? I guess the LineForm could be useful, but eh.

You need to split these functions up into different libraries too... don't have a huge library of line snippets, they're just little mathematical operations ; P.

 

[D4RK_G4ND4LF]

With a line width > 1, it turns into a rectangle, and we already have snippets for checking to see if a point is in a rectangle : P.

well in this case my submission is obsolete
edit: no it is not
a line is a rectangle with an infinite length

I will have to find some better name though
IsPointWithinRangeOfLineFromTo would describe it correctly but I am looking for something shorter

help from someone with awesome math-english-knowledge is greatly appreciated
edit: I'll go with the one Nestharus suggested in pm
thanks to you again

What is this slope intercept stuff?

Your library needs to contain minimal functions specific to the library. As it stands now, it is cumbersome and just bleh...

I probably got you wrong there
I'll delete it

Also LineFrom or w/e should be LineSegment, and really most people would be checking for LineSegments now wouldn't they? I guess the LineForm could be useful, but eh.

the cases I could imagine would use GroupEnumUnitsInRange and therefore would automatically choose a fitting segment

I also talked to you about line widths. You need to have a line width of one, otherwise it's not a line is it? With a line width > 1, it turns into a rectangle, and we already have snippets for checking to see if a point is in a rectangle : P.

also a line with a width of 1 could be checked much easier
the angle from point 1 to point 2 would be exactly the same as the angle from point1 to the target point and that case would be very unlikely to happen
even easier as Nestharus has proven below
even easier as Nestharus has proven in his snippet

 

[Nestharus]

edit
see you changed it to circle intersects line

I'll submit my little line snippet then. I think it's fine atm.

Mind if I submit this?

library IsPointOnLine

//checks to see if point px is on line [(lx1, ly1), (lx2, ly2)]
function IsPointOnLine takes real lx1, real ly1, real lx2, real ly2, real px, real py returns boolean
    return (lx1 == px and ly1 == py) or (lx2 == px and ly2 == py) or (lx2 != px and lx1 != px and (ly2-ly1)/(lx2-lx1) == (py-ly1)/(px-lx1))
endfunction

endlibrary

 

[Laiev]

funny

.

 

[Nestharus]

Looks pretty good, but your second function won't work right because it doesn't limit itself to the vector (might intersect at 15, 18 where the vector only goes to 3, 5)

Also

//
    function CircleIntersectsLine takes real px, real py, real m, real n, real r returns boolean
        local real x = (py + px/m - n)/(m + 1/m)
        local real y = m*x + n
        return r*r >= (x-px)*(x-px) + (y-py)*(y-py)
    endfunction

Could be

    function DoesCircleIntersectLine takes real h, real k, real m, real b, real r returns boolean
        local real x = (k + h/m - b)/(m + 1/m)-h
        local real y = m*x + b - k
        return r*r >= x*x + y*y
    endfunction

and

    function CircleIntersectsLineFromTo takes real px, real py, real x1, real y1, real x2, real y2, real r returns boolean
        //Make sure we won't divide by zero
        if x1 == x2 then
            return r*r >= (px-x1)*(px-x1)
        endif
        if y1 == y2 then
            return r*r >= (py-y1)*(py-y1)
        endif
        return CircleIntersectsLine(px, py, (y1-y2)/(x1-x2), y1 - (y1-y2)/(x1-x2)*x1, r)
    endfunction

Can be function DoesCircleIntersectVector takes real h, real k, real x1, real y1, real x2, real y2, real r returns boolean

To do it properly, you need to retrieve intersections for the line and circle and make sure one of them is between x1 and x2 of the vector.

function DoesCircleIntersectVector takes real h, real k, real x1, real y1, real x2, real y2, real r returns boolean
    local real x
    local real y
    local real m
    local real b
    
    if x1 == x2 then
        return r*r >= (h-x1)*(h-x1)
    elseif y1 == y2 then
        return r*r >= (k-y1)*(k-y1)
    endif
    
    if (x2 == x1) then
        return false
    endif
    
    set m = (y2-y1)/(x2-x1)
    set b = y1-m*x1
    
    set x = (k + h/m - b)/(m + 1/m)-h
    set y = m*x + b - k
    
    //the bounds below are wrong. Really need to retrieve both intersections and see if either are on the vector
    //this only checks one intersection. I'm tired, so figure the rest out on your own : P.
    return r*r >= x*x + y*y and ((x2 > x1 and x <= x2 and x >= x1) or (x >= x2 and x <= x1))
endfunction

 

[D4RK_G4ND4LF]

funny

Looks pretty good, but your second function won't work right because it doesn't limit itself to the vector (might intersect at 15, 18 where the vector only goes to 3, 5)

it's not line segment
but I'm working on it
edit: done

Also

//
    function CircleIntersectsLine takes real px, real py, real m, real n, real r returns boolean
        local real x = (py + px/m - n)/(m + 1/m)
        local real y = m*x + n
        return r*r >= (x-px)*(x-px) + (y-py)*(y-py)
    endfunction

Could be

    function DoesCircleIntersectLine takes real h, real k, real m, real b, real r returns boolean
        local real x = (k + h/m - b)/(m + 1/m)-h
        local real y = m*x + b - k
        return r*r >= x*x + y*y
    endfunction

you are right but y requires x and not x-h

and

    function CircleIntersectsLineFromTo takes real px, real py, real x1, real y1, real x2, real y2, real r returns boolean
        //Make sure we won't divide by zero
        if x1 == x2 then
            return r*r >= (px-x1)*(px-x1)
        endif
        if y1 == y2 then
            return r*r >= (py-y1)*(py-y1)
        endif
        return CircleIntersectsLine(px, py, (y1-y2)/(x1-x2), y1 - (y1-y2)/(x1-x2)*x1, r)
    endfunction

Can be function DoesCircleIntersectVector takes real h, real k, real x1, real y1, real x2, real y2, real r returns boolean

why h and k? that does not make any sense at all to me oO
who called it like that? (but I checked it and apparently this is quite popular so...)

 

[GhostWolf]

(1, 2) to (2, 1) is a SEGMENT, not a Vector.
A vector would be (1, 2).
You can't check if a point is inside a vector since a vector has no position.

On another note, you should probably first make simple classes such as Vector, Circle, AABB (Rect?), OBB, Line, Segment, and such.

 

[Nestharus]

The vector is the magnitude of the segment and can be represented by either the magnitude + an angle or the x,y components.

Also this is stupid (x1<=h and h<=x2) or (x1>=h and h>=x2) as it will always return true >.>.

Your bounds are still bad ; ).

 

[GhostWolf]

The vector is the magnitude of the segment and can be represented by either the magnitude + an angle or the x,y components.

No, that makes no sense.
You might mean a Point + a Vector.

 

[Nestharus]

Actually, I'm right in regards to that, but a vector also includes a direction, making me wrong ; P.

So these scripts do deal with line segments and not vectors.

Also, I see that your bounds are fine actually ;o.

was reading it as (x1<h<x2 or x2<h<x1) and (other stuff)

So that's why I was thinking, wth? : o.

Oh well, ; D.

 

[Bribe]

So is this ready to submit or what? Thread topic seems to bounce around a bit.

 

[Nestharus]

This portion doesn't fit

function GetDistanceFromLineToPoint takes real x1, real y1, real x2, real y2, real h, real k returns real
    local real r
    local real distance = SquareRoot((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
    if distance <= 0.00 then
        //if points are the same the line would be a plane I guess
        //but it's more useful this way
        return SquareRoot((x1-h)*(x1-h)+(y1-k)*(y1-k))
    endif
    set r = (x2-x1)*(k-y1)-(h-x1)*(y2-y1)
    if r < 0.00 then
        return -r/distance
    endif
    return r/distance
endfunction

But anyways, shouldn't this be moved to small code snippets? ;o

 

[Bribe]

What do you mean it doesn't fit? Just merge the two functions?

 

[Nestharus]

No, I mean it doesn't fit with the lib ;P, but I guess it doesn't matter ;D.

 

[Bribe]

This should be re-submitted to Small Code Snippets.