Select Page

Objects distribution within concave polygon

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?

#### Attached Thumbnails

Source: Objects distribution within concave polygon