patternMinor
Finding the nearest polygon
Viewed 0 times
nearestthepolygonfinding
Problem
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:
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;
// ver
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:
- Entity: performs a loop through ALL polygons.
- Polygon Loop: loops through ALL vertices of the polygon in the current iteration.
- 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.
- 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.
- 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;
// ver
Solution
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.
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.
- calculate distance to each polygon surrounding circle and eliminate all polygons which are too far away to be a match
- Entity: performs a loop through all not eleminated polygons.
- Polygon Loop: loops through ALL vertices of the polygon in the current iteration.
- 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.
- 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.
- 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.
Context
StackExchange Code Review Q#54598, answer score: 3
Revisions (0)
No revisions yet.