trunk/src/fakes.c

/***************************************
 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 <http://www.gnu.org/licenses/>.
 ***************************************/


#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(dist1<dist2)
       return(node1);
    else
       return(node2);
   }

 /* Create the fake node */

 fakenode=NODE_FAKE+point;

 GetLatLong(nodes,node1,NULL,&lat1,&lon1);
 GetLatLong(nodes,node2,NULL,&lat2,&lon2);

 if(lat1>3 && 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<sizeof(fake_segments)/sizeof(fake_segments[0]);i++)
   {
    fake_segments[i].node1=NO_NODE;
    fake_segments[i].node2=NO_NODE;
   }

 for(i=0;i<sizeof(real_segments)/sizeof(real_segments[0]);i++)
    real_segments[i]=NO_SEGMENT;

 prevpoint=0;
}


/*++++++++++++++++++++++++++++++++++++++
  Lookup the latitude and longitude of a fake node.

  index_t fakenode The fake node to lookup.

  double *latitude Returns the latitude

  double *longitude Returns the longitude.
  ++++++++++++++++++++++++++++++++++++++*/

void GetFakeLatLong(index_t fakenode, double *latitude,double *longitude)
{
 index_t whichnode=fakenode-NODE_FAKE;

 *latitude =fake_lat[whichnode];
 *longitude=fake_lon[whichnode];
}


/*++++++++++++++++++++++++++++++++++++++
  Finds the first fake segment associated to a fake node.

  Segment *FirstFakeSegment Returns a pointer to the first fake segment.

  index_t fakenode The fake node to lookup.
  ++++++++++++++++++++++++++++++++++++++*/

Segment *FirstFakeSegment(index_t fakenode)
{
 index_t whichnode=fakenode-NODE_FAKE;

 return(&fake_segments[4*whichnode-4]);
}


/*++++++++++++++++++++++++++++++++++++++
  Finds the next fake segment associated to a fake node.

  Segment *NextFakeSegment Returns a pointer to the next fake segment.

  Segment *fakesegmentp The first fake segment.

  index_t fakenode The node to lookup.
  ++++++++++++++++++++++++++++++++++++++*/

Segment *NextFakeSegment(Segment *fakesegmentp,index_t fakenode)
{
 index_t whichnode=fakenode-NODE_FAKE;

 if(fakesegmentp==&fake_segments[4*whichnode-4])
    return(&fake_segments[4*whichnode-3]);

 if(fakesegmentp==&fake_segments[4*whichnode-3] && fake_segments[4*whichnode-2].node1!=NO_NODE)
    return(&fake_segments[4*whichnode-2]);

 if(fakesegmentp==&fake_segments[4*whichnode-3] && fake_segments[4*whichnode-1].node1!=NO_NODE)
    return(&fake_segments[4*whichnode-1]);

 if(fakesegmentp==&fake_segments[4*whichnode-2] && fake_segments[4*whichnode-1].node1!=NO_NODE)
    return(&fake_segments[4*whichnode-1]);

 return(NULL);
}


/*++++++++++++++++++++++++++++++++++++++
  Finds the fake segment between a real node and a fake node.

  Segment *ExtraFakeSegment Returns a segment between the two specified nodes if it exists.

  index_t realnode The real node.

  index_t fakenode The fake node.
  ++++++++++++++++++++++++++++++++++++++*/

Segment *ExtraFakeSegment(index_t realnode,index_t fakenode)
{
 index_t whichnode=fakenode-NODE_FAKE;

 if(fake_segments[4*whichnode-4].node1==realnode || fake_segments[4*whichnode-4].node2==realnode)
    return(&fake_segments[4*whichnode-4]);

 if(fake_segments[4*whichnode-3].node1==realnode || fake_segments[4*whichnode-3].node2==realnode)
    return(&fake_segments[4*whichnode-3]);

 return(NULL);
}


/*++++++++++++++++++++++++++++++++++++++
  Lookup a fake segment given its index.

  Segment *LookupFakeSegment Returns a pointer to the fake segment.

  index_t fakesegment The index of the fake segment.
  ++++++++++++++++++++++++++++++++++++++*/

Segment *LookupFakeSegment(index_t fakesegment)
{
 index_t whichsegment=fakesegment-SEGMENT_FAKE;

 return(&fake_segments[whichsegment]);
}


/*++++++++++++++++++++++++++++++++++++++
  Find the fake index of a fake segment.

  index_t IndexFakeSegment Returns the fake segment.

  Segment *fakesegmentp The fake segment to look for.
  ++++++++++++++++++++++++++++++++++++++*/

index_t IndexFakeSegment(Segment *fakesegmentp)
{
 index_t whichsegment=(index_t)(fakesegmentp-&fake_segments[0]);

 return(whichsegment+SEGMENT_FAKE);
}


/*++++++++++++++++++++++++++++++++++++++
  Find the real segment underlying a fake segment.

  index_t IndexRealSegment Returns the index of the real segment.

  index_t fakesegment The index of the fake segment.
  ++++++++++++++++++++++++++++++++++++++*/

index_t IndexRealSegment(index_t fakesegment)
{
 index_t whichsegment=fakesegment-SEGMENT_FAKE;

 return(real_segments[whichsegment]);
}


/*++++++++++++++++++++++++++++++++++++++
  Determine if a route between two fake segments is valid or a U-turn.

  int IsFakeUTurn Returns true for a U-turn.

  index_t fakesegment1 The first fake segment.

  index_t fakesegment2 The second fake segment.
  ++++++++++++++++++++++++++++++++++++++*/

int IsFakeUTurn(index_t fakesegment1,index_t fakesegment2)
{
 index_t whichsegment1=fakesegment1-SEGMENT_FAKE;
 index_t whichsegment2=fakesegment2-SEGMENT_FAKE;

 if(fake_segments[whichsegment1].node1==fake_segments[whichsegment2].node1)
    return(1);

 if(fake_segments[whichsegment1].node2==fake_segments[whichsegment2].node2)
    return(1);

 return(0);
}
1	amb	455	/***************************************
2			Fake node and segment generation.
3
4			Part of the Routino routing software.
5			****************/ /****************
6	amb	1680	This file Copyright 2008-2015 Andrew M. Bishop
7	amb	455
8			This program is free software: you can redistribute it and/or modify
9			it under the terms of the GNU Affero General Public License as published by
10			the Free Software Foundation, either version 3 of the License, or
11			(at your option) any later version.
12
13			This program is distributed in the hope that it will be useful,
14			but WITHOUT ANY WARRANTY; without even the implied warranty of
15			MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16			GNU Affero General Public License for more details.
17
18			You should have received a copy of the GNU Affero General Public License
19			along with this program. If not, see <http://www.gnu.org/licenses/>.
20			***************************************/
21
22
23			#include "types.h"
24			#include "nodes.h"
25			#include "segments.h"
26
27	amb	532	#include "fakes.h"
28	amb	455
29
30			/+ The minimum distance along a segment from a node to insert a fake node. (in km). +/
31			#define MINSEGMENT 0.005
32
33
34	amb	1784	/* Local variables (re-initialised by DeleteFakeNodes() function) */
35
36	amb	455	/+ A set of fake segments to allow start/finish in the middle of a segment. +/
37	amb	535	static Segment fake_segments[4*NWAYPOINTS+1];
38	amb	455
39	amb	608	/+ A set of pointers to the real segments underlying the fake segments. +/
40			static index_t real_segments[4*NWAYPOINTS+1];
41
42	amb	455	/+ A set of fake node latitudes and longitudes. +/
43			static double fake_lon[NWAYPOINTS+1],fake_lat[NWAYPOINTS+1];
44
45	amb	535	/+ The previous waypoint. +/
46			static int prevpoint=0;
47	amb	455
48	amb	535
49	amb	455	/*++++++++++++++++++++++++++++++++++++++
50	amb	680	Create a pair of fake segments corresponding to the given segment split in two
51			(and will create an extra two fake segments if adjacent waypoints are on the
52			same segment).
53	amb	455
54			index_t CreateFakes Returns the fake node index (or a real one in special cases).
55
56			Nodes *nodes The set of nodes to use.
57
58	amb	608	Segments *segments The set of segments to use.
59
60	amb	680	int point Which of the waypoints this is.
61	amb	455
62	amb	1078	Segment *segmentp The segment to split.
63	amb	455
64			index_t node1 The first node at the end of this segment.
65
66			index_t node2 The second node at the end of this segment.
67
68	amb	1168	distance_t dist1 The distance to the first node.
69	amb	455
70	amb	1168	distance_t dist2 The distance to the second node.
71	amb	455	++++++++++++++++++++++++++++++++++++++*/
72
73	amb	1168	index_t CreateFakes(Nodes nodes,Segments segments,int point,Segment *segmentp,index_t node1,index_t node2,distance_t dist1,distance_t dist2)
74	amb	455	{
75			index_t fakenode;
76			double lat1,lon1,lat2,lon2;
77
78	amb	1784	/* Initialise all the connecting segments to fake values */
79	amb	535
80			fake_segments[4*point-4].node1=NO_NODE;
81			fake_segments[4*point-4].node2=NO_NODE;
82
83			fake_segments[4*point-3].node1=NO_NODE;
84			fake_segments[4*point-3].node2=NO_NODE;
85
86			fake_segments[4*point-2].node1=NO_NODE;
87			fake_segments[4*point-2].node2=NO_NODE;
88
89			fake_segments[4*point-1].node1=NO_NODE;
90			fake_segments[4*point-1].node2=NO_NODE;
91
92	amb	455	/* Check if we are actually close enough to an existing node */
93
94	amb	1385	if(dist1<=km_to_distance(MINSEGMENT) && dist2>km_to_distance(MINSEGMENT))
95	amb	535	{
96			prevpoint=point;
97	amb	455	return(node1);
98	amb	535	}
99	amb	455
100	amb	1385	if(dist2<=km_to_distance(MINSEGMENT) && dist1>km_to_distance(MINSEGMENT))
101	amb	535	{
102			prevpoint=point;
103	amb	455	return(node2);
104	amb	535	}
105	amb	455
106	amb	1385	if(dist1<=km_to_distance(MINSEGMENT) && dist2<=km_to_distance(MINSEGMENT))
107	amb	455	{
108	amb	535	prevpoint=point;
109
110	amb	455	if(dist1<dist2)
111			return(node1);
112			else
113			return(node2);
114			}
115
116			/* Create the fake node */
117
118	amb	471	fakenode=NODE_FAKE+point;
119	amb	455
120	amb	1291	GetLatLong(nodes,node1,NULL,&lat1,&lon1);
121			GetLatLong(nodes,node2,NULL,&lat2,&lon2);
122	amb	455
123			if(lat1>3 && lat2<-3)
124			lat2+=2*M_PI;
125			else if(lat1<-3 && lat2>3)
126			lat1+=2*M_PI;
127
128	amb	1385	fake_lat[point]=lat1+(lat2-lat1)(double)dist1/(double)(dist1+dist2); / (dist1+dist2) must be > 0 */
129			fake_lon[point]=lon1+(lon2-lon1)(double)dist1/(double)(dist1+dist2); / (dist1+dist2) must be > 0 */
130	amb	455
131			if(fake_lat[point]>M_PI) fake_lat[point]-=2*M_PI;
132
133	amb	631	/*
134			* node1 fakenode node2
135			* #--------------------------------------# real_segments[4point-{4,3}]
136			*
137			* #----------* fake_segments[4*point-4]
138			* ----------------------------# fake_segments[4point-3]
139			*
140			*
141			* node1 fakenode[prevpoint] node2
142			* #----------------------------%---------# real_segments[4prevpoint-{4,3,1}], real_segments[4*point-{4,3,2}]
143			* fakenode[point]
144			* #----------* fake_segments[4*prevpoint-4]
145			* ----------------------------# fake_segments[4prevpoint-3]
146			* ------------------% fake_segments[4prevpoint-1]
147			* #-----------------------------% fake_segments[4*point-4]
148			* %---------# fake_segments[4*point-3]
149			* ------------------% fake_segments[4point-2]
150			*/
151
152	amb	455	/* Create the first fake segment */
153
154	amb	1078	fake_segments[4point-4]=segmentp;
155	amb	455
156	amb	535	fake_segments[4*point-4].node2=fakenode;
157	amb	455
158	amb	1168	fake_segments[4*point-4].distance=DISTANCE(dist1)\|DISTFLAG(segmentp->distance);
159	amb	455
160	amb	1078	real_segments[4*point-4]=IndexSegment(segments,segmentp);
161	amb	608
162	amb	455	/* Create the second fake segment */
163
164	amb	1078	fake_segments[4point-3]=segmentp;
165	amb	455
166	amb	535	fake_segments[4*point-3].node1=fakenode;
167	amb	455
168	amb	1168	fake_segments[4*point-3].distance=DISTANCE(dist2)\|DISTFLAG(segmentp->distance);
169	amb	455
170	amb	1078	real_segments[4*point-3]=IndexSegment(segments,segmentp);
171	amb	608
172	amb	535	/* Create a third fake segment to join adjacent points if both are fake and on the same real segment */
173
174			if(prevpoint>0 && fake_segments[4prevpoint-4].node1==node1 && fake_segments[4prevpoint-3].node2==node2)
175			{
176	amb	1168	if(DISTANCE(dist1)>DISTANCE(fake_segments[4prevpoint-4].distance)) / point is further from node1 than prevpoint */
177	amb	535	{
178	amb	725	fake_segments[4point-2]=fake_segments[4prevpoint-3];
179	amb	535
180	amb	631	fake_segments[4*point-2].node2=fakenode;
181	amb	535
182	amb	1168	fake_segments[4point-2].distance=(DISTANCE(dist1)-DISTANCE(fake_segments[4prevpoint-4].distance))\|DISTFLAG(segmentp->distance);
183	amb	535	}
184			else
185			{
186	amb	725	fake_segments[4point-2]=fake_segments[4prevpoint-4];
187	amb	535
188	amb	631	fake_segments[4*point-2].node1=fakenode;
189	amb	535
190	amb	1168	fake_segments[4point-2].distance=(DISTANCE(fake_segments[4prevpoint-4].distance)-DISTANCE(dist1))\|DISTFLAG(segmentp->distance);
191	amb	535	}
192
193	amb	1078	real_segments[4*point-2]=IndexSegment(segments,segmentp);
194	amb	608
195	amb	535	fake_segments[4prevpoint-1]=fake_segments[4point-2];
196	amb	608
197			real_segments[4prevpoint-1]=real_segments[4point-2];
198	amb	535	}
199
200			/* Return the fake node */
201
202			prevpoint=point;
203
204	amb	455	return(fakenode);
205			}
206
207
208			/*++++++++++++++++++++++++++++++++++++++
209	amb	1565	Create a fake segment connecting a node to itself.
210
211			index_t CreateFakeNullSegment Returns the index of a fake segment.
212
213			Segments *segments The list of segments to use.
214
215			index_t node The node that is to be linked.
216
217			index_t segment The segment that is to be emulated.
218
219			int point The waypoint number.
220			++++++++++++++++++++++++++++++++++++++*/
221
222			index_t CreateFakeNullSegment(Segments *segments,index_t node,index_t segment,int point)
223			{
224			Segment *segmentp=LookupSegment(segments,segment,1);
225
226			fake_segments[4*point-2].node1=node;
227			fake_segments[4*point-2].node2=node;
228			fake_segments[4*point-2].way=segmentp->way;
229			fake_segments[4*point-2].distance=0;
230
231			return(4*point-2+SEGMENT_FAKE);
232			}
233
234
235			/*++++++++++++++++++++++++++++++++++++++
236	amb	1784	Re-initialise the fake node data storage.
237			++++++++++++++++++++++++++++++++++++++*/
238
239			void DeleteFakeNodes(void)
240			{
241			unsigned int i;
242
243			for(i=0;i<sizeof(fake_segments)/sizeof(fake_segments[0]);i++)
244			{
245			fake_segments[i].node1=NO_NODE;
246			fake_segments[i].node2=NO_NODE;
247			}
248
249			for(i=0;i<sizeof(real_segments)/sizeof(real_segments[0]);i++)
250			real_segments[i]=NO_SEGMENT;
251
252			prevpoint=0;
253			}
254
255
256			/*++++++++++++++++++++++++++++++++++++++
257	amb	455	Lookup the latitude and longitude of a fake node.
258
259	amb	680	index_t fakenode The fake node to lookup.
260	amb	455
261			double *latitude Returns the latitude
262
263			double *longitude Returns the longitude.
264			++++++++++++++++++++++++++++++++++++++*/
265
266			void GetFakeLatLong(index_t fakenode, double latitude,double longitude)
267			{
268	amb	608	index_t whichnode=fakenode-NODE_FAKE;
269	amb	455
270	amb	608	*latitude =fake_lat[whichnode];
271			*longitude=fake_lon[whichnode];
272	amb	455	}
273
274
275			/*++++++++++++++++++++++++++++++++++++++
276			Finds the first fake segment associated to a fake node.
277
278	amb	680	Segment *FirstFakeSegment Returns a pointer to the first fake segment.
279	amb	455
280	amb	680	index_t fakenode The fake node to lookup.
281	amb	455	++++++++++++++++++++++++++++++++++++++*/
282
283			Segment *FirstFakeSegment(index_t fakenode)
284			{
285	amb	608	index_t whichnode=fakenode-NODE_FAKE;
286	amb	455
287	amb	608	return(&fake_segments[4*whichnode-4]);
288	amb	455	}
289
290
291			/*++++++++++++++++++++++++++++++++++++++
292	amb	680	Finds the next fake segment associated to a fake node.
293	amb	455
294	amb	680	Segment *NextFakeSegment Returns a pointer to the next fake segment.
295	amb	455
296	amb	1078	Segment *fakesegmentp The first fake segment.
297	amb	455
298			index_t fakenode The node to lookup.
299			++++++++++++++++++++++++++++++++++++++*/
300
301	amb	1078	Segment NextFakeSegment(Segment fakesegmentp,index_t fakenode)
302	amb	455	{
303	amb	608	index_t whichnode=fakenode-NODE_FAKE;
304	amb	455
305	amb	1078	if(fakesegmentp==&fake_segments[4*whichnode-4])
306	amb	608	return(&fake_segments[4*whichnode-3]);
307	amb	535
308	amb	1078	if(fakesegmentp==&fake_segments[4whichnode-3] && fake_segments[4whichnode-2].node1!=NO_NODE)
309	amb	608	return(&fake_segments[4*whichnode-2]);
310	amb	535
311	amb	1078	if(fakesegmentp==&fake_segments[4whichnode-3] && fake_segments[4whichnode-1].node1!=NO_NODE)
312	amb	608	return(&fake_segments[4*whichnode-1]);
313	amb	535
314	amb	1078	if(fakesegmentp==&fake_segments[4whichnode-2] && fake_segments[4whichnode-1].node1!=NO_NODE)
315	amb	608	return(&fake_segments[4*whichnode-1]);
316	amb	535
317			return(NULL);
318	amb	455	}
319
320
321			/*++++++++++++++++++++++++++++++++++++++
322	amb	680	Finds the fake segment between a real node and a fake node.
323	amb	455
324			Segment *ExtraFakeSegment Returns a segment between the two specified nodes if it exists.
325
326	amb	608	index_t realnode The real node.
327	amb	455
328	amb	608	index_t fakenode The fake node.
329	amb	455	++++++++++++++++++++++++++++++++++++++*/
330
331	amb	608	Segment *ExtraFakeSegment(index_t realnode,index_t fakenode)
332	amb	455	{
333	amb	608	index_t whichnode=fakenode-NODE_FAKE;
334	amb	455
335	amb	608	if(fake_segments[4whichnode-4].node1==realnode \|\| fake_segments[4whichnode-4].node2==realnode)
336			return(&fake_segments[4*whichnode-4]);
337	amb	455
338	amb	608	if(fake_segments[4whichnode-3].node1==realnode \|\| fake_segments[4whichnode-3].node2==realnode)
339			return(&fake_segments[4*whichnode-3]);
340	amb	455
341			return(NULL);
342			}
343
344
345			/*++++++++++++++++++++++++++++++++++++++
346			Lookup a fake segment given its index.
347
348	amb	680	Segment *LookupFakeSegment Returns a pointer to the fake segment.
349	amb	455
350			index_t fakesegment The index of the fake segment.
351			++++++++++++++++++++++++++++++++++++++*/
352
353			Segment *LookupFakeSegment(index_t fakesegment)
354			{
355	amb	608	index_t whichsegment=fakesegment-SEGMENT_FAKE;
356	amb	455
357	amb	608	return(&fake_segments[whichsegment]);
358	amb	455	}
359
360
361			/*++++++++++++++++++++++++++++++++++++++
362			Find the fake index of a fake segment.
363
364			index_t IndexFakeSegment Returns the fake segment.
365
366	amb	1078	Segment *fakesegmentp The fake segment to look for.
367	amb	455	++++++++++++++++++++++++++++++++++++++*/
368
369	amb	1078	index_t IndexFakeSegment(Segment *fakesegmentp)
370	amb	455	{
371	amb	1680	index_t whichsegment=(index_t)(fakesegmentp-&fake_segments[0]);
372	amb	455
373	amb	608	return(whichsegment+SEGMENT_FAKE);
374	amb	455	}
375	amb	608
376
377			/*++++++++++++++++++++++++++++++++++++++
378			Find the real segment underlying a fake segment.
379
380	amb	680	index_t IndexRealSegment Returns the index of the real segment.
381	amb	608
382	amb	680	index_t fakesegment The index of the fake segment.
383	amb	608	++++++++++++++++++++++++++++++++++++++*/
384
385			index_t IndexRealSegment(index_t fakesegment)
386			{
387			index_t whichsegment=fakesegment-SEGMENT_FAKE;
388
389			return(real_segments[whichsegment]);
390			}
391	amb	727
392
393			/*++++++++++++++++++++++++++++++++++++++
394			Determine if a route between two fake segments is valid or a U-turn.
395
396			int IsFakeUTurn Returns true for a U-turn.
397
398			index_t fakesegment1 The first fake segment.
399
400			index_t fakesegment2 The second fake segment.
401			++++++++++++++++++++++++++++++++++++++*/
402
403			int IsFakeUTurn(index_t fakesegment1,index_t fakesegment2)
404			{
405			index_t whichsegment1=fakesegment1-SEGMENT_FAKE;
406			index_t whichsegment2=fakesegment2-SEGMENT_FAKE;
407
408			if(fake_segments[whichsegment1].node1==fake_segments[whichsegment2].node1)
409			return(1);
410
411			if(fake_segments[whichsegment1].node2==fake_segments[whichsegment2].node2)
412			return(1);
413
414			return(0);
415			}