/***************************************
Fake node and segment generation.
Part of the Routino routing software.
******************/ /******************
This file Copyright 2008-2015 Andrew M. Bishop
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU Affero General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Affero General Public License for more details.
You should have received a copy of the GNU Affero General Public License
along with this program. If not, see .
***************************************/
#include "types.h"
#include "nodes.h"
#include "segments.h"
#include "fakes.h"
/*+ The minimum distance along a segment from a node to insert a fake node. (in km). +*/
#define MINSEGMENT 0.005
/* Local variables (re-initialised by DeleteFakeNodes() function) */
/*+ A set of fake segments to allow start/finish in the middle of a segment. +*/
static Segment fake_segments[4*NWAYPOINTS+1];
/*+ A set of pointers to the real segments underlying the fake segments. +*/
static index_t real_segments[4*NWAYPOINTS+1];
/*+ A set of fake node latitudes and longitudes. +*/
static double fake_lon[NWAYPOINTS+1],fake_lat[NWAYPOINTS+1];
/*+ The previous waypoint. +*/
static int prevpoint=0;
/*++++++++++++++++++++++++++++++++++++++
Create a pair of fake segments corresponding to the given segment split in two
(and will create an extra two fake segments if adjacent waypoints are on the
same segment).
index_t CreateFakes Returns the fake node index (or a real one in special cases).
Nodes *nodes The set of nodes to use.
Segments *segments The set of segments to use.
int point Which of the waypoints this is.
Segment *segmentp The segment to split.
index_t node1 The first node at the end of this segment.
index_t node2 The second node at the end of this segment.
distance_t dist1 The distance to the first node.
distance_t dist2 The distance to the second node.
++++++++++++++++++++++++++++++++++++++*/
index_t CreateFakes(Nodes *nodes,Segments *segments,int point,Segment *segmentp,index_t node1,index_t node2,distance_t dist1,distance_t dist2)
{
index_t fakenode;
double lat1,lon1,lat2,lon2;
/* Initialise all the connecting segments to fake values */
fake_segments[4*point-4].node1=NO_NODE;
fake_segments[4*point-4].node2=NO_NODE;
fake_segments[4*point-3].node1=NO_NODE;
fake_segments[4*point-3].node2=NO_NODE;
fake_segments[4*point-2].node1=NO_NODE;
fake_segments[4*point-2].node2=NO_NODE;
fake_segments[4*point-1].node1=NO_NODE;
fake_segments[4*point-1].node2=NO_NODE;
/* Check if we are actually close enough to an existing node */
if(dist1<=km_to_distance(MINSEGMENT) && dist2>km_to_distance(MINSEGMENT))
{
prevpoint=point;
return(node1);
}
if(dist2<=km_to_distance(MINSEGMENT) && dist1>km_to_distance(MINSEGMENT))
{
prevpoint=point;
return(node2);
}
if(dist1<=km_to_distance(MINSEGMENT) && dist2<=km_to_distance(MINSEGMENT))
{
prevpoint=point;
if(dist13 && lat2<-3)
lat2+=2*M_PI;
else if(lat1<-3 && lat2>3)
lat1+=2*M_PI;
fake_lat[point]=lat1+(lat2-lat1)*(double)dist1/(double)(dist1+dist2); /* (dist1+dist2) must be > 0 */
fake_lon[point]=lon1+(lon2-lon1)*(double)dist1/(double)(dist1+dist2); /* (dist1+dist2) must be > 0 */
if(fake_lat[point]>M_PI) fake_lat[point]-=2*M_PI;
/*
* node1 fakenode node2
* #----------*----------------------------# real_segments[4*point-{4,3}]
*
* #----------* fake_segments[4*point-4]
* *----------------------------# fake_segments[4*point-3]
*
*
* node1 fakenode[prevpoint] node2
* #----------*------------------%---------# real_segments[4*prevpoint-{4,3,1}], real_segments[4*point-{4,3,2}]
* fakenode[point]
* #----------* fake_segments[4*prevpoint-4]
* *----------------------------# fake_segments[4*prevpoint-3]
* *------------------% fake_segments[4*prevpoint-1]
* #-----------------------------% fake_segments[4*point-4]
* %---------# fake_segments[4*point-3]
* *------------------% fake_segments[4*point-2]
*/
/* Create the first fake segment */
fake_segments[4*point-4]=*segmentp;
fake_segments[4*point-4].node2=fakenode;
fake_segments[4*point-4].distance=DISTANCE(dist1)|DISTFLAG(segmentp->distance);
real_segments[4*point-4]=IndexSegment(segments,segmentp);
/* Create the second fake segment */
fake_segments[4*point-3]=*segmentp;
fake_segments[4*point-3].node1=fakenode;
fake_segments[4*point-3].distance=DISTANCE(dist2)|DISTFLAG(segmentp->distance);
real_segments[4*point-3]=IndexSegment(segments,segmentp);
/* Create a third fake segment to join adjacent points if both are fake and on the same real segment */
if(prevpoint>0 && fake_segments[4*prevpoint-4].node1==node1 && fake_segments[4*prevpoint-3].node2==node2)
{
if(DISTANCE(dist1)>DISTANCE(fake_segments[4*prevpoint-4].distance)) /* point is further from node1 than prevpoint */
{
fake_segments[4*point-2]=fake_segments[4*prevpoint-3];
fake_segments[4*point-2].node2=fakenode;
fake_segments[4*point-2].distance=(DISTANCE(dist1)-DISTANCE(fake_segments[4*prevpoint-4].distance))|DISTFLAG(segmentp->distance);
}
else
{
fake_segments[4*point-2]=fake_segments[4*prevpoint-4];
fake_segments[4*point-2].node1=fakenode;
fake_segments[4*point-2].distance=(DISTANCE(fake_segments[4*prevpoint-4].distance)-DISTANCE(dist1))|DISTFLAG(segmentp->distance);
}
real_segments[4*point-2]=IndexSegment(segments,segmentp);
fake_segments[4*prevpoint-1]=fake_segments[4*point-2];
real_segments[4*prevpoint-1]=real_segments[4*point-2];
}
/* Return the fake node */
prevpoint=point;
return(fakenode);
}
/*++++++++++++++++++++++++++++++++++++++
Create a fake segment connecting a node to itself.
index_t CreateFakeNullSegment Returns the index of a fake segment.
Segments *segments The list of segments to use.
index_t node The node that is to be linked.
index_t segment The segment that is to be emulated.
int point The waypoint number.
++++++++++++++++++++++++++++++++++++++*/
index_t CreateFakeNullSegment(Segments *segments,index_t node,index_t segment,int point)
{
Segment *segmentp=LookupSegment(segments,segment,1);
fake_segments[4*point-2].node1=node;
fake_segments[4*point-2].node2=node;
fake_segments[4*point-2].way=segmentp->way;
fake_segments[4*point-2].distance=0;
return(4*point-2+SEGMENT_FAKE);
}
/*++++++++++++++++++++++++++++++++++++++
Re-initialise the fake node data storage.
++++++++++++++++++++++++++++++++++++++*/
void DeleteFakeNodes(void)
{
unsigned int i;
for(i=0;i