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 should add that the map is an array of dimensions 5000x10000 and the coastline is available in binary format (all pixel values are zero except for coastline pixels = 1).

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
    $\begingroup$ This is not ray tracing but ray casting. If you have polygons there is hit detection needed. If you are travelling along coastline it would be just go along polyline and check if you can bounce. The description is too vague to me. In CAD there are build "roadmaps" to avoid going near the object and to speed up things. If you can clarify the objective (what are you looking for) and how it should behave, and what you have tried that would improve this question. $\endgroup$ – Evil Sep 21 '15 at 14:26
  • $\begingroup$ If you have raster modified floodfill on BFS does the job, but this is not the fastest solution. $\endgroup$ – Evil Sep 21 '15 at 16:57
  • $\begingroup$ BSP Tree is standard in game development for the very similar situation where the walls of your floor plan determine what you can see from a spot. The walls become the space partitions. $\endgroup$ – cardiff space man Sep 22 '15 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.