Finding the nearest polygon

Question

Finding the nearest polygon out of a list of polygons seems to be quite a challenge on performance, due to lack of optimization.

Consider the following image:

I'll give the concept behind this. The "purple" pointer under the mouse is an entity and each blue blob is a polygon. The red ring denotes the nearest polygon, while the pink line denotes the nearest line of that polygon.

Here is the system:

1. Entity: performs a loop through ALL polygons.
2. Polygon Loop: loops through ALL vertices of the polygon in the current iteration.
3. Vertex Loop: if the distance between the entity and the current vertex is lower than the distance between the entity and the previous vertex, save the current vertex and the ID of the polygon the vertex belongs to.
4. Once all loops are finished, take the nearest polygon/vertex and get the vertex of the polygon to the left and right of the nearest vertex.
5. Check the left and right vertices to see which is closest to the nearest vertex. Doing so, finds the nearest line of collision to the entity.

In short, I loop through all polygons and all vertexes of each polygon to find the nearest collision line of the nearest polygon to the entity. This allows me to handle terrain, collisions, gravity, etc.

The reason for this, is that the polygons can have any shape. Since this is the case, I have to dynamically find the nearest polygon based off of the vertex of each polygon to the entity. It's costly, but gets the job done...

I know this method is inefficient, but how could I go about making this system better? Or using an entirely different and existing system that is better?

The partial code below does not include finding the nearest line. That part I am not worried about as it's very easy/fast to do.

// srce -> list(1d-array) of polygon object-IDs;
// updated -> polygon vertex array of each polygon object;
// polygon -> current iteration in the srce list(1d-array);
// with( ... ) -> current polygon of the current iteration;
// vertex -> the current vertex in the iteration of vertices of the polygon;
// srcex and srcey -> entity x,y position;
// xvertex -> x-position of the current vertex in the iteration;
// yvertex -> x-position of the current vertex in the iteration;
// nearest* vars -> store the nearest vertex/polygon data;
// size -> total vertexes in the nearest polygon;
// NOTE: Each vertex takes up 2 indexes in the list(1d-array);

// Iterate through all polygon objects;
repeat( ds_list_size( srce ) ) {
   with( ds_list_find_value( srce , polygon ) ) {
      vertex = 0;

      // Iterate through the polygon's vertices;
      repeat( ds_list_size( updated ) div 2 ) {
         xvertex = ds_list_find_value( updated , vertex );
         yvertex = ds_list_find_value( updated , vertex + 1 );
         vertex_dist = point_distance( srcex , srcey , xvertex , yvertex );

         // Here we get the current nearest point IF it's closer than the previous;
         // Here -1 means there is current NO nearest vertex;
         if ( vertex_dist < nearest_dist || nearest_dist == -1 ) {
            // If this vertex is closer than the previous, store it's data;
            nearest_dist = vertex_dist;
            nearestx = xvertex;
            nearesty = yvertex;

            // This one is confusing: nearestv stores the INDEX of the vertex in...
            // ... the array of vertices, this is a reference point for the vertex;
            nearestv = vertex;

            nearest_polygon = id;
            size = ds_list_size( id );
         }

         vertex += 2;
      }
   }

   polygon += 1;
}

Answer 1

If shape and number of polygons do not change (or at least not often), I would add an extra step (the new first step) to your algorithm.

Calculate the center and radius of the smallest surrounding circle for each polygon. This way you can calculate in a minimal and maximal distance of all vertices from the given position in one run without iterating through them.

If the minimum distance for a polygon is greater than the maximum of an other polygon, no vertex of that polygon can be the nearest => we can ignore this polygon.

Than proceed like you did before.

1. calculate distance to each polygon surrounding circle and eliminate all polygons which are too far away to be a match
2. Entity: performs a loop through all not eleminated polygons.
3. Polygon Loop: loops through ALL vertices of the polygon in the current iteration.
4. Vertex Loop: if the distance between the entity and the current vertex is lower than the distance between the entity and the previous vertex, save the current vertex and the ID of the polygon the vertex belongs to.
5. Once all loops are finished, take the nearest polygon/vertex and get the vertex of the polygon to the left and right of the nearest vertex.
6. Check the left and right vertices to see which is closest to the nearest vertex. Doing so, finds the nearest line of collision to the entity.

Answer 2

• Try maintaining the polygon bounding rectangle (or even bounding circle). Getting the nearest of these is a LOT simpler and will reduce your possible polygons to consider.

  -- The reason you need this is to filter the possible polygons, not to decide on them. It doesn't matter if the shape is a good or bad fit; if it's a bad fit, then it'd just be included in more possible choices. But if you know (for example) that the nearest polygon is entirely within 100 units, there's no point even considering polygons where the closest point is greater than that.

• I have doubts that your nearest vertex approach will work - consider an 'infinitely long' horizontal line just below your point, that bends back to a vertex below that line - it'll pick up the line below the horizontal line since that has a nearby point.

• What you should consider doing instead is dropping a perpendicular offset to each line and selecting the shortest of these, and only after this fails to pick any consider vertices.
• It would also be better (if you can) to select all the polygon lines individually with a line bounding rectangle that are within (say) 10 units from your point, and test these. If there are none, increase the buffer distance and try again.

I've found Accelerated Search For the Nearest Line which may help.