∩ Segment / Polygon

Intersection as fast as possible!

Presentation

This little code allows you to see the function for calculating the intersection of a segment with a polygon that I use in the game.
Lua being a rather slow language, it is necessary to limit as much as possible the accesses to the tables and the calculations. The version offered here is the fastest I have managed to code. If I managed to optimize this code, I will come and update this Snippet.

To maximize performance, I repeated the first point at the end of the polygon. This allows me to save a little more time by limiting the tests and the accesses to the "shape" array, on the other hand this modification no longer makes it possible to use the display.newPolygon () method of Solar2D which will not work correctly with a polygon having one point too many!

This function is able to calculate a thousand segment / polygon intersections at 60 FPS on my reference phone, namely a Samsung Galaxy J3 (2017 version).

--  we start by defining some polygons!

local tShape = {
{38, 188, 29, 180, 23, 179, 14, 181, 23, 217, 29, 216, 36, 211, 41, 198, 38, 188},
{236, 84, 235, 82, 213, 83, 223, 102, 235, 96, 237, 89, 236, 84},
{163, 111, 164, 124, 175, 126, 181, 119, 181, 117, 163, 111},
{63, 148, 63, 147, 47, 136, 38, 144, 58, 159, 62, 155, 63, 152, 63, 150, 63, 149, 63, 148},
{108, 55, 107, 54, 102, 51, 96, 53, 92, 58, 92, 59, 96, 67, 103, 69, 110, 60, 108, 55},
{171, 202, 169, 200, 165, 201, 163, 202, 163, 202, 162, 204, 162, 206, 162, 206, 162, 206, 164, 209, 172, 205, 171, 202},
{366, 104, 361, 94, 357, 91, 356, 90, 351, 89, 347, 89, 337, 114, 339, 117, 342, 119, 357, 119, 366, 105, 366, 104},
{144, 108, 117, 114, 114, 116, 102, 130, 98, 148, 106, 172, 129, 187, 173, 167, 178, 148, 144, 108},
{68, 198, 18, 192, 16, 211, 37, 232, 39, 232, 69, 208, 69, 208, 69, 205, 68, 198},
{131, 276, 118, 298, 124, 315, 150, 323, 163, 315, 170, 298, 131, 276},
{386, 261, 385, 260, 366, 252, 324, 280, 327, 310, 328, 312, 388, 319, 400, 291, 386, 261},
{216, 108, 145, 91, 140, 106, 160, 145, 171, 148, 216, 116, 216, 111, 216, 108},
{339, 41, 339, 40, 332, 32, 331, 31, 285, 45, 283, 59, 297, 80, 330, 80, 343, 55, 339, 41},
{190, 135, 171, 139, 168, 154, 171, 160, 190, 164, 199, 150, 190, 135},
{329, 270, 294, 236, 251, 263, 329, 276, 329, 270},
{47, 130, 42, 128, 42, 128, 42, 128, 21, 163, 36, 169, 44, 167, 57, 149, 57, 148, 47, 130},
{69, 183, 67, 179, 57, 181, 57, 182, 57, 182, 57, 185, 63, 189, 69, 183, 69, 183},
{244, 42, 242, 40, 239, 38, 224, 37, 215, 41, 212, 44, 207, 54, 208, 66, 229, 80, 242, 76, 251, 58, 244, 42},
{53, 253, 52, 289, 78, 300, 102, 272, 53, 253},
{198, 246, 163, 253, 183, 265, 187, 264, 191, 261, 196, 255, 198, 247, 198, 246},
{70, 254, 68, 280, 75, 278, 81, 267, 70, 254},
{91, 76, 68, 92, 65, 97, 64, 99, 68, 137, 81, 150, 125, 147, 132, 141, 141, 115, 91, 76},
{273, 216, 279, 225, 316, 215, 317, 207, 273, 216},
{260, 131, 247, 123, 240, 124, 235, 127, 237, 152, 242, 155, 254, 153, 260, 146, 260, 146, 262, 139, 260, 131},
{265, 105, 264, 104, 262, 102, 246, 99, 238, 108, 237, 115, 245, 126, 260, 126, 262, 124, 267, 117, 267, 113, 265, 105},
{420, 85, 408, 76, 391, 73, 370, 90, 369, 91, 382, 127, 386, 129, 404, 130, 425, 105, 425, 102, 420, 85},
{375, 137, 372, 136, 344, 177, 389, 160, 375, 137},
{87, 265, 74, 264, 69, 266, 68, 267, 66, 269, 63, 287, 64, 287, 89, 294, 93, 290, 93, 289, 96, 280, 87, 265},
{179, 242, 121, 243, 119, 270, 159, 290, 173, 282, 182, 264, 183, 258, 179, 242},
{97, 36, 91, 30, 90, 30, 80, 28, 73, 32, 70, 35, 67, 50, 68, 53, 75, 60, 100, 45, 97, 36}
}

function linePolygonIntersection(frx, fry, tox, toy, shape) -- the function takes as input the coordinates of the segment and a polyogon
local s
local sax, say, sbx, sby
local dx1, dy1
dx1, dy1 = tox - frx, toy - fry -- dx1 and dy1 will remain constant for all the polygon

sbx, sby = shape[1], shape[2] -- (sbx, syb) coordinates of the previous point

local nbPoints = #shape -- number of points
for s = 3, nbPoints, 2 do -- we iterate over all the segment
sax, say = sbx, sby -- (sax, sab) origin of the polygon side
sbx, sby = shape[s], shape[s + 1] -- (sbx, syb) destination of the polygon side

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

c1 = dy1 * (sax - tox) - dx1 * (say - toy) -- If c1 <0 then we go "to the right" of the segment
if c1 >= 0 then -- We immediately exit the following calculations are useless
c2 = dx1 * (sby - fry) - dy1 * (sbx - frx) -- If c2 <0 then we go "to the left" of the segment
if c2 >= 0 then -- We immediately exit the following calculations are useless
dx2 = sbx - sax -- We now know that the line intersects the side,
dy2 = sby - say -- But we have to make sure that the SEGMENT cuts the side
c3 = dy2 * (tox - sbx) - dx2 * (toy - sby) -- which is true if c3> = 0
if c3 >= 0 then
num = 1 / (-dx2 * dy1 + dx1 * dy2) -- it only remains to calculate the point of intersection
t = (dx2 * (fry - say) - dy2 * (frx - sax)) * num -- t should be between 0 and 1
if (t > 0) then
x = frx + (t * dx1)
y = fry + (t * dy1)
return {edge = s, t = t, x = x, y = y} -- we return the dimension, t, x, and y
end
end
end
end
end
return nil -- If the segment does not intersect the polygon, we return nil
end

local cntWidth = display.actualContentWidth -- physical screen width
local cntHeight = display.actualContentHeight -- physical screen height
local cntX = display.contentCenterX -- X and Y center of the virtual screen
local cntY = display.contentCenterY

local back = display.newRect(0, 0, cntWidth, cntHeight) -- we draw a rectangle to erase the background
back:setFillColor(0, 0, 0)
back.x = display.contentWidth * 0.5
back.y = display.contentHeight * 0.5

function drawPolygon(shape) -- polygon plot function.
for p = 1, #shape - 2, 2 do -- unable to use newPolygon because of the duplication of the first point.
display.newLine(shape[p], shape[p+1], shape[p+2], shape[p+3])
end
end

local s
for s = 1, #tShape do drawPolygon(tShape[s]) end -- We draw the polygons on the screen

local oCollisonGroup = display.newGroup() -- We create a group to display the collision information.

local function onObjectTouch(event) -- Every touch of the screen
while oCollisonGroup.numChildren > 0 do oCollisonGroup[1]:removeSelf() end -- We empty the collision group

if event.phase == "began" or event.phase == "moved" then
local ray = display.newLine(oCollisonGroup, cntX, cntY, event.x, event.y) -- we trace "the radius"
for s = 1, #tShape do -- and we test the collisions with all the polygons
local oResult = linePolygonIntersection(cntX, cntY, event.x, event.y, tShape[s])
if oResult then -- if there is a collision
local circle = display.newCircle(oCollisonGroup, oResult.x, oResult.y, 3)
circle:setFillColor(1, 0, 0) -- We draw a red circle
end
end
end
return true
end

back:addEventListener("touch", onObjectTouch) -- Setting up the Listener

Download

You can download the project archive running under Solar2D

Commentaires