PHP/MySQL tree that is inifinite

Question

I've got a tree-algorithm and database problem I'd like to have an answer to.

I've got a few areas, let's say 20. Each of these areas have sub-areas ~ 20 each. These parent areas are spread out on a map. Some of these parent areas are close to eachother.

The database looks like this: [area_id, title, parent_id] - Some has multiple children, there's a root node containing all areas. (The Adjacency List Model)

To make this in a picture I could do this:

The different areas as I said, can be close to eachother, (or far away). I'd like someway to tie let's say Area 1 and Area 5 together because I know they're close, and Area 1 is also close to Area 4. Now, here's the problem, let's say that Area 4 is also close to Area 5.

It would look like something like this:

Which makes it an infitite loop? because I want Area 1 to be close to Area 4, but also Area 4 is close to Area 1.

I'd like to do a search, where you can select "search nearby areas", so you select one area then you can search the nearby ones. I could use some tips, on how to solve this with a database and php.

I've been looking around on this forum for help but I don't really know the "name" of this problem, I'd be happy if someone could point me in the right direction or straight up help me out in thist thread.

Thanks guys, and if it's something else you need to know I'll try to answer as soon as possible.

Answer 1

For anything that is dealing with proximity, I would certainly take an approach of putting in either geospatial information (if these are true areas/regions) and then applying a radial search which can be done via any number of simple through to complex queries and calculations.

If these places are on the other hand fictional, it might be interesting to consider making a fake location - even if it a simple x,y coordinate system. This will allow you to perform radial searches again - which you can enlarge or shrink to your needs - or even simply order the results in ascending distance from site a to b.

Answer 2

To subdivide an area you need a rectangle that you can split along the axis. Look at kd-tree, r-tree, or quadtrees and spatial index. I can recommend you my php class Hilbert curve. It's a monster curve and fills completely the plane. You can find it at phpclasses.org.

Answer 3

I finally solved it using a kind of "neighboring" select statment.

I did this by creating another table which contains neighbor-relationships. That table looked like: [table_id, area_id, neighbor_area_id]

Here I added all the neighbors that are avaliable, with some INNER JOIN and select statment I managed to get out what I wanted, so a search can be done for all areas neighboring the selected one.

The sql-statment looked like this:

SELECT adds.title, categories.title, area.title
FROM adds
INNER JOIN categories ON categories.category_id = adds.category_id
INNER JOIN areas ON adds.area_id = areas.area_id
WHERE areas.area_id IN (SELECT area_neighbors.area_neighbor_id 
                        FROM area_neighbors 
                        WHERE area_id='25')
OR adds.area_id='25'

This would give me all adds in neighboring areas to area_id 25.

I cannot say if this is the smartest or best solution but it's one that works for me. Hope this helps someone! and thanks for all the replies!