%% - alg: archangels delegate angels to install direction signs on a chart of roads, to allow people at each of the nodes to congregate at a single point on the chart, following the shortest paths. note: type of sign for destination point.
%% - Two signs may be needed at a point
%% (1. convert chart to graph)
%% 2a. find leg lengths
%% 2b. convert chart to directed chart
%% 3. test directed chart
%% 1. convert chart to graph
%% placesigns([[
%% find_segment_lengths([[[1,3],[2,3]],[[2,3],[3,3]],[[2,3],[2,5]],[[2,5],
%% [3,5]],[[3,5],[3,3]],[[3,3],[3,1]],[[3,3],[4,3]],[[4,3],[4,2]],[[4,3],
%% [4,4]],[[4,4],[5,4]]],Chart).
%% Graph = [[[[1,3],[2,3]],1],...
find_segment_lengths( [], Chart, Chart ).
find_segment_lengths( [ Item | Items ] , Chart1 , Chart2 ) :-
Item = [Point1, Point2], Point1 = [X1, Y1], Point2 = [X2, Y2],
Delta_X is X2 - X1, Delta_Y is Y2 - Y1,
Delta_X_Squared is Delta_X ^ 2, Delta_Y_Squared is Delta_Y ^ 2,
Segment_Length_Squared is Delta_X_Squared + Delta_Y_Squared,
Segment_Length is sqrt( Segment_Length_Squared ),
append( Item, [ Segment_Length ], New_Item),
append( Chart1 , [ New_Item ] , Chart3 ),
find_segment_lengths( Items, Chart3, Chart2 ).
%% follow a path and add signs point back towards the end point
%% if a path connects to another path back to the end point, point to the shortest path
%% the paths done from the point are re-checked
%% if the end-point is found again, the paths are re-checked.
%% output path for each person
%% chart_to_directed_chart(Origin,
%% Origin - point the people must arrive at
%% chart_to_directed_chart([1,3],[[[[1,3],[2,3]],1]],[],[[[2,3],[1,3]]]).
chart_to_directed_chart(_,[],Chart,Chart).
chart_to_directed_chart(End_Point,Items,Chart1,Chart2) :-