#!/usr/bin/perl
#-------------------------------------------------------------------------------
#	$Id: reachable.pl,v 1.6 2023/01/27 13:57:54 wolf Exp $
#-------------------------------------------------------------------------------
#	https://www.netzwolf.info/code/geo/routing/reachable.html
#-------------------------------------------------------------------------------
#	This program is free software.
#	It comes without any warranty, to the extent permitted by applicable law.
#	You can redistribute it and/or modify it under the terms of the
#		"Do What The Fuck You Want To" Public License, Version 2,
#	as published by Sam Hocevar. See http://www.wtfpl.net/ for more details.
#-------------------------------------------------------------------------------

# ./reachable.pl {lat} {lon} {distance} <data.graph

use strict;
use utf8;

# process args

my $startLat = 1.0 * shift (@ARGV);
my $startLon = 1.0 * shift (@ARGV);
my $maxDist  = 1.0 * shift (@ARGV);

# graph

my %lon;
my %lat;

my %neighbours;		# node -> list of nodes
my %arcLength;		# snode,enode -> distance

#-----------------------------------------------------------------------
#	read graph
#-----------------------------------------------------------------------

warn "reading graph ...\n";

while (<>) {

	chomp;
	my @f = split /\t/;

	# node

	if ($f[0] eq 'node') {

		my $node = $f[1];
		my $lon  = $f[2];
		my $lat  = $f[3];

		$lon{$node} = $lon;
		$lat{$node} = $lat;
		next;
	}

	# arc

	if ($f[0] eq 'arc') {

		my $snode = $f[1];
		my $enode = $f[2];
		my $dist  = $f[3] || 0.001;	# must NOT be zero

		# ignode multiple arcs between two nodes

		next if defined $arcLength{$snode, $enode};

		# no neighbours yet -> create list

		unless ($neighbours{$snode}) {
			$neighbours{$snode} = [];
		}

		# store arc

		$arcLength{$snode, $enode} = $dist;
		push (@{$neighbours{$snode}}, $enode);

		next;
	}
}

#-----------------------------------------------------------------------
#	lookup start node
#-----------------------------------------------------------------------

warn "lookup start node ...\n";

my $bestDistance = 1e30;
my $startNode;
my $cos = cos ($startLat * 3.1415925 / 180.0);

foreach my $node (keys %lon) {

	# distance in degrees

	my $dLon = ($lon{$node}-$startLon) * $cos;
	my $dLat = ($lat{$node}-$startLat);

	# skip square root and scaling

	my $distance = $dLon*$dLon + $dLat*$dLat;

	next unless $distance < $bestDistance;

	# found better node

	$startNode = $node;
	$bestDistance = $distance;
}

die unless $startNode;

# start node found

warn "start node $startNode @ lat $lat{$startNode} lon $lon{$startNode}.\n";

print "start\t$lon{$startNode}\t$lat{$startNode}\n";

#-----------------------------------------------------------------------
#	reachability analysis
#-----------------------------------------------------------------------

my %bestDistance;	# distance from startnode to node

$bestDistance{$startNode} = 0;

my @nodesToBeAnalyzed = ($startNode);

# as long as nodes available

while (@nodesToBeAnalyzed) {

	# order by distance and get nearest, terminate if nearest outside limit

	@nodesToBeAnalyzed = sort {$bestDistance{$a} <=> $bestDistance{$b}} @nodesToBeAnalyzed;

	my $thisNode = $nodesToBeAnalyzed[0];
	my $thisDist = $bestDistance{$thisNode};

	last if $thisDist>$maxDist;

	shift (@nodesToBeAnalyzed);

	# check arcs

	my $hasOuterNeighbour = 0;

	foreach my $thatNode (@{$neighbours{$thisNode}}) {

		# dist to thatNode via thisNode

		my $viaDist = $thisDist + $arcLength{$thisNode, $thatNode};

		# reachable?

		if ($viaDist <= $maxDist) {
		
			print "arc\t$lon{$thisNode}\t$lat{$thisNode}\t$lon{$thatNode}\t$lat{$thatNode}\n";

		} else {

			print "noarc\t$lon{$thisNode}\t$lat{$thisNode}\t$lon{$thatNode}\t$lat{$thatNode}\n";
			$hasOuterNeighbour=1;
		}

		# already known distance of thatNode

		my $thatDist = $bestDistance{$thatNode};

		# if first touch of thatNode, add to todo list

		push (@nodesToBeAnalyzed, $thatNode) unless defined $thatDist;

		# remember best distance to thatNode

		$bestDistance{$thatNode} = $viaDist if !defined $thatDist || $viaDist<$thatDist;
	}

	print "inner\t$lon{$thisNode}\t$lat{$thisNode}\n" if $hasOuterNeighbour;
}

# list nodes on todo list

foreach my $thisNode (@nodesToBeAnalyzed) {

	print "outer\t$lon{$thisNode}\t$lat{$thisNode}\n";
}

exit 0;

#-------------------------------------------------------------------------------
#	$Id: reachable.pl,v 1.6 2023/01/27 13:57:54 wolf Exp $
#-------------------------------------------------------------------------------
