Which algorithm can efficiently find a set of poin

Question

Given a set of points s (a set of x,y coordinates) and a path that is made up of line segments joining a set of points l, describe an efficient algorithm that can be used to find a subset of points from s that are within the specified distance d of the path l.

A practical application of this may be to find a list of restaurants within 10 miles anywhere along a road trip path between cites.

For example, in the following diagram, the points in green would be included in the search results.

Solutions would be preferred in C#, but bonus points may be given for a SQL based approach :-)

Answer 1

1.) Store your points in a SQL Server 2008 table using the geometry datatype (or geography, if they're defined using coordinates of lat/long) Here's a script to create 100 sample points distributed randomly between (0,0) and (40,20):

DECLARE @Points table (
  id int,
  position geometry
  );

DECLARE @i int = 0, @x int, @y int;
WHILE (@i < 100)
BEGIN
  INSERT INTO @Points VALUES 
    (@i, geometry::Point(RAND() * 40, RAND() * 20, 0))
  SET @i = @i + 1;
END

2.) Define your line as a linestring, using the same datatype and SRID as for your points:

DECLARE @line geometry = 'LINESTRING(0 10, 10 15, 20 8, 40 10)';

3.) Use the STDistance() method in a predicate of a SELECT query against the points table. For example, to select all points within 5 units of the line:

SELECT * FROM @Points
WHERE @line.STDistance(position) < 5;

What's more, since the spatial methods of SQL Server are available in a redistributable dll (Microsoft.SqlServer.Types.dll - part of the SQL Server feature pack http://www.microsoft.com/downloads/en/details.aspx?FamilyID=ceb4346f-657f-4d28-83f5-aae0c5c83d52), you can use this same approach in either C# or direct in SQL Server.

Answer 2

I'm surprised no one has mentioned the A* alogirithm for this. It seems like a perfect fit. What am I missing here? If you're not familar with it, google and ye shall find =). (Yes, it does come from the gaming world...)

Answer 3

1. Define a "left road" and "right road": for each line segment of the original path, create a line segment d units to the "left" and one d units to the "right" of the segment.

2. Connect the left road and right road at the ends to make a polygon.

3. Apply a standard algorithm to determine which points of interest lie inside the polygon.

Answer 4

Tough homework assignment eh?

Perhaps a good start might be to look at breadth-first pathfinding algorithms- maybe something like a flood-fill approach would be useful for this?

Edit: So if it just looks like a homework assignment, maybe I can be more helpful...

I would first look to define a rectangle containing the line and the points that could be within it as that may enable us to get rid of a large number of points that are nowhere near our line.

For each point you could then create a square, representing the list of points within the radius of that point. This is again a way of reducing the number of elements to search.

Unfortunately I don't know enough geometry to be aware of a clever way of deciding whether a list of points fall inside or outside of a circle aside from simply calculating the distance between them and the centre of the circle through basic trig- I'm sure there is one. By using the aforementioned simple subdivision or some variant on it you should find that you can pre-emptively reduce the number of possible points that need to be searched through.

Also if you keep all your points to search in one list and remove the ones that are hits for the first circle, when it comes to measure subsequent shapes. I've used a brute-force version of this to do simple postcode-distance checks based on location data - that is documented in quite a few places online, but running it down a path would probably be quite computationally expensive.

This geometric approach would probably be better for a situation where you weren't doing a lot of repeated searches- if there are many in a row you might want to organise your ponts into a network so that you can use standard pathfinding on them. It would be worth doing some protoyping to see which is more efficient, but I would expect that if you were to create an appropriate network to represent your data you could then be more flexible in how you search it.

Answer 5

You should be able to accomplish this through vector math and trig though the exact methods escape me.

For each line segment calculate the values need to transform a point from world coordinates to local coordinates relative to the line segment (so any point run through the calculation would be relative to a coordinate system where the line segment is the x-axis)

For each point run the following checks:

1- If the point is within distance of either end point we know that it should be included. This is accomplished by a simple distance^2 <= (x2 - x1)^2 + (y2 - y1)^2 calculation between each endpoint and the target point.

2- Run the target point through the transformation. After the transformation if x >= 0 and x <= (length of the line segment) and |y| <= distance then the target point should be included otherwise it should be excluded.

My vector math is a bit rusty so I can't provide better code/examples sorry! But maybe my post will inspire someone else to write out the proper way to do it.

Answer 6

I'm not really sure if I understand the question correctly, but wouldn't Dijkstra's algorithm fit? It finds the shortest paths from a source node, and you can just abort after you reached you maximum distance and check which points from s have already been found. I'm not sure how well it plays with SQL though.