• Advertisement
Sign in to follow this  

Objects distribution within concave polygon

This topic is 972 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So, first of all I am under NDA, so I need use analogical examples of my problem. Mainly I am looking for algorithms that can help me find results for my problem, so this is mostly theoretical question.
 
My input would be concave simple polygon (a list of points in cw or ccw order) that contains holes (stored as a list of list of points). Alternatively, I can triangulate that polygon and input this as a list of triangles. They mostly would be a simple shape where neighbouring segments are in right angle (I attached some example cases). Sometimes input might contain segments under irregular angles.
 
Having this region defined, I want to distribute objects within that shape. The number of objects doesn't need to be constant, but needs to be in given range (for instance at least 2 must be placed, but no more than 20). Each objects have some properties defined and influence each other.
 
Another problem is that they need to be placed in aesthetic way, to give you a real life idea I don't want to end up with something like this. But I might adjust the locations as a post process, so this is less important right now.
 
As the output I would need the list of points.
 
What I can provide for the algorithm are learning sets and evaluation method which says how good the output is.
 
Some examples - wireless signal enhancers placement in a building, monster placement in dungeon crawler game where each monster has different power, hp etc., chests/pick-ups of different value positioning in the game, maybe heat detectors (or any other detector) distribution in a room, surveillance cameras distribution in a room (so we want to place them in the way they cover the most space with least devices used).

 

The thing I already tried is an expanding grid of points, but it gave bad results. I also tried genetic algorithms, but they took to long and gave very random looking point distribution, the results were almost perfect in terms of numbers though. So I am looking for some kind of method that can adapt points to shape of the room and give as good results as GA. I was also thinking about neural networks, but the only ones I was working with were outputing true/false value and I don't know if they can create a list of points.

 

So does any other optimization agorithm/concept comes to your mind? I also didn't work with any fuzzy logics yet, I even have no idea how they work, I am just aware of their existance, is this something worth investigating in this case?

Share this post


Link to post
Share on other sites
Advertisement
If you use an optimization method like simulated annealing or genetic algorithms, you can divide the problem in two parts:
1) Generate candidate distributions (usually by modifying an existing distribution a bit)
2) Evaluate their utility (how happy you are with the result)

If you are not happy with what the results look like, try to define what you don't like about them very precisely, then add that as an extra term in the utility function.

The candidate generation can be used to speed up the process dramatically. For instance, if having objects on corners or on walls is rewarded by the utility function, you should try to place objects there with high probability.

Without knowing what the objects you are placing are, I can't think of anything more specific to tell you.

Share this post


Link to post
Share on other sites

Good distributions depend on the nature of the things you distribute; often you can define a simple geometric problem to solve.

For example, if you are placing 360° security cameras with unlimited range, you minimize the number of cameras to watch the whole room if you decompose the polygon into the minimum number of star-shaped pieces and you place a camera anywhere in what Wikipedia calls the "kernel" of each piece.

Distributing guardians in the same way would be good for detecting intruders, but you would end up with too few people (often only one) if the polygon has an easy shape and with no guarantees of balance if there are many obstacles; assigning an appropriate number of guardians to each entrance and simply placing them in front of it (e.g. strung along the curve that lies at a certain distance from the entrance, at appropriate distances from other walls and between each other) would be more effective.

Share this post


Link to post
Share on other sites

If you use an optimization method like simulated annealing or genetic algorithms, you can divide the problem in two parts:
1) Generate candidate distributions (usually by modifying an existing distribution a bit)
2) Evaluate their utility (how happy you are with the result)

If you are not happy with what the results look like, try to define what you don't like about them very precisely, then add that as an extra term in the utility function.

The candidate generation can be used to speed up the process dramatically. For instance, if having objects on corners or on walls is rewarded by the utility function, you should try to place objects there with high probability.

 

This sounds like a nice idea. So do you think something like combining GA with gradien descent would be a good way to do it?

I also found something like this:

 

The first part of the video (0:00 - 0:25) shows something I need. The points are distributed in optimum way and can be easily aligned afterwards (even manually). I have no idea what was used here, it looks like some kind of coverage optimization using independent inteligent agents?

Share this post


Link to post
Share on other sites
Once you define a utility function, there are several algorithms you can try. Gradient descent is fine if all the parameters you are trying to optimize are real numbers and the utility function is differentiable. If you are optimizing over some combinatorial data, you can try simulated annealing. And if you are optimizing over a set of computer programs, perhaps you can use genetic algorithms.

All of these algorithms have issues one needs to be aware of. For instance, gradient descent can get stuck in local minima. In my experience, finding the right utility function is more important than what algorithm you use to optimize. Slightly suboptimal solutions are generally acceptable.

Share this post


Link to post
Share on other sites

Finally I found something satisfying, Particle Swarm Optimisation was good for my problem. I used the same fitness function as I used for GA but PSO was much faster and gave a little bit better solutions.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement