Advice on raytracing algorithm needed

1
votes

I have a grid that shows the world and its coastlines. An excerpt from the area around the UK is shown here Coastline grid around UK

From an arbitrary origin point anywhere in the ocean, I want to find those coastline points that are in line of sight of the origin without having to cross another coastline point. For example, if the origin is on the west side of the UK, I would expect to get many coastline points of western Ireland and western UK but not from Denmark as it is "covered" by the UK.

I need advice on a fast algorithm that can "shoot out" rays and detect where those rays cross the first coastline (coastline map is available in binary format).

Alternatively, I could imagine to move along all coastline pixels, build the connecting line between the origin and the coastline point and check if there is no other coastline point on the connecting line. Does any algorithm comes to mind that could accomplish this check of coastline crossing efficiently?

I realize this question is a shot in the blue but maybe there is someone smart who has knowledge in this area. Any help is much appreciated.

1
pythonpython-2.7numpyscipyraytracing
Maybe you should post this question on cs.stackexchange.com – Ibraim Ganiev
If you take this answer and store all edges in an efficient way (e.g. divide the map into a grid and for each box store the edges in(tersecting) it), you can check which boxes the ray enters, and which of the segments in that box it intersects. If you start from the origin of the ray you can simply check the boxes it passes through in order (you might need to check which segment is nearest the origin of the ray if there are multiple intersections in the same box). – Sam van Herwaarden
When you say that the coastline is stored as a "binary format", do you mean that it's stored as a raster image? (i.e. a 2-D array of pixels) It's more common to store coastlines as vector images (lists of line segments). The algorithm will vary somewhat (and it's accuracy as well) depending on the answer. – Gretchen
Hi Sam and Anna, thanks for your comments. The "boxing" idea sounds interesting and as if it would increase efficiency. I will give that some more thought. Anna, by binary format, I meant that I have a 2-D array of pixels with value 1 (=shoreline) and 0 (=no shoreline). I am curious to hear what you think. – user1984653
Can you specify what do you mean by "fast" and on what hardware? There are multiple approaches possible that differ by both speed and complexity, but there is no point in creating an overly complicated solution if something basic will do. Also, what is the resolution of your map? – Miloslaw Smyk

1 Answers

1
votes

The simplest approach is to use DDA algorithm to walk pixels from the point of interest towards points on image edges. Assuming a stop on a first hit, for an 5000x10000 map this results in several million iterations of a very simple loop.

If this is too much computation, you could use one of space partitioning schemes (e.g. quad tree, uniform grid, BSP tree) to skip over large empty areas.