Click here to Skip to main content
15,899,124 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Hello people.
It's nice to see so many people helping each other. This time I'm stuck and I need help. Or to be more precisely in search for a faster solution.
I'm not trying to reinvent GPS software or mapping system but I need to create a similar software in vb.net. It will work on a touch screen too.
The map is larger than screen size and obviously scrollable (7000px x 2000px).
When I click on it I get the MapX and MapY coordinates of that point on the map. I need to get from an .xml file the correspondent info. There are 600 POIs and every POI is a square (50px x 50px). My algorithm follows these steps:
- get every .xml node (POI) with coordX < MapX and add to a temporary list
- in this list keep only nodes with coordX + 50 > MapX
- new elimination criteria: CoordY < MapY
- last criteria: CoordY + 50 > MapY
At the end of the search there is only one node and I can read values from it: ID, information about place, other related info
Structure of .xml: (all places and coordinates are fictive)
<POIs>
<POI>
<CoordX>11</CoordX>
<CoordY>12</CoordY>
<ID>1</ID>
<Info>Museum</Info>
<Description>National Museum of ....</Description>
</POI>
<POI>
<CoordX>22</CoordX>
<CoordY>23</CoordY>
<ID>2</ID>
<Info>Police Station</Info>
<Description>13th Precinct</Description>
</POI>
.....
</POIs>

Is this the fastest method to find the POI ? Can I combine all 4 criterias to find in only one search the node ?
If the answer is yes can you give me an example of code ? Or point me to an existing thread ?
Posted
Updated 10-Nov-10 10:57am
v6

1 solution

Hi,

Your algorithm uses a temporary list which is modified. That is not very effective, it is much better to do the selection directly and never create any temporary list (see example attached below for an example).

If you have 600 POI's it is really noy that much. Given that you do not read the XML from disk eveytime (that is expensive!) and do not create intermediate lists it should be fast.

But one way of getting the solution to be faster is to group all POIs in a 2-dimensional array gruping the POIs on location so only a subset of them has to be searched.

Here is a quick and dirty implementation (not tested, and unfortunately in C# - but I don't do VB.NET :cool:). It should give you a hint of how to get faster implementation:

C#
public class POI {
    public int X { get; set; }
    public int Y { get; set; }
    public string Value { get; set; }
}
public class PoiStore {
    public const int MAP_SIZE_X = 7000;
    public const int MAP_SIZE_Y = 2000;
    public const int DELTA = 100;
    private readonly IList<POI>[,] _array = new IList<POI>[MAP_SIZE_X/DELTA, MAP_SIZE_Y/DELTA];
    /// <summary>
    /// Store in an array that collects all POIs in a DELTA sized grid.
    /// </summary>
    private void Store(POI poi) {
        var x = poi.X / DELTA;
        var y = poi.Y / DELTA;
        var list = _array[x, y];
        if (list == null) {
            list = new List<POI>();
            _array[x, y] = list;
        }
        list.Add(poi);
    }
    /// <summary>
    /// Read the XML and store in an array
    /// </summary>
    public void ReadXml(string url) {
        var doc = XDocument.Load(url);
        foreach (var uriElement in doc.Root.Elements("URI")) {
            Store(new POI {
                X = int.Parse(uriElement.Element("CoordX").Value),
                Y = int.Parse(uriElement.Element("CoordY").Value),
                Value = uriElement.Element("Value").Value
            });
        }
    }
    /// <summary>
    /// Find all POIs that are within the square given by <c>from</c> and <c>to</c>
    /// </summary>
    public IEnumerable<POI> Find(Point from, Point to) {
        for (var xIndex = from.X / DELTA; xIndex <= to.X / DELTA; xIndex++) {
            for (var yIndex = from.Y / DELTA; yIndex <= to.Y / DELTA; yIndex++) {
                var list = _array[xIndex,yIndex];
                if (list == null) continue;
                foreach (var poi in list) {
                    if (from.X <= poi.X && poi.X <= to.X && from.Y <= poi.Y && poi.Y <= to.Y) {
                        yield return poi;
                    }
                }
            }
        }
    }
}
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900