Jump to content
  • Advertisement
Sign in to follow this  
Oscar Dalvit

CENTRIC ALGORITHM

This topic is 698 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

Hi guys,

 

I need an help to find an algorithm or a solution for this problem... I really hope to find here the "genius" able to solve my problem.

 

1. We are developing a billboard made with many spaces of different sizes, for example 10x100 pixel 10x10 pixel 20x30 pixel and so on ...

 

2. In the center of the billboard we have a fixed space of 100x100 pixel, it represents the center of the billboard and has a GEOLOCATION RECORD 

 

3. Each SPACE has a GEOLOCATION record stored 

 

4. We should organize these spaces all one next one starting from the center in a centric order. The priority is set by calculating the distance in REAL geolocation of each space from the coordinates of the space in the center. 

I hope is clear the scenario :) 

we are looking for someone that has a great idea to solve the problem

 

PS: the spaces to manage are 10k, and the algorithm should be performing because wea are running on Android and IOS 

 

BYE
 

Share this post


Link to post
Share on other sites
Advertisement

I hope is clear the scenario :)

 

I'm afraid I struggled to understand the problem you're trying to solve.

 

My best guess is that it sounds a lot like you're packing textures into an atlas which is a bin packing problem: https://en.wikipedia.org/wiki/Bin_packing_problem this is nigh on impossible to solve optimally. The good news is that there are plenty of ways to get adequate results pretty quickly, there might be some good leads here: http://gamedev.stackexchange.com/questions/2829/texture-packing-algorithm

Share this post


Link to post
Share on other sites
The only thing I found when I searched for "Centric ordering" seemed to indicate that you try to place each subsequent item in the closest free space to the center. Is that correct?

It seems like a bin/texture packing problem, with the added constraint of putting things close to the center (which seems like it would make the problem even more difficult).

If you have a specific order of "spaces" (rectangles) and you need to place them in that order, you will probably have a lot of problems with gaps that you can't put any other rectangles in later on (i.e. fragmentation) Edited by Nypyren

Share this post


Link to post
Share on other sites

Hi Nypyren,

 

yeah the Centrinc Ordering is perfectly what I'm trying to do.

 

Is not so important if we have some gaps, but the most tricky part is to order the "squares" all around the center by priority (and priority is calculated on distance from the GEO of the CENTER SQUARE and the GEOLOCATION record of all the others squares... 

 

We should keep the CENTER SQUARE in the middle and organize all arround it the other squares... 

We have 10.000 squares of different dimensions to organize by this way... but I repeat is not super important to have some free gap between them if is not possible to fit them always perfectly... 

Remember the scenario is 10.000 squares, all different sizes 10x10 100x10 20x30  etc... all of them a GEOLOCATION RECORD. One of them we decide is the CENTER SQUARE... all other have a priority calculating by GEOLOCATION CENTER - GEOLOCATION OF SQUARE (and if is egual we add a random priority between same exactly results) and then we should fit all these squares all arround the center, with less spaces possible in a CENTRIC organization.

Share this post


Link to post
Share on other sites

I would proceed in two steps:

  • Arrange rectangle centers according to their geographical coordinates and according to an appropriate map projection, e.g. a Mercator projection cut at the opposite meridian of the "center square" (so that it ends up in the middle of the layout longitude-wise).
  • Shift rectangles horizontally and/or vertically to avoid overlap Rectangles aren't going to move far from their "natural" positions, except in places where they are too large for their density.

The second step is obviously the difficult one, with different possible heuristics; but I suspect you actually need to solve an easier problem than arranging 10k rectangles of arbitrary size and arbitrary geographical location:

  • If you add rectangles one by one to a well-behaved layout (initially containing the "center square" in the center) you might be able to constrain their location to suitable gaps for a given size (like placing fixed-size buildings in a typical grid-based RTS or tower defense game) or to constrain their size (touching neighbours without overlap) given an arbitrary location.
  • If you need to draw rectangles corresponding to a list of "geolocations" you might be able to simply shrink the ones that are too close to their neighbours. For example, you might build a list of all overlaps, then repeatedly select the two rectangles with the highest-area overlap, shrink or shift them a little, update overlap sizes, and repeat until everything fits.

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!