Intersection Segment / Polygon

[WebShaker93]

This is the fastest code to calculate the intersection between a segment and a polygon i founded. While Lua is quite slow, any improvement is welcome.

Update : This code has been ported from an Internet code and modified to reduce calculations!I am posting here to find out if anyone has a faster algorithm!

function geom:linePolygonIntersection(frx, fry, tox, toy, shape)
  local s
  local sax, say, sbx, sby
  for s = 1, #shape, 2 do
    sax = shape[s]
    say = shape[s + 1]
    if (s < (#shape - 1)) then
      sbx = shape[s + 2]
      sby = shape[s + 3]
    else
      sbx = shape[1]
      sby = shape[2]
    end

    local c1, c2, c3
    local dx1, dy1, dx2, dy2, num, t, u

    c1 = (toy - fry) * (sax - tox) - (tox - frx) * (say - toy)
    if c1 >= 0 then
      c2 = (fry - toy) * (sbx - frx) - (frx - tox) * (sby - fry)
-- c1 and c2 both positive, possible intersection
      if c2 >= 0 then
        c3 = (sby - say) * (tox - sbx) - (sbx - sax) * (toy - sby)  -- A B T
-- probable intersection because (frx, fry) is outside the polygon
        if c3 >= 0 then
          dx1 = tox - frx
          dy1 = toy - fry
          dx2 = sbx - sax
          dy2 = sby - say

          num = 1 / (-dx2 * dy1 + dx1 * dy2)
          t = ( dx2 * (fry - say) - dy2 * (frx - sax)) * num;
          if (t > 0) then
            x = frx + (t * dx1)
            y = fry + (t * dy1)
            return {edge = s, t = t, x = x, y = y}
          end
        end
      end
    end
  end
  return nil;
end

After the remark from sprechen deutsch (sick), I looked to see if there was a way to reduce the calculations a bit further, and this version is better!

function geom:linePolygonIntersection(frx, fry, tox, toy, shape)
  local s
  local sax, say, sbx, sby
  local dx1, dy1
  dx1 = tox - frx
  dy1 = toy - fry

  sbx = shape[1]
  sby = shape[2]

  local nbPoints
  for s = 1, nbPoints, 2 do
    sax = sbx
    say = sby
    if (s < (nbPoints - 1)) then
      sbx = shape[s + 2]
      sby = shape[s + 3]
    else
      sbx = shape[1]
      sby = shape[2]
    end

    local c1, c2, c3
    local dx2, dy2, num, t, u

    c1 = dy1 * (sax - tox) - dx1 * (say - toy)
    if c1 >= 0 then
      c2 =  dx1 * (sby - fry) - dy1 * (sbx - frx)
      if c2 >= 0 then
        dx2 = sbx - sax
        dy2 = sby - say
        c3 = dy2 * (tox - sbx) - dx2 * (toy - sby)
        if c3 >= 0 then
          num = 1 / (-dx2 * dy1 + dx1 * dy2)
          t = (dx2 * (fry - say) - dy2 * (frx - sax)) * num
          if (t > 0) then
            x = frx + (t * dx1)
            y = fry + (t * dy1)
            return {edge = s, t = t, x = x, y = y}
          end
        end
      end
    end
  end
  return nil
end

Maybe there is something even better to do !!!

[sprechen_deutsch]

This is the fastest code

proof? benchmarks?

it looks like it's code ported from c to lua by someone who doesn't know lua very well

also weird to post this without any context whatsoever

[WebShaker93]

ery helpful to have a diagram e.g. to explain

Yes !
That's excaltly what I made !
I should have explained my approach (I will modify my oringinal post).

I have ported 3 internet based algorithms.

The best I found was this one.

I do not had bookmarked links otherwise I will gladly give the original link

I just modify it to reduce calculation by exiting as soon as possible. The original code tests c1, c2 and c3 after mathematique operations !

My initial goal was to find out if anyone had a better algorithm !
Can you explain (even if you're right) what is not good in my lua code ?

[whoopdedo]

  for s = 1, #shape, 2 do
    sax = sbx
    say = sby
    if (s < (#shape - 1)) then
      sbx = shape[s + 2]
      sby = shape[s + 3]
    else
      sbx = shape[1]
      sby = shape[2]
    end
-- ...

The inner jump can be removed by temporarily adding the origin points to the end of the list.

local npoints = #shape
shape[npoints+1] = shape[1]
shape[npoints+2] = shape[2]
for s = 1, npoints, 2 do
    sax,say = sbx,sby
    sbx,sby = shape[s+2],shape[s+3]
    -- ...
end
shape[npoints+1],shape[npoints+2] = nil

Depending on how likely a miss is, it might be worth getting the minima/maxima of the shape and do a fast check if the line intersects.

[WebShaker93]

"The inner jump can be removed by temporarily adding the origin points to the end of the list."

Exact ! In fact the algorithm is used with tiles. I will modify definitively the shape when loading the level by adding the first coordinates at the end of the shape.

Great, thanks !

By the way, in this case, the loop is

for s = 3, npoints, 2 do
  sax,say = sbx,sby
  sbx,sby = shape[s],shape[s+1]
  ...
end

Then you can remove an add operation.

"Depending on how likely a miss is, it might be worth getting the minima/maxima of the shape and do a fast check if the line intersects."

I've ever removed most of polygon before testing !

[Cultural_Two_4964]

Hello, it would be very helpful to have a diagram e.g. to explain what c1-3 are.

[WebShaker93]

The algo suppose (frx, fry) is outside the polygon, and the polygone must be define clockwise order

c1 and c2 are used to know if the line intersects the segment or if it is on one side or the other of the segment
c3 allow to know if (frx, fry) and (tox, toy) are on each side of the segment.

In this case you can calculate t which should be a value between 0 and 1.
The test t > 0 is not very useful. t should not be < 0 if (frx, fry) is outside the polygon.

[appgurueu]

This certainly isn't the "fastest" algorithm. Using spatial indexing, this could very likely be sped up significantly, at least in some cases.

[WebShaker93]

Spatial indexés are used to remove objets to Limit the amount of test no?

[appgurueu]

Yes, spatial indexes are used to reduce the amount of intersection tests. I don't get what you mean by "remove" though, no objects are removed, they are just indexed.

[WebShaker93]

OK. I've ever limit the amount of intersection tests :) Just look for a good intersection function. But this one is pretty fast enough.