LÖVE

Posted: **Fri Nov 11, 2022 9:01 pm**

Hello everyone

I present to you a small library that I made to facilitate the work on everything related to geometry.

I first started by using the library polygon from AlexarJING then I added functions to it, again and again until give what I present to you today. I didn't really know how to name it since it was no longer limited to polygons, it does a lot of various things, rather than listing everything I'll leave you a demo (which do not use all the features) and the GitHub link which lists all the functions that 'she owns.

I would have liked to put it in CC0 license (like the original one) but using a piece of library for the concave polygon partition in convex which was already in MIT license I had a doubt, so I put it in MIT too but you can do with it what you want in my opinion.

Have fun !

Posted: **Mon Nov 14, 2022 3:57 pm**

I added the functions 'isCircleInCircle', 'isCircleOutCircle', 'getDist', 'getAngle', 'keepMidVerts', 'getSegDist'.
Notably with the possibility of having the coordinates to replace the circle in collision with the second.

As well as a port of the simplify-js JavaScript module to reduce the number of vertices of a polygon. I also published the port alone on another GitHub repository. This new function in GeoMan is 'simplifyPoly'.

I post you the same demo with some additions. Can anyone tell me what you think, good or bad? I'm still a beginner so this would help.

Posted: **Sat Nov 19, 2022 1:39 am**

Good job. Does the detection work well (speedwise) for multiple objects?

Posted: **Sun Nov 20, 2022 3:27 pm**

"Small" update including

New functions:

New function isPolySelfIntersect to test if a polygon/polyline self intersects.
New function getPolyLength with the isLine parameter if we need to measure the length of a polyline or the perimeter of a polygon.
New function getMiddle to get the middle between two points.
New function isTrianglesIntersect for quick test of intersection between triangles.
New function isSegmentsOverlap to know if two segments overlap.
New function getPolysSharedEdges to get the indexes of shared edges, returns 'nil' if there is none.

New parameters:

New parameter entirely for isPolyInPoly which is false by default, to test if the polygon is completely or partially in the second.
New parameter getMostVerts for polybool to get the largest table or leave the choice of sorting to the user.
New parameter isCenter for the function setPolyPosition to determine if the new position given should be its center or at the top left.

Extras:

I made the name of some functions more relevant and made the order of some parameters more logical.
I corrected some defects in the lineCross.lua file.

I also added the execution time of the operations in the demos, at the bottom right.

Edit: Small optimizations and bug fixes plus add isPolysAdjacents to know if the two polygons given in parameter are adjacent. With the parameter getAdj you can retrieve the indexes and vertices of adjacent lines.

Posted: **Sun Nov 20, 2022 3:33 pm**

dusoft wrote: ↑Sat Nov 19, 2022 1:39 am Good job. Does the detection work well (speedwise) for multiple objects?

Thank you very much, otherwise it depends on the type of detection, which one are you talking about ?

I use most of these functions in my projects and haven't had any performance issues so far, if I have any I'll fix them. After that it depends a lot on what you will do with them and how you use them.

Posted: **Sun Nov 20, 2022 4:43 pm**

It is pretty good, you are attempting some complicated operations here like polygon unions and convex hull. Some of the algorithms could use work like your isPolySelfIntersect function. Please note that your code performs the same check twice i vs j and j vs i

Code: Select all

for i = 1, #edges do
  for j = 1, #edges do
    if i ~= j then
      -- test i and j

You only need to check each pair of edges once:

Code: Select all

for i = 1, #edges do
  for j = i + 1, #edges do
     -- test i and j

Your "isPointInTri" function could use what we call "early bailout" where the function returns as soon as one of the conditions fails. Here is your version:

Code: Select all

local function isPointInTri(x,y,verts)

    local x1, y1 = verts[1], verts[2]
    local x2, y2 = verts[3], verts[4]
    local x3, y3 = verts[5], verts[6]

    local d1 = sign(x,y, x1,y1, x2,y2)
    local d2 = sign(x,y, x2,y2, x3,y3)
    local d3 = sign(x,y, x3,y3, x1,y1)

    local neg = (d1 < 0) or (d2 < 0) or (d3 < 0)
    local pos = (d1 > 0) or (d2 > 0) or (d3 > 0)

    return not (neg and pos)

end

Early bailout version:

Code: Select all

function pointInTriangle(px, py, x1, y1, x2, y2, x3, y3)
  local ax, ay = x1 - px, y1 - py
  local bx, by = x2 - px, y2 - py
  local cx, cy = x3 - px, y3 - py
  local sab = ax*by - ay*bx < 0
  if sab ~= (bx*cy - by*cx < 0) then
    return false
  end
  return sab == (cx*ay - cy*ax < 0)
end

For further reading, check out my humble article at:
https://2dengine.com/?p=intersections#P ... e_triangle

Posted: **Sun Nov 20, 2022 5:32 pm**

ivan wrote: ↑Sun Nov 20, 2022 4:43 pm For further reading, check out my humble article at:
https://2dengine.com/?p=intersections#P ... e_triangle

Thank you very much for your details, I will study all that for, it's really nice !

ivan wrote: ↑Sun Nov 20, 2022 4:43 pm Please note that your code performs the same check twice i vs j and j vs i

After rereading it seems to me that it was normal, if the user wants to indicate a function there to filter if there are several intersections by segments in particular.

Posted: **Sun Nov 20, 2022 7:07 pm**

Bigfoot71 wrote: ↑Sun Nov 20, 2022 3:33 pm
dusoft wrote: ↑Sat Nov 19, 2022 1:39 am Good job. Does the detection work well (speedwise) for multiple objects?
Thank you very much, otherwise it depends on the type of detection, which one are you talking about ?

I use most of these functions in my projects and haven't had any performance issues so far, if I have any I'll fix them. After that it depends a lot on what you will do with them and how you use them.

I am curious about performance intersects detection for multiple polygons at once, e.g. one player body and tens/hundreds of enemies.

Posted: **Sun Nov 20, 2022 7:31 pm**

dusoft wrote: ↑Sun Nov 20, 2022 7:07 pm I am curious about performance intersects detection for multiple polygons at once, e.g. one player body and tens/hundreds of enemies.

Polygon vs polygon intersection is usually quite expensive.
That is why we have so called broadphase collision where a partitioning method is used to dismiss unlikely collision pairs.

Posted: **Sun Nov 20, 2022 9:58 pm**

dusoft wrote: ↑Sun Nov 20, 2022 7:07 pm I am curious about performance intersects detection for multiple polygons at once, e.g. one player body and tens/hundreds of enemies.

Here is a small demo that I just made very quickly. The player himself is represented by a polygon and there is an adjustable number of enemies (also represented by polygons).

I use the isPolyInPoly function for collisions, which can be quite greedy, and no optimization has been done as mentioned by Ivan, at each frame all enemies will test their collision with the player.

I tried up to a hundred and something enemies and was running at 60 FPS on an Intel Pentium J2900.

I would like to specify that the more the number of vertices will be, the more the time required will be high too, demo only contains hexagons, therefore 6 vertices per shape.

Edit: Here is a video where I went up to more than 1000 polygons and I kept the 60 FPS rather well, I myself am pleasantly surprised !

https://streamable.com/6mm3ud

LÖVE

GeoMan - Geometry library

GeoMan - Geometry library

Re: GeoMan - Geometry library

Re: GeoMan - Geometry library

Re: GeoMan - Geometry library

Re: GeoMan - Geometry library

Re: GeoMan - Geometry library

Re: GeoMan - Geometry library

Re: GeoMan - Geometry library

Re: GeoMan - Geometry library

Re: GeoMan - Geometry library