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	/***************************************
2	Fake node and segment generation.
3
4	Part of the Routino routing software.
5	****************/ /****************
6	This file Copyright 2008-2015 Andrew M. Bishop
7
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	#include "fakes.h"
28
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	/* Local variables (re-initialised by DeleteFakeNodes() function) */
35
36	/+ A set of fake segments to allow start/finish in the middle of a segment. +/
37	static Segment fake_segments[4*NWAYPOINTS+1];
38
39	/+ A set of pointers to the real segments underlying the fake segments. +/
40	static index_t real_segments[4*NWAYPOINTS+1];
41
42	/+ A set of fake node latitudes and longitudes. +/
43	static double fake_lon[NWAYPOINTS+1],fake_lat[NWAYPOINTS+1];
44
45	/+ The previous waypoint. +/
46	static int prevpoint=0;
47
48
49	/*++++++++++++++++++++++++++++++++++++++
50	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
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	Segments *segments The set of segments to use.
59
60	int point Which of the waypoints this is.
61
62	Segment *segmentp The segment to split.
63
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	distance_t dist1 The distance to the first node.
69
70	distance_t dist2 The distance to the second node.
71	++++++++++++++++++++++++++++++++++++++*/
72
73	index_t CreateFakes(Nodes nodes,Segments segments,int point,Segment *segmentp,index_t node1,index_t node2,distance_t dist1,distance_t dist2)
74	{
75	index_t fakenode;
76	double lat1,lon1,lat2,lon2;
77
78	/* Initialise all the connecting segments to fake values */
79
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	/* Check if we are actually close enough to an existing node */
93
94	if(dist1<=km_to_distance(MINSEGMENT) && dist2>km_to_distance(MINSEGMENT))
95	{
96	prevpoint=point;
97	return(node1);
98	}
99
100	if(dist2<=km_to_distance(MINSEGMENT) && dist1>km_to_distance(MINSEGMENT))
101	{
102	prevpoint=point;
103	return(node2);
104	}
105
106	if(dist1<=km_to_distance(MINSEGMENT) && dist2<=km_to_distance(MINSEGMENT))
107	{
108	prevpoint=point;
109
110	if(dist1<dist2)
111	return(node1);
112	else
113	return(node2);
114	}
115
116	/* Create the fake node */
117
118	fakenode=NODE_FAKE+point;
119
120	GetLatLong(nodes,node1,NULL,&lat1,&lon1);
121	GetLatLong(nodes,node2,NULL,&lat2,&lon2);
122
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	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
131	if(fake_lat[point]>M_PI) fake_lat[point]-=2*M_PI;
132
133	/*
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	/* Create the first fake segment */
153
154	fake_segments[4point-4]=segmentp;
155
156	fake_segments[4*point-4].node2=fakenode;
157
158	fake_segments[4*point-4].distance=DISTANCE(dist1)\|DISTFLAG(segmentp->distance);
159
160	real_segments[4*point-4]=IndexSegment(segments,segmentp);
161
162	/* Create the second fake segment */
163
164	fake_segments[4point-3]=segmentp;
165
166	fake_segments[4*point-3].node1=fakenode;
167
168	fake_segments[4*point-3].distance=DISTANCE(dist2)\|DISTFLAG(segmentp->distance);
169
170	real_segments[4*point-3]=IndexSegment(segments,segmentp);
171
172	/* 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	if(DISTANCE(dist1)>DISTANCE(fake_segments[4prevpoint-4].distance)) / point is further from node1 than prevpoint */
177	{
178	fake_segments[4point-2]=fake_segments[4prevpoint-3];
179
180	fake_segments[4*point-2].node2=fakenode;
181
182	fake_segments[4point-2].distance=(DISTANCE(dist1)-DISTANCE(fake_segments[4prevpoint-4].distance))\|DISTFLAG(segmentp->distance);
183	}
184	else
185	{
186	fake_segments[4point-2]=fake_segments[4prevpoint-4];
187
188	fake_segments[4*point-2].node1=fakenode;
189
190	fake_segments[4point-2].distance=(DISTANCE(fake_segments[4prevpoint-4].distance)-DISTANCE(dist1))\|DISTFLAG(segmentp->distance);
191	}
192
193	real_segments[4*point-2]=IndexSegment(segments,segmentp);
194
195	fake_segments[4prevpoint-1]=fake_segments[4point-2];
196
197	real_segments[4prevpoint-1]=real_segments[4point-2];
198	}
199
200	/* Return the fake node */
201
202	prevpoint=point;
203
204	return(fakenode);
205	}
206
207
208	/*++++++++++++++++++++++++++++++++++++++
209	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	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	Lookup the latitude and longitude of a fake node.
258
259	index_t fakenode The fake node to lookup.
260
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	index_t whichnode=fakenode-NODE_FAKE;
269
270	*latitude =fake_lat[whichnode];
271	*longitude=fake_lon[whichnode];
272	}
273
274
275	/*++++++++++++++++++++++++++++++++++++++
276	Finds the first fake segment associated to a fake node.
277
278	Segment *FirstFakeSegment Returns a pointer to the first fake segment.
279
280	index_t fakenode The fake node to lookup.
281	++++++++++++++++++++++++++++++++++++++*/
282
283	Segment *FirstFakeSegment(index_t fakenode)
284	{
285	index_t whichnode=fakenode-NODE_FAKE;
286
287	return(&fake_segments[4*whichnode-4]);
288	}
289
290
291	/*++++++++++++++++++++++++++++++++++++++
292	Finds the next fake segment associated to a fake node.
293
294	Segment *NextFakeSegment Returns a pointer to the next fake segment.
295
296	Segment *fakesegmentp The first fake segment.
297
298	index_t fakenode The node to lookup.
299	++++++++++++++++++++++++++++++++++++++*/
300
301	Segment NextFakeSegment(Segment fakesegmentp,index_t fakenode)
302	{
303	index_t whichnode=fakenode-NODE_FAKE;
304
305	if(fakesegmentp==&fake_segments[4*whichnode-4])
306	return(&fake_segments[4*whichnode-3]);
307
308	if(fakesegmentp==&fake_segments[4whichnode-3] && fake_segments[4whichnode-2].node1!=NO_NODE)
309	return(&fake_segments[4*whichnode-2]);
310
311	if(fakesegmentp==&fake_segments[4whichnode-3] && fake_segments[4whichnode-1].node1!=NO_NODE)
312	return(&fake_segments[4*whichnode-1]);
313
314	if(fakesegmentp==&fake_segments[4whichnode-2] && fake_segments[4whichnode-1].node1!=NO_NODE)
315	return(&fake_segments[4*whichnode-1]);
316
317	return(NULL);
318	}
319
320
321	/*++++++++++++++++++++++++++++++++++++++
322	Finds the fake segment between a real node and a fake node.
323
324	Segment *ExtraFakeSegment Returns a segment between the two specified nodes if it exists.
325
326	index_t realnode The real node.
327
328	index_t fakenode The fake node.
329	++++++++++++++++++++++++++++++++++++++*/
330
331	Segment *ExtraFakeSegment(index_t realnode,index_t fakenode)
332	{
333	index_t whichnode=fakenode-NODE_FAKE;
334
335	if(fake_segments[4whichnode-4].node1==realnode \|\| fake_segments[4whichnode-4].node2==realnode)
336	return(&fake_segments[4*whichnode-4]);
337
338	if(fake_segments[4whichnode-3].node1==realnode \|\| fake_segments[4whichnode-3].node2==realnode)
339	return(&fake_segments[4*whichnode-3]);
340
341	return(NULL);
342	}
343
344
345	/*++++++++++++++++++++++++++++++++++++++
346	Lookup a fake segment given its index.
347
348	Segment *LookupFakeSegment Returns a pointer to the fake segment.
349
350	index_t fakesegment The index of the fake segment.
351	++++++++++++++++++++++++++++++++++++++*/
352
353	Segment *LookupFakeSegment(index_t fakesegment)
354	{
355	index_t whichsegment=fakesegment-SEGMENT_FAKE;
356
357	return(&fake_segments[whichsegment]);
358	}
359
360
361	/*++++++++++++++++++++++++++++++++++++++
362	Find the fake index of a fake segment.
363
364	index_t IndexFakeSegment Returns the fake segment.
365
366	Segment *fakesegmentp The fake segment to look for.
367	++++++++++++++++++++++++++++++++++++++*/
368
369	index_t IndexFakeSegment(Segment *fakesegmentp)
370	{
371	index_t whichsegment=(index_t)(fakesegmentp-&fake_segments[0]);
372
373	return(whichsegment+SEGMENT_FAKE);
374	}
375
376
377	/*++++++++++++++++++++++++++++++++++++++
378	Find the real segment underlying a fake segment.
379
380	index_t IndexRealSegment Returns the index of the real segment.
381
382	index_t fakesegment The index of the fake segment.
383	++++++++++++++++++++++++++++++++++++++*/
384
385	index_t IndexRealSegment(index_t fakesegment)
386	{
387	index_t whichsegment=fakesegment-SEGMENT_FAKE;
388
389	return(real_segments[whichsegment]);
390	}
391
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	}