Newer
Older
/*
* Copyright (C) 2008 Steve Ratcliffe
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2 as
* published by the Free Software Foundation.
*
* 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 General Public License for more details.
*
*
* Author: Robert Vollmert
* Create date: 02-Dec-2008
*/
package uk.me.parabola.imgfmt.app.net;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
import uk.me.parabola.imgfmt.app.Area;
import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.log.Logger;
/**
* This is a component of the RoadNetwork.
*
* Keeps track of outside neighbours and allows subdivision
* to satisfy NOD1 constraints.
*
* The approach to subdivision is to tile the map into RouteCenters.
* One could imagine that overlapping RouteCenters would be an option,
* say by splitting largely independent networks (motorways, footways).
*
* Could be rolled into RouteCenter.
*/
public class NOD1Part {
private static final Logger log = Logger.getLogger(NOD1Part.class);
/*
* Constraints:
*
* 1. Nodes section smaller than about 0x4000, which gives
* a bound on the number of nodes.
* 2. At most 0x100 entries in Table A. This gives a bound
* on the number of (forward) arcs meeting this
* RouteCenter.
* 3. At most 0x40 entries in Table B. This gives a bound
* on the number of neighboring nodes.
* 4. Absolute values of coordinate offsets at most 0x8000,
* which translates to about 0.7 degrees, so bounding
* box should be at most 1.4 x 1.4 degrees assuming
* the reference is in the middle. (With small offsets,
* this would be 0.08 x 0.08 degrees.)
* 5. Absolute values of relative NOD1 offsets at most
* 0x2000, which limits the nodes section to 0x2000
* unless we take care to order the nodes nicely.
* 6. Distance between nodes and start of tables must
* fit in a char for writing Table C. So nodes
* section smaller than 0x10000.
*/
// maximal width and height of the bounding box, since
// NOD 1 coordinate offsets are at most 16 bit wide.
private static final int MAX_SIZE_UNSAFE = 1 << 16;
private static final int MAX_SIZE = MAX_SIZE_UNSAFE - 0x800;
// Table A has at most 0x100 entries
private static final int MAX_TABA_UNSAFE = 0x100;
private static final int MAX_TABA = MAX_TABA_UNSAFE - 0x8;
// Table B has at most 0x100 entries
private static final int MAX_TABB_UNSAFE = 0x100;
private static final int MAX_TABB = MAX_TABB_UNSAFE - 0x2;
// Nodes size is max 0x2000 to cope with signed 14 bit node offsets
private static final int MAX_NODES_SIZE = 0x2000;
private int nodesSize;
public class BBox {
int maxLat, minLat, maxLon, minLon;
boolean empty;
BBox() {
empty = true;
}
BBox(Coord co) {
empty = false;
int lat = co.getLatitude();
int lon = co.getLongitude();
minLat = lat;
maxLat = lat+1;
minLon = lon;
maxLon = lon+1;
}
BBox(int minLat, int maxLat, int minLon, int maxLon) {
empty = false;
this.minLat = minLat;
this.maxLat = maxLat;
this.minLon = minLon;
this.maxLon = maxLon;
}
Area toArea() {
return new Area(minLat, minLon, maxLat, maxLon);
}
boolean contains(BBox bbox) {
return minLat <= bbox.minLat && bbox.maxLat <= maxLat
&& minLon <= bbox.minLon && bbox.maxLon <= maxLon;
}
boolean contains(Coord co) {
return contains(new BBox(co));
}
void extend(BBox bbox) {
if (bbox.empty)
return;
if (empty) {
empty = false;
minLat = bbox.minLat;
maxLat = bbox.maxLat;
minLon = bbox.minLon;
maxLon = bbox.maxLon;
} else {
minLat = Math.min(minLat, bbox.minLat);
maxLat = Math.max(maxLat, bbox.maxLat);
minLon = Math.min(minLon, bbox.minLon);
maxLon = Math.max(maxLon, bbox.maxLon);
}
}
void extend(Coord co) {
extend(new BBox(co));
}
BBox[] splitLat() {
BBox[] ret = new BBox[2];
int midLat = (minLat + maxLat) / 2;
ret[0] = new BBox(minLat, midLat, minLon, maxLon);
ret[1] = new BBox(midLat, maxLat, minLon, maxLon);
return ret;
}
BBox[] splitLon() {
BBox[] ret = new BBox[2];
int midLon = (minLon + maxLon) / 2;
ret[0] = new BBox(minLat, maxLat, minLon, midLon);
ret[1] = new BBox(minLat, maxLat, midLon, maxLon);
return ret;
}
int getWidth() {
return maxLon - minLon;
}
int getHeight() {
return maxLat - minLat;
}
int getMaxDimension() {
return Math.max(getWidth(), getHeight());
}
public String toString() {
return "BBox[" + new Coord(minLat,minLon).toDegreeString()
+ ", " + new Coord(maxLat,maxLon).toDegreeString() + "]";
}
}
// The area we are supposed to cover.
private final BBox bbox;
// The area that actually has nodes.
private final BBox bboxActual = new BBox();
private List<RouteNode> nodes = new ArrayList<>();
private Map<RouteNode,RouteNode> destNodes = new LinkedHashMap<>();
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
/**
* Create an unbounded NOD1Part.
*
* All nodes will be accepted by addNode and
* all arcs will be considered internal.
*/
public NOD1Part() {
log.info("creating new unbounded NOD1Part");
this.bbox = null;
}
/**
* Create a bounded NOD1Part.
*
* The bounding box is used to decide which arcs
* are internal.
*/
private NOD1Part(BBox bbox) {
log.info("creating new NOD1Part:", bbox);
this.bbox = bbox;
}
/**
* Add a node to this part.
*
* The node is used to populate the tables. If an
* arc points outside the bbox, we know it's not
* an internal arc. It might still turn into an
* external arc at a deeper level of recursion.
*/
public void addNode(RouteNode node) {
assert bbox == null || bbox.contains(node.getCoord()) : "trying to add out-of-bounds node: " + node;
bboxActual.extend(node.getCoord());
nodes.add(node);
for (RouteArc arc : node.arcsIteration()) {
tabA.addArc(arc);
RouteNode dest = arc.getDest();
} else if (bbox != null && !bbox.contains(dest.getCoord()) || dest.getGroup() != node.getGroup()) {
destNodes.put(dest, dest);
}
}
for (RouteRestriction rr: node.getRestrictions()){
List<RouteArc> arcs = rr.getArcs();
if (arcs.size() >= 3){
for (int i = 0; i < arcs.size(); i++){
RouteArc arc = arcs.get(i);
if (arc.getSource() != node){
tabA.addArc(arc);
RouteNode dest = arc.getDest();
destNodes.put(dest, dest);
else if (bbox != null && !bbox.contains(dest.getCoord()) || dest.getGroup() != node.getGroup()) {
arc.setInternal(false);
destNodes.put(dest, dest);
}
}
}
nodesSize += node.boundSize();
}
/**
* Subdivide this part recursively until it satisfies the constraints.
*/
public List<RouteCenter> subdivide() {
return subdivideHelper(0);
}
/**
* Subdivide this part recursively until it satisfies the constraints.
*/
protected List<RouteCenter> subdivideHelper(int depth) {
List<RouteCenter> centers = new LinkedList<>();
if (satisfiesConstraints()) {
centers.add(this.toRouteCenter());
return centers;
}
if(depth > 48) {
log.error("Region contains too many nodes/arcs (discarding " + nodes.size() + " nodes to be able to continue)");
log.error(" Expect the routing to be broken near " + bbox);
for (RouteNode node : nodes)
node.discard();
return centers;
}
log.info("subdividing", bbox, bboxActual);
BBox[] split ;
if (bboxActual.getWidth() > bboxActual.getHeight())
split = bboxActual.splitLon();
else
split = bboxActual.splitLat();
NOD1Part[] parts = new NOD1Part[2];
for (int i = 0; i < split.length; i++)
parts[i] = new NOD1Part(split[i]);
for (RouteNode node : nodes) {
int i = 0;
while (!split[i].contains(node.getCoord()))
i++;
parts[i].addNode(node);
}
this.tabA = null;
this.destNodes = null;
this.nodes = null;
for (NOD1Part part : parts)
if(!part.bboxActual.empty)
centers.addAll(part.subdivideHelper(depth + 1));
return centers;
}
private boolean satisfiesConstraints() {
log.debug("constraints:", bboxActual, tabA.size(), destNodes.size(), nodesSize);
return bboxActual.getMaxDimension() < MAX_SIZE
&& tabA.size() < MAX_TABA
&& nodesSize < MAX_NODES_SIZE;
}
/**
* Convert to a RouteCenter.
*
* satisfiesConstraints() should be true for this to
* be a legal RouteCenter.
*/
private RouteCenter toRouteCenter() {
nodes.sort((n1, n2) -> n1.getCoord().compareTo(n2.getCoord()));
TableB tabB = new TableB();
for (RouteNode rn : destNodes.keySet())
tabB.addNode(rn);
return new RouteCenter(bboxActual.toArea(), nodes, tabA, tabB);
}
}