/*
* Copyright (C) 2013-2014.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 3 or
* 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.
*/
package uk.me.parabola.mkgmap.osmstyle;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashMap;
import uk.me.parabola.imgfmt.Utils;
import uk.me.parabola.imgfmt.app.Area;
import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.log.Logger;
import uk.me.parabola.mkgmap.filters.DouglasPeuckerFilter;
import uk.me.parabola.mkgmap.general.MapPoint;
import uk.me.parabola.mkgmap.reader.osm.CoordPOI;
import uk.me.parabola.mkgmap.reader.osm.FakeIdGenerator;
import uk.me.parabola.mkgmap.reader.osm.Node;
import uk.me.parabola.mkgmap.reader.osm.RestrictionRelation;
import uk.me.parabola.mkgmap.reader.osm.Way;
import uk.me.parabola.util.GpxCreator;
/**
* We are rounding coordinates with double precision to map units with a
* precision of < 2m. This hasn't a big visible effect for single points,
* but wherever points are connected with lines the lines may show
* heavy zig-zagging while the original lines were almost straight.
* This happens when one of the points was rounded to one direction
* and the next point was rounded to the opposite direction.
* The effect is esp. visible with parallel roads, rails, and buildings,
* but also in small roundabouts.
* The methods in this class try to fix these wrong bearings by
* moving or removing points.
*
* @author GerdP
*
*/
public class WrongAngleFixer
{
private static final Logger log =
Logger.
getLogger(WrongAngleFixer.
class);
private static final double MAX_BEARING_ERROR =
15;
private static final double MAX_BEARING_ERROR_HALF = MAX_BEARING_ERROR /
2;
private static final double MAX_DIFF_ANGLE_STRAIGHT_LINE =
3;
private final Area bbox
;
private static final String DEBUG_PATH =
null;
private int pass
;
private boolean extraPass
;
private ArrayList<ConvertedWay
> convertedWays
;
/**
* Construct new WrongAngleFixer
* @param bbox the bounding box, ignored if null, else might be used for debugging
* @param allCoordPOI all {@code MapPoint} instances which refer to {@code CoordP} instances. There location might be changed
* in this class.
*/
public WrongAngleFixer
(Area bbox
) {
this.
bbox = bbox
;
if (DEBUG_PATH
!=
null && bbox
!=
null && (long) bbox.
getWidth() * bbox.
getHeight() < 100000) {
List<Coord
> grid =
new ArrayList<>();
for (int lat = bbox.
getMinLat(); lat
< bbox.
getMaxLat(); lat++
) {
for (int lon = bbox.
getMinLong(); lon
< bbox.
getMaxLong(); lon++
) {
grid.
add(new Coord
(lat, lon
));
}
}
GpxCreator.
createGpx(Utils.
joinPath(DEBUG_PATH,
"grid"), bbox.
toCoords(), grid
);
}
}
/**
* Find wrong angles caused by rounding to map units. Try to fix them by
* moving, removing or merging points.
* When done, remove obsolete points.
* @param roads list of roads, elements might be set to null by this method
* @param lines list of non-routable ways
* @param modifiedRoads Will be enlarged by all roads modified in this method
* @param deletedRoads Will be enlarged by all roads in roads that were set to null by this method
* @param restrictions Map with restriction relations
* @param renderedPOI all MapPoint instances for {@code CoordPOI} instances
*/
public void optimizeWays
(List<ConvertedWay
> roads,
List<ConvertedWay
> lines,
Map<Long, ConvertedWay
> modifiedRoads,
Set<Long> deletedRoads,
List<RestrictionRelation
> restrictions,
List<MapPoint
> renderedPOI
) {
printBadAngles
("bad_angles_start", roads
);
writeOSM
("roads_orig", roads
);
writeOSM
("lines_orig", lines
);
convertedWays =
new ArrayList<>();
convertedWays.
addAll(roads
);
convertedWays.
addAll(lines
);
convertedWays.
removeIf(ConvertedWay::isOverlay
);
convertedWays.
sort((o1,o2
) -
> Long.
compare(o1.
getWay().
getId(), o2.
getWay().
getId()));
replaceDuplicateBoundaryNodes
(convertedWays
);
Map<Coord, Coord
> replacements = removeWrongAngles
(modifiedRoads, deletedRoads
);
writeOSM
("roads_post_rem_wrong_angles", roads
);
removeObsoletePoints
(modifiedRoads
);
writeOSM
("roads_post_rem_obsolete_points", roads
);
printBadAngles
("bad_angles_finish", roads
);
writeOSM
("lines_post_rem_wrong_angles", lines
);
convertedWays =
null;
for (RestrictionRelation rr : restrictions
) {
for (Coord p : rr.
getViaCoords()) {
Coord replacement = getReplacement
(p,
null, replacements
);
if (p
!= replacement
) {
rr.
replaceViaCoord(p, replacement
);
}
}
}
// update positions of the POIs which were already created.
for (MapPoint mp : renderedPOI
) {
Coord replacement = getReplacement
(mp.
getLocation(),
null, replacements
);
if (mp.
getLocation() != replacement
) {
mp.
setLocation(replacement
);
}
}
}
/**
* Make boundary nodes unique.
* @param convertedWays
* @param coordMap
*/
private static void replaceDuplicateBoundaryNodes
(List<ConvertedWay
> convertedWays
) {
Long2ObjectOpenHashMap
<Coord
> coordMap =
new Long2ObjectOpenHashMap
<>();
for (ConvertedWay cw : convertedWays
) {
if (!cw.
isValid())
continue;
Way way = cw.
getWay();
List<Coord
> points = way.
getPoints();
for (int i =
0; i
< points.
size(); i++
) {
Coord co = points.
get(i
);
if (!co.
getOnBoundary())
continue;
Coord repl = coordMap.
get(Utils.
coord2Long(co
));
if (repl ==
null)
coordMap.
put(Utils.
coord2Long(co
), co
);
else {
if (!co.
isAddedByClipper() && repl.
isAddedByClipper()) {
log.
debug("check replaced original boundary node at", co
);
}
points.
set(i, repl
);
}
}
}
}
/**
* Common code to handle replacements of points in ways. Checks for special
* cases regarding CoordPOI.
*
* @param p point to replace
* @param way way that contains p
* @param replacements the Map containing the replaced points
* @return the replacement
*/
private static Coord getReplacement
(Coord p, Way way,
Map<Coord, Coord
> replacements
) {
// check if this point is to be replaced because
// it was previously merged into another point
if (p.
isReplaced()) {
Coord replacement =
null;
Coord r = p
;
while ((r = replacements.
get(r
)) !=
null) {
replacement = r
;
}
if (replacement
!=
null) {
if (p
instanceof CoordPOI
) {
CoordPOI cp =
(CoordPOI
) p
;
Node node = cp.
getNode();
if (cp.
isUsed() && way
!=
null && way.
getId() !=
0) {
String wayPOI = way.
getTag(StyledConverter.
WAY_POI_NODE_IDS);
if (wayPOI
!=
null && wayPOI.
contains("[" + node.
getId() +
"]")) {
if (replacement
instanceof CoordPOI
) {
Node rNode =
((CoordPOI
) replacement
).
getNode();
if (rNode.
getId() != node.
getId()) {
if (wayPOI.
contains("[" + rNode.
getId() +
"]")) {
log.
warn("CoordPOI", node.
getId(),
"replaced by CoordPOI", rNode.
getId(),
"in way", way.
toBrowseURL());
} else {
log.
warn("CoordPOI", node.
getId(),
"replaced by ignored CoordPOI",
rNode.
getId(),
"in way", way.
toBrowseURL());
}
}
} else {
log.
warn("CoordPOI", node.
getId(),
"replaced by simple coord in way",
way.
toBrowseURL());
}
}
}
}
return replacement
;
}
log.
error("replacement not found for point " + p.
toOSMURL());
}
return p
;
}
/**
* Find wrong angles caused by rounding to map units. Try to fix them by
* moving, removing or merging points.
* @param modifiedRoads map of modified routable ways (modified by this routine)
* @param deletedRoads set of ids of deleted routable ways (modified by this routine)
* @return
*/
private Map<Coord, Coord
> removeWrongAngles
(Map<Long, ConvertedWay
> modifiedRoads,
Set<Long> deletedRoads
) {
// replacements maps those nodes that have been replaced to
// the node that replaces them
Map<Coord, Coord
> replacements =
new IdentityHashMap<>();
final HashSet<Coord
> changedPlaces =
new HashSet<>();
int numNodesMerged =
0;
HashSet<Way
> waysWithBearingErrors =
new HashSet<>();
HashSet<Long> waysThatMapToOnePoint =
new HashSet<>();
// filter with Douglas Peucker algo
prepWithDouglasPeucker
(modifiedRoads
);
Way lastWay =
null;
boolean anotherPassRequired =
true;
final int maxPass =
20;
for (pass =
1; pass
< maxPass
; pass++
) {
if (!anotherPassRequired
&& !extraPass
)
break;
anotherPassRequired =
false;
log.
info("Removing wrong angles - PASS", pass
);
writeOSM
("pass_" + pass, convertedWays
);
// Step 1: detect points which are parts of line segments with wrong bearings
lastWay =
null;
for (ConvertedWay cw : convertedWays
) {
if (!cw.
isValid())
continue;
Way way = cw.
getWay();
if (way.
equals(lastWay
))
continue;
if (pass
!=
1 && !waysWithBearingErrors.
contains(way
))
continue;
lastWay = way
;
List<Coord
> points = way.
getPoints();
// scan through the way's points looking for line segments with big
// bearing errors
Coord prev =
null;
if (points.
get(0) == points.
get(points.
size() -
1) && points.
size() >=
2)
prev = points.
get(points.
size() -
2);
boolean hasNonEqualPoints =
false;
for (int i =
0; i
< points.
size(); ++i
) {
Coord p = points.
get(i
);
if (pass ==
1)
p.
setRemove(false);
p = getReplacement
(p, way, replacements
);
if (!cw.
isRoad() && (i ==
0 || i == points.
size() -
1)) {
p.
setEndOfWay(true);
}
if (prev
!=
null) {
if (pass ==
1 && !p.
equals(prev
))
hasNonEqualPoints =
true;
double err = calcBearingError
(p, prev
);
if (err
>= MAX_BEARING_ERROR
) {
// bearing error is big
p.
setPartOfBadAngle(true);
prev.
setPartOfBadAngle(true);
}
}
prev = p
;
}
if (pass ==
1 && !hasNonEqualPoints
) {
waysThatMapToOnePoint.
add(way.
getId());
log.
info("all points of way", way.
toBrowseURL(),
"are rounded to equal map units");
}
}
// Step 2: collect the line segments that are connected to critical points
IdentityHashMap<Coord, CenterOfAngle
> centerMap =
new IdentityHashMap<>();
List<CenterOfAngle
> centers =
new ArrayList<>(); // needed for ordered processing
Map<Coord,
Set<Way
>> overlaps =
new HashMap<>();
lastWay =
null;
for (ConvertedWay cw : convertedWays
) {
if (!cw.
isValid() || cw.
getWay().
equals(lastWay
))
continue;
Way way = cw.
getWay();
if (pass
!=
1 && !waysWithBearingErrors.
contains(way
))
continue;
lastWay = way
;
boolean wayHasSpecialPoints =
false;
List<Coord
> points = way.
getPoints();
// scan through the way's points looking for line segments with big
// bearing errors
Coord prev =
null;
if (points.
get(0) == points.
get(points.
size() -
1) && points.
size() >=
2)
prev = points.
get(points.
size() -
2);
for (int i =
0; i
< points.
size(); ++i
) {
Coord p = points.
get(i
);
if (prev
!=
null) {
if (p == prev
) {
points.
remove(i
);
--i
;
if (cw.
isRoad()) {
modifiedRoads.
put(way.
getId(), cw
);
}
continue;
}
if (p.
isPartOfBadAngle() || prev.
isPartOfBadAngle()) {
wayHasSpecialPoints =
true;
// save both points with their neighbour
Coord p1 = prev
;
Coord p2 = p
;
CenterOfAngle coa1 = getOrCreateCenter
(p, cw, centerMap, centers, overlaps
);
CenterOfAngle coa2 = getOrCreateCenter
(prev, cw, centerMap, centers, overlaps
);
coa1.
addNeighbour(coa2
);
coa2.
addNeighbour(coa1
);
if (points.
size() ==
2) {
// way has only two points, don't merge them
coa1.
addBadMergeCandidate(coa2
);
}
if (cw.
isRoad() && p1.
getHighwayCount() >=
2 && p2.
getHighwayCount() >=
2
&& cw.
isRoundabout()) {
// avoid to merge exits of roundabouts
coa1.
addBadMergeCandidate(coa2
);
}
}
}
prev = p
;
}
if (pass ==
1 && wayHasSpecialPoints
)
waysWithBearingErrors.
add(way
);
}
markOverlaps
(overlaps, centers
);
overlaps.
clear();
// Step 3: Update list of ways with bearing errors or points next to them
lastWay =
null;
for (ConvertedWay cw : convertedWays
) {
if (!cw.
isValid() || cw.
getWay().
equals(lastWay
))
continue;
Way way = cw.
getWay();
lastWay = way
;
if (!waysWithBearingErrors.
contains(way
)) {
List<Coord
> points = way.
getPoints();
// scan through the way's points looking for line segments with big
// bearing errors
for (Coord p : points
) {
if (p.
getHighwayCount() >=
2 && centerMap.
containsKey(p
)) {
waysWithBearingErrors.
add(way
);
break;
}
}
}
}
log.
info("pass " + pass +
": analysing " + centers.
size() +
" points with bearing problems.");
centerMap =
null; // Return to GC
// Step 4: try to correct the errors
List<CenterOfAngle
> checkAgainList =
null;
boolean tryMerge =
false;
while (true) {
checkAgainList =
new ArrayList<>();
for (CenterOfAngle coa : centers
) {
coa.
center.
setPartOfBadAngle(false); // reset flag for next pass
if (coa.
getCurrentLocation(replacements
) ==
null)
continue; // removed center
if (!coa.
isOK(replacements
)) {
boolean changed = coa.
tryChange(replacements, tryMerge
);
if (changed
) {
if (DEBUG_PATH
!=
null)
changedPlaces.
add(coa.
center);
continue;
}
checkAgainList.
add(coa
);
}
}
if (tryMerge
)
break; // leave when 2nd pass finished
tryMerge =
true;
centers = checkAgainList
;
}
// Step 5: apply the calculated corrections to the ways
lastWay =
null;
boolean lastWayModified =
false;
ConvertedWay lastConvertedWay =
null;
for (ConvertedWay cw : convertedWays
) {
if (!cw.
isValid() ||
!waysWithBearingErrors.
contains(cw.
getWay()))
continue;
Way way = cw.
getWay();
List<Coord
> points = way.
getPoints();
if (way.
equals(lastWay
)) {
if (lastWayModified
) {
points.
clear();
points.
addAll(lastWay.
getPoints());
if (cw.
isReversed() != lastConvertedWay.
isReversed())
Collections.
reverse(points
);
}
continue;
}
lastWay = way
;
lastConvertedWay = cw
;
lastWayModified =
false;
// loop backwards because we may delete points
for (int i = points.
size() -
1; i
>=
0; i--
) {
Coord p = points.
get(i
);
if (p.
isToRemove()) {
if (pass
>= maxPass -
1) {
log.
warn("removed point in last pass. Way", getUsableId
(way
), p.
toDegreeString());
}
points.
remove(i
);
anotherPassRequired =
true;
lastWayModified =
true;
if (i
> 0 && i
< points.
size() && points.
get(i -
1) == points.
get(i
)) {
// special case: handle micro loop
points.
remove(i
);
}
continue;
}
// check if this point is to be replaced because
// it was previously moved
Coord replacement = getReplacement
(p, way, replacements
);
if (p == replacement
)
continue;
if (p.
isViaNodeOfRestriction()) {
// make sure that we find the restriction with the new coord instance
replacement.
setViaNodeOfRestriction(true);
p.
setViaNodeOfRestriction(false);
}
p = replacement
;
if (pass
>= maxPass -
1) {
log.
warn("changed point in last pass. Way", getUsableId
(way
), p.
toDegreeString());
}
// replace point in way
points.
set(i, p
);
if (p.
getHighwayCount() >=
2)
numNodesMerged++
;
lastWayModified =
true;
if (i +
1 < points.
size() && points.
get(i +
1) == p
) {
points.
remove(i
);
anotherPassRequired =
true;
}
if (i -
1 >=
0 && points.
get(i -
1) == p
) {
points.
remove(i
);
anotherPassRequired =
true;
}
}
if (lastWayModified
&& cw.
isRoad()) {
modifiedRoads.
put(way.
getId(), cw
);
}
}
if (extraPass
) {
anotherPassRequired =
false;
break;
} else {
if (!anotherPassRequired
) {
// check if we have centres on different ways that overlap
for (CenterOfAngle coa : centers
) {
if (coa.
forceChange) {
anotherPassRequired =
true;
extraPass =
true;
break;
}
}
}
}
}
// finish: remove remaining duplicate points
int numWaysDeleted =
0;
lastWay =
null;
boolean lastWayModified =
false;
ConvertedWay lastConvertedWay =
null;
for (ConvertedWay cw : convertedWays
) {
Way way = cw.
getWay();
List<Coord
> points = way.
getPoints();
if (points.
size() < 2) {
if (log.
isInfoEnabled())
log.
info(" Way " + way.
getTag("name") +
" (" + way.
toBrowseURL() +
") has less than 2 points - deleting it");
if (!cw.
isRoad() && !waysThatMapToOnePoint.
contains(way.
getId())) {
log.
warn("non-routable way ", way.
getId(),
"was removed");
}
if (cw.
isRoad())
deletedRoads.
add(way.
getId());
++numWaysDeleted
;
continue;
}
if (way.
equals(lastWay
)) {
if (lastWayModified
) {
points.
clear();
points.
addAll(lastWay.
getPoints());
if (cw.
isReversed() != lastConvertedWay.
isReversed())
Collections.
reverse(points
);
}
continue;
}
lastWay = way
;
lastConvertedWay = cw
;
lastWayModified =
false;
Coord prev = points.
get(points.
size() -
1);
// loop backwards because we may delete points
for (int i = points.
size() -
2; i
>=
0; i--
) {
Coord p = points.
get(i
);
if (p == prev
) {
points.
remove(i
);
lastWayModified =
true;
}
prev = p
;
}
}
// treat special case: non-routable ways may be connected to moved
// points in roads
for (ConvertedWay cw : convertedWays
) {
if (!cw.
isValid() || cw.
isRoad())
continue;
Way way = cw.
getWay();
List<Coord
> points = way.
getPoints();
int n = points.
size();
boolean hasReplacedPoints =
false;
for (int i =
0; i
< n
; i++
) {
Coord p = points.
get(i
);
if (p.
isReplaced()) {
hasReplacedPoints =
true;
points.
set(i, getReplacement
(p,
null, replacements
));
}
}
if (hasReplacedPoints
&& DEBUG_PATH
!=
null) {
GpxCreator.
createGpx(Utils.
joinPath(DEBUG_PATH, way.
getId() +
"_mod_non_routable"), points
);
}
}
if (DEBUG_PATH
!=
null) {
GpxCreator.
createGpx(
Utils.
joinPath(DEBUG_PATH,
"solved_badAngles"),
bbox.
toCoords(),
new ArrayList<>(changedPlaces
));
}
if (anotherPassRequired
) {
log.
warn("Removing wrong angles - didn't finish in " + pass +
" passes, giving up!");
} else {
log.
info("Removing wrong angles - finished in", pass,
"passes (", numNodesMerged,
"nodes merged,",
numWaysDeleted,
"ways deleted)");
}
return replacements
;
}
private CenterOfAngle getOrCreateCenter
(Coord p, ConvertedWay cw,
IdentityHashMap<Coord, CenterOfAngle
> centerMap,
List<CenterOfAngle
> centers,
Map<Coord,
Set<Way
>> overlaps
) {
CenterOfAngle coa = centerMap.
get(p
);
if (coa ==
null) {
coa =
new CenterOfAngle
(p, centerMap.
size() +
1);
centerMap.
put(p, coa
);
centers.
add(coa
);
if (cw.
isRoad() && pass
> 1) {
overlaps.
computeIfAbsent(p, k -
> new HashSet<>()).
add(cw.
getWay());
}
}
return coa
;
}
private void markOverlaps
(Map<Coord,
Set<Way
>> overlaps,
List<CenterOfAngle
> centers
) {
for (Entry
<Coord,
Set<Way
>> entry : overlaps.
entrySet()) {
if (entry.
getValue().
size() > 1) {
Coord p = entry.
getKey();
for (CenterOfAngle coa : centers
) {
if (coa.
center.
equals(p
)) {
// two different centres are on the same Garmin point and they
// appear on different ways. We try hard to change them.
coa.
forceChange =
true;
}
}
}
}
}
/**
* remove obsolete points in ways. Obsolete are points which are
* very close to 180 degrees angles in the real line or wrong points.
* Wrong points are those that produce wrong angles, so that
* removing them reduces the error.
* @param modifiedRoads
*/
private void removeObsoletePoints
(Map<Long, ConvertedWay
> modifiedRoads
) {
ConvertedWay lastConvertedWay =
null;
int numPointsRemoved =
0;
boolean lastWasModified =
false;
List<Coord
> removedInWay =
new ArrayList<>();
List<Coord
> obsoletePoints =
new ArrayList<>();
List<Coord
> modifiedPoints =
new ArrayList<>();
for (ConvertedWay cw : convertedWays
) {
if (!cw.
isValid())
continue;
Way way = cw.
getWay();
if (lastConvertedWay
!=
null && way.
equals(lastConvertedWay.
getWay())) {
if (lastWasModified
) {
List<Coord
> points = way.
getPoints();
points.
clear();
points.
addAll(lastConvertedWay.
getPoints());
if (cw.
isReversed() != lastConvertedWay.
isReversed())
Collections.
reverse(points
);
}
continue;
}
lastConvertedWay = cw
;
lastWasModified =
false;
List<Coord
> points = way.
getPoints();
modifiedPoints.
clear();
double maxErrorDistance = calcMaxErrorDistance
(points.
get(0));
boolean draw =
false;
removedInWay.
clear();
modifiedPoints.
add(points.
get(0));
// scan through the way's points looking for points which are
// on almost straight line and therefore obsolete
for (int i =
1; i +
1 < points.
size(); i++
) {
Coord cm = points.
get(i
);
if (!allowedToRemove
(cm
)) {
modifiedPoints.
add(cm
);
continue;
}
Coord c1 = modifiedPoints.
get(modifiedPoints.
size() -
1);
Coord c2 = points.
get(i +
1);
if (c1 == c2
) {
// loop, handled by split routine
modifiedPoints.
add(cm
);
continue;
}
boolean keepThis =
true;
double realAngle = Utils.
getAngle(c1, cm, c2
);
if (Math.
abs(realAngle
) < MAX_DIFF_ANGLE_STRAIGHT_LINE
) {
double distance = cm.
distToLineSegment(c1, c2
);
if (distance
>= maxErrorDistance
) {
modifiedPoints.
add(cm
);
continue;
}
keepThis =
false;
} else {
double displayedAngle = Utils.
getDisplayedAngle(c1, cm, c2
);
if (displayedAngle
< 0 && realAngle
> 0 || displayedAngle
> 0 && realAngle
< 0) {
// straight line is closer to real angle
keepThis =
false;
} else if (Math.
abs(displayedAngle
) < 1) {
// displayed line is nearly straight
if (c1.
getHighwayCount() < 2 && c2.
getHighwayCount() < 2) {
// we can remove the point
keepThis =
false;
}
} else if (Math.
abs(realAngle - displayedAngle
) > 2 * Math.
abs(realAngle
)
&& Math.
abs(realAngle
) < MAX_BEARING_ERROR_HALF
) {
// displayed angle is much sharper than wanted, straight line is closer to real
// angle
keepThis =
false;
} else if (c1.
equals(c2
)) {
// spike / overlap
log.
debug("pass", pass,
"roads=" +
(cw.
isRoad()),
"extra remove to remove spike or overlap near", cm.
toDegreeString());
keepThis =
false;
}
}
if (keepThis
) {
modifiedPoints.
add(cm
);
continue;
}
if (log.
isDebugEnabled()) {
log.
debug("removing obsolete point on almost straight segment in way ", way.
toBrowseURL(),
"at",
cm.
toOSMURL());
}
if (DEBUG_PATH
!=
null) {
obsoletePoints.
add(cm
);
removedInWay.
add(cm
);
}
numPointsRemoved++
;
lastWasModified =
true;
}
if (lastWasModified
) {
modifiedPoints.
add(points.
get(points.
size() -
1));
points.
clear();
points.
addAll(modifiedPoints
);
if (cw.
isRoad())
modifiedRoads.
put(way.
getId(), cw
);
if (DEBUG_PATH
!=
null && (draw || cw.
isRoundabout())) {
GpxCreator.
createGpx(Utils.
joinPath(DEBUG_PATH, way.
getId() +
"_dpmod"), points, removedInWay
);
}
}
}
if (DEBUG_PATH
!=
null) {
GpxCreator.
createGpx(Utils.
joinPath(DEBUG_PATH,
"_obsolete"),
bbox.
toCoords(),
new ArrayList<>(obsoletePoints
));
}
log.
info("Removed", numPointsRemoved,
"obsolete points from lines");
}
/**
* debug code
* @param roads
*/
private void printBadAngles
(String name,
List<ConvertedWay
> roads
){
if (DEBUG_PATH ==
null)
return;
List<ConvertedWay
> badWays =
new ArrayList<>();
Way lastWay =
null;
List<Coord
> badAngles =
new ArrayList<>();
for (int w =
0; w
< roads.
size(); w++
) {
ConvertedWay cw = roads.
get(w
);
if (!cw.
isValid())
continue;
Way way = cw.
getWay();
if (way.
equals(lastWay
)) {
continue;
}
boolean hasBadAngles =
false;
lastWay = way
;
List<Coord
> points = way.
getPoints();
// scan through the way's points looking for points which are
// on almost straight line and therefore obsolete
for (int i = points.
size() -
2; i
>=
1; --i
) {
Coord cm = points.
get(i
);
Coord c1 = points.
get(i -
1);
Coord c2 = points.
get(i +
1);
if (c1 == c2
) {
// loop, handled by split routine
continue;
}
double realAngle = Utils.
getAngle(c1, cm, c2
);
double displayedAngle = Utils.
getDisplayedAngle(c1, cm, c2
);
if (Math.
abs(displayedAngle - realAngle
) > 30) {
badAngles.
add(cm
);
hasBadAngles =
true;
}
}
if (points.
size() > 2) {
Coord p0 = points.
get(0);
Coord plast = points.
get(points.
size() -
1);
if (p0 == plast
) {
Coord cm = points.
get(0);
Coord c1 = points.
get(points.
size() -
2);
Coord c2 = points.
get(1);
if (c1 == c2
) {
// loop, handled by split routine
continue;
}
double realAngle = Utils.
getAngle(c1, cm, c2
);
double displayedAngle = Utils.
getDisplayedAngle(c1, cm, c2
);
if (Math.
abs(displayedAngle - realAngle
) > 30) {
badAngles.
add(cm
);
hasBadAngles =
true;
}
}
}
if (hasBadAngles
)
badWays.
add(cw
);
}
GpxCreator.
createGpx(Utils.
joinPath(DEBUG_PATH, name
), bbox.
toCoords(),
new ArrayList<>(badAngles
));
writeOSM
(name, badWays
);
}
/**
* Check if the point can safely be removed.
* @param p
* @return true if remove is okay
*/
private static boolean allowedToRemove
(Coord p
) {
if (p.
getOnBoundary() || p.
getOnCountryBorder() || p.
isEndOfWay())
return false;
if (p
instanceof CoordPOI
&& ((CoordPOI
) p
).
isUsed())
return false;
return p.
getHighwayCount() < 2 && !p.
isViaNodeOfRestriction();
}
/**
* helper class
*/
private class CenterOfAngle
{
boolean forceChange
;
final Coord center
;
final List<CenterOfAngle
> neighbours
;
final int id
; // debugging aid
boolean wasMerged
;
List<CenterOfAngle
> badMergeCandidates
;
public CenterOfAngle
(Coord center,
int id
) {
this.
center = center
;
assert !center.
isReplaced();
this.
id = id
;
neighbours =
new ArrayList<>();
}
@
Override
public String toString
() {
return "CenterOfAngle [id=" + id +
" " + center.
toString() +
" " + center.
toDegreeString() +
", wasMerged="
+ wasMerged +
", num Neighbours=" + neighbours.
size() +
"]";
}
/**
* returns current center position or null if removed
* @param replacements
* @return
*/
public Coord getCurrentLocation
(Map<Coord, Coord
> replacements
) {
Coord c = getReplacement
(center,
null, replacements
);
if (c.
isToRemove())
return null;
return c
;
}
/**
* Add neighbour which should not be merged
* @param other
*/
public void addBadMergeCandidate
(CenterOfAngle other
) {
if (badMergeCandidates ==
null)
badMergeCandidates =
new ArrayList<>();
badMergeCandidates.
add(other
);
}
public void addNeighbour
(CenterOfAngle other
) {
if (this == other
) {
log.
error("neighbour is equal");
}
boolean isNew =
true;
// we want only different Coord instances here
for (CenterOfAngle neighbour : neighbours
) {
if (neighbour == other
) {
isNew =
false;
break;
}
}
if (isNew
)
neighbours.
add(other
);
}
/**
*
* @param replacements
* @return false if this needs changes
*/
public boolean isOK
(Map<Coord, Coord
> replacements
) {
if (forceChange
)
return false;
Coord c = getCurrentLocation
(replacements
);
if (c ==
null)
return true; // removed center: nothing to do
for (CenterOfAngle neighbour : neighbours
) {
Coord n = neighbour.
getCurrentLocation(replacements
);
if (n ==
null)
continue; // skip removed neighbours
double err = calcBearingError
(c, n
);
if (err
>= MAX_BEARING_ERROR
)
return false;
}
return true;
}
private void replaceCoord
(Coord toRepl, Coord replacement,
Map<Coord, Coord
> replacements
) {
assert toRepl
!= replacement
;
if (toRepl.
getOnBoundary()) {
if (!replacement.
equals(toRepl
)) {
log.
error("boundary node is replaced by node with non-equal coordinates at", toRepl.
toOSMURL());
assert false :
"boundary node is replaced";
}
replacement.
setOnBoundary(true);
}
if (toRepl.
getOnCountryBorder()) {
if (!replacement.
equals(toRepl
)) {
log.
warn("country boundary node is replaced by node with non-equal coordinates at",
toRepl.
toOSMURL());
}
replacement.
setOnCountryBorder(true);
}
toRepl.
setReplaced(true);
if (toRepl
instanceof CoordPOI
) {
CoordPOI cp =
(CoordPOI
) toRepl
;
if (cp.
isUsed() ) {
replacement =
new CoordPOI
(replacement
);
((CoordPOI
) replacement
).
setNode(cp.
getNode());
((CoordPOI
) replacement
).
setUsed(true);
((CoordPOI
) replacement
).
setConvertToViaInRouteRestriction(cp.
getConvertToViaInRouteRestriction());
if (!replacement.
highPrecEquals(cp.
getNode().
getLocation())) {
log.
error("CoordPOI node is replaced with non-equal coordinates at", toRepl.
toOSMURL());
}
}
}
if (toRepl.
isViaNodeOfRestriction())
replacement.
setViaNodeOfRestriction(true);
replacements.
put(toRepl, replacement
);
while (toRepl.
getHighwayCount() > replacement.
getHighwayCount()) {
replacement.
incHighwayCount();
}
if (toRepl.
isEndOfWay()) {
replacement.
setEndOfWay(true);
}
}
/**
* Try whether a move or remove or merge of this centre
* fixes bearing problems.
* @param replacements
* @param tryAlsoMerge true means merge is allowed
* @return true if something was changed
*/
public boolean tryChange
(Map<Coord, Coord
> replacements,
boolean tryAlsoMerge
) {
if (wasMerged
) {
return false;
}
Coord currentCenter = getCurrentLocation
(replacements
);
if (currentCenter ==
null)
return false; // cannot modify removed centre
CenterOfAngle worstNeighbour =
null;
Coord worstNP =
null;
double initialMaxError =
0;
double initialSumErr =
0;
HashSet<Coord
> dupCheck =
new HashSet<>();
boolean hasDups =
false;
for (CenterOfAngle neighbour : neighbours
) {
Coord n = neighbour.
getCurrentLocation(replacements
);
if (n ==
null)
return false; // neighbour was removed
if (!dupCheck.
add(n
)) {
hasDups =
true;
}
if (currentCenter.
highPrecEquals(n
)) {
if (currentCenter == n
) {
log.
error(id +
": bad neighbour " + neighbour.
id +
" zero distance");
}
if (badMergeCandidates
!=
null && badMergeCandidates.
contains(neighbour
)
|| neighbour.
badMergeCandidates !=
null && neighbour.
badMergeCandidates.
contains(this)) {
// not allowed to merge
} else {
replaceCoord
(currentCenter, n, replacements
);
neighbour.
wasMerged = wasMerged =
true;
return true;
}
}
double err = calcBearingError
(currentCenter, n
);
if (err
!=
Double.
MAX_VALUE)
initialSumErr += err
;
if (err
> initialMaxError
){
initialMaxError = err
;
worstNeighbour = neighbour
;
worstNP = n
;
}
}
if (initialMaxError
< MAX_BEARING_ERROR
)
return false;
double removeErr = calcRemoveError
(replacements
);
if (removeErr ==
0) {
currentCenter.
setRemove(true);
return true;
}
if (hasDups
) {
if (extraPass
&& tryAlsoMerge
&& currentCenter.
getHighwayCount() > 1) {
// spike
List<Coord
> altPositions = currentCenter.
getAlternativePositions();
for (Coord altCenter : altPositions
) {
if (dupCheck.
contains(altCenter
)) {
log.
debug("pass", pass,
"extra move to remove spike or overlap near", currentCenter.
toDegreeString());
replaceCoord
(currentCenter, altCenter, replacements
);
return true;
}
}
}
// two or more neighbours are on the same Garmin point.
// Better improve one of them.
return false;
}
if (initialMaxError ==
Double.
MAX_VALUE)
initialSumErr = initialMaxError
;
double bestReplErr = initialMaxError
;
Coord bestCenterReplacement =
null;
List<Coord
> altPositions = currentCenter.
getAlternativePositions();
for (Coord altCenter : altPositions
) {
double err = calcBearingError
(altCenter, worstNP
);
if (err
>= bestReplErr
)
continue;
// alt. position is improvement, check all neighbours
double errMax = calcMaxError
(replacements, currentCenter, altCenter
);
if (errMax
< initialMaxError
) {
bestReplErr = err
;
bestCenterReplacement = altCenter
;
}
}
Coord bestNeighbourReplacement =
null;
// calculate effect when both this and the worst neighbour are changed.
if (worstNP.
hasAlternativePos()) {
for (Coord altCenter : altPositions
) {
replaceCoord
(currentCenter, altCenter, replacements
);
for (Coord altN : worstNP.
getAlternativePositions()) {
double err = calcBearingError
(altCenter, altN
);
if (err
>= bestReplErr
)
continue;
double errNeighbour = worstNeighbour.
calcMaxError(replacements, worstNP, altN
);
if (errNeighbour
< bestReplErr
) {
bestReplErr = err
;
bestCenterReplacement = altCenter
;
bestNeighbourReplacement = altN
;
}
}
replacements.
remove(currentCenter
);
currentCenter.
setReplaced(false);
}
}
boolean specialChange =
false;
if (extraPass
&& bestReplErr
>= MAX_BEARING_ERROR
&& bestCenterReplacement
!=
null
&& bestReplErr
* 2 < initialMaxError
&& initialMaxError
< 180) {
specialChange =
true;
}
if (bestReplErr
< MAX_BEARING_ERROR || specialChange
) {
if (removeErr
< bestReplErr
&& initialMaxError - removeErr
>= MAX_BEARING_ERROR_HALF
&& removeErr
< MAX_BEARING_ERROR_HALF
) {
bestCenterReplacement =
null;
}
if (bestCenterReplacement
!=
null) {
replaceCoord
(currentCenter, bestCenterReplacement, replacements
);
if (bestNeighbourReplacement
!=
null)
replaceCoord
(worstNP, bestNeighbourReplacement, replacements
);
double modifiedSumErr = calcSumOfErrors
(replacements
);
if (modifiedSumErr
< initialSumErr
) {
if (specialChange
)
log.
debug("pass", pass,
"special repl",
this);
return true;
}
// revert changes
replacements.
remove(currentCenter
);
currentCenter.
setReplaced(false);
replacements.
remove(worstNP
);
worstNP.
setReplaced(false);
}
}
if (removeErr
< MAX_BEARING_ERROR
) {
// createGPX(gpxPath+id+"_rem", replacements);
currentCenter.
setRemove(true);
return true;
}
if (!tryAlsoMerge
)
return false;
double dist = currentCenter.
distance(worstNP
);
double maxDist = calcMaxErrorDistance
(currentCenter
) * 2;
if (dist
< maxDist ||
this.
neighbours.
size() ==
3 && worstNeighbour.
neighbours.
size() ==
3)
return tryMerge
(initialMaxError, worstNeighbour, replacements
);
return false;
}
/**
* Calculate error when two centres are merged. If they are not equal
* and the error is too big, nothing is changed and false is returned.
*
* @param initialMaxError max. bearing error of this centre
* @param neighbour neighbour to merge
* @param replacements
* @return true if merge is okay
*/
private boolean tryMerge
(double initialMaxError, CenterOfAngle neighbour,
Map<Coord, Coord
> replacements
) {
if (badMergeCandidates
!=
null && badMergeCandidates.
contains(neighbour
)
|| neighbour.
badMergeCandidates !=
null && neighbour.
badMergeCandidates.
contains(this)) {
return false; // not allowed to merge
}
Coord c = getCurrentLocation
(replacements
);
Coord n = neighbour.
getCurrentLocation(replacements
);
// check special cases: don't merge if
// 1) both points are via nodes
// 2) both nodes are boundary nodes with non-equal coords
// 3) one point is via node and the other is a boundary node, the result could be that the restriction is ignored.
if (c.
getOnBoundary() && (n.
isViaNodeOfRestriction() ||
(n.
getOnBoundary() && !c.
equals(n
)))
||
(c.
isViaNodeOfRestriction() && (n.
isViaNodeOfRestriction() || n.
getOnBoundary()))
||
(c
instanceof CoordPOI
&& (n
instanceof CoordPOI || n.
getOnBoundary()))
||
(n
instanceof CoordPOI
&& (c
instanceof CoordPOI || c.
getOnBoundary())))
return false;
Coord mergePoint
;
if (c.
getOnBoundary() || c
instanceof CoordPOI
)
mergePoint = c
;
else if (n.
getOnBoundary() || n
instanceof CoordPOI
)
mergePoint = n
;
else if (c.
equals(n
))
mergePoint = c
;
else
mergePoint = c.
makeBetweenPoint(n,
0.5);
double err =
0;
if (!c.
equals(n
)) {
err = calcMergeErr
(neighbour, mergePoint, replacements
);
if (err ==
Double.
MAX_VALUE && initialMaxError ==
Double.
MAX_VALUE) {
log.
warn("still equal neighbour after merge", c.
toOSMURL());
} else {
if (err
>= MAX_BEARING_ERROR
)
return false;
if (initialMaxError - err
< MAX_BEARING_ERROR_HALF
&& err
> MAX_BEARING_ERROR_HALF
) {
return false; // improvement too small
}
}
// merge only if the merged line is part of a (nearly) straight line going through both centres,
if (!checkNearlyStraight
(c.
bearingTo(n
), neighbour, replacements
)
||
!neighbour.
checkNearlyStraight(n.
bearingTo(c
),
this, replacements
)) {
// createGPX(gpxPath + "no_more_merge_" + id, replacements);
// neighbour.createGPX(gpxPath + "no_more_merge_" + neighbour.id, replacements);
// System.out.println("no_merge at " + mergePoint.toDegreeString() + " " + mergePoint.toOSMURL() + " at " + id);
return false;
}
}
int hwc = c.
getHighwayCount() + n.
getHighwayCount() -
1;
for (int i = mergePoint.
getHighwayCount(); i
< hwc
; i++
) {
mergePoint.
incHighwayCount();
}
if (c
!= mergePoint
)
replaceCoord
(c, mergePoint, replacements
);
if (n
!= mergePoint
) {
replaceCoord
(n, mergePoint, replacements
);
}
// createGPX(gpxPath+id+"_merged", replacements);
// neighbour.createGPX(gpxPath+neighbour.id+"_merged_w_"+id, replacements);
neighbour.
wasMerged = wasMerged =
true;
return true;
}
/**
* Try to find a line that builds a nearly straight line
* with the connection to an other centre.
* @param bearing bearing of the connection to the other centre
* @param other the other centre
* @param replacements s
* @return true if a nearly straight line exists
*/
private boolean checkNearlyStraight
(double bearing, CenterOfAngle other,
Map<Coord, Coord
> replacements
) {
Coord c = getCurrentLocation
(replacements
);
for (CenterOfAngle neighbour : neighbours
) {
if (neighbour == other
)
continue;
Coord n = neighbour.
getCurrentLocation(replacements
);
if (n
!=
null) {
double bearing2 = c.
bearingTo(n
);
double angle = bearing2 -
(bearing -
180);
while (angle
> 180)
angle -=
360;
while (angle
< -
180)
angle +=
360;
if (Math.
abs(angle
) < 10) // tolerate small angle
return true;
}
}
return false;
}
/**
* Calculate max. error of this merged with other centres.
* @param other the other centre
* @param mergePoint the point which should be used as a new centre for both
* @param replacements
* @return the error
*/
private double calcMergeErr
(CenterOfAngle other, Coord mergePoint,
Map<Coord, Coord
> replacements
) {
double maxErr =
0;
for (CenterOfAngle neighbour : neighbours
) {
if (neighbour == other
)
continue;
Coord n = neighbour.
getCurrentLocation(replacements
);
if (n
!=
null) {
double err = calcBearingError
(mergePoint, n
);
if (err
> maxErr
)
maxErr = err
;
}
}
for (CenterOfAngle othersNeighbour : other.
neighbours) {
if (othersNeighbour ==
this)
continue;
Coord n = othersNeighbour.
getCurrentLocation(replacements
);
if (n
!=
null) {
double err = calcBearingError
(mergePoint, n
);
if (err
> maxErr
)
maxErr = err
;
}
}
return maxErr
;
}
/**
* Calculate max. bearing error of centre point to all neighbours.
* @param replacements
* @param toRepl if centre or a neighbour center is identical to this, use replacement instead
* @param replacement see toRepl
* @return error [0..180] or Double.MAX_VALUE in case of equal points
*/
private double calcMaxError
(Map<Coord, Coord
> replacements, Coord toRepl, Coord replacement
) {
double maxErr =
0;
Coord c = getCurrentLocation
(replacements
);
for (CenterOfAngle neighbour : neighbours
) {
Coord n = neighbour.
getCurrentLocation(replacements
);
if (n ==
null)
continue; // neighbour was removed
double err
;
if (c == toRepl
)
err = calcBearingError
(replacement, n
);
else if (n == toRepl
)
err = calcBearingError
(c, replacement
);
else
err = calcBearingError
(c, n
);
if (err ==
Double.
MAX_VALUE)
return err
;
if (err
> maxErr
)
maxErr = err
;
}
return maxErr
;
}
/**
* Calculate sum of errors for a centre.
* @param replacements
* @return
*/
private double calcSumOfErrors
(Map<Coord, Coord
> replacements
) {
double sumErr =
0;
Coord c = getCurrentLocation
(replacements
);
for (CenterOfAngle neighbour : neighbours
) {
Coord n = neighbour.
getCurrentLocation(replacements
);
if (n ==
null)
continue; // skip removed neighbour
double err = calcBearingError
(c, n
);
if (err ==
Double.
MAX_VALUE)
return err
;
sumErr += err
;
}
return sumErr
;
}
/**
* Calculate error for a removed centre.
* @param replacements
* @return Double.MAX_VALUE if centre must not be deleted, else [0..180]
*/
private double calcRemoveError
(Map<Coord, Coord
> replacements
) {
if (!allowedToRemove
(center
))
return Double.
MAX_VALUE;
if (neighbours.
size() > 2)
return Double.
MAX_VALUE;
Coord c = getCurrentLocation
(replacements
);
Coord
[] outerPoints =
new Coord
[neighbours.
size()];
for (int i =
0; i
< neighbours.
size(); i++
) {
CenterOfAngle neighbour = neighbours.
get(i
);
Coord n = neighbour.
getCurrentLocation(replacements
);
if (n ==
null)
return Double.
MAX_VALUE;
if (c.
equals(n
)) {
if (!allowedToRemove
(neighbour.
center)
|| c.
getDistToDisplayedPoint() >= n.
getDistToDisplayedPoint()) {
return 0;
}
return Double.
MAX_VALUE;
}
outerPoints
[i
] = n
;
}
if (neighbours.
size() < 2)
return Double.
MAX_VALUE;
for (int i =
0; i
< neighbours.
size(); i++
) {
if (2 * c.
getDistToDisplayedPoint() < outerPoints
[i
].
getDistToDisplayedPoint()) {
return Double.
MAX_VALUE;
}
}
double dsplAngle = Utils.
getDisplayedAngle(outerPoints
[0], c, outerPoints
[1]);
if (Math.
abs( dsplAngle
) < 3)
return Double.
MAX_VALUE;
double realAngle = Utils.
getAngle(outerPoints
[0], c, outerPoints
[1]);
return Math.
abs(realAngle
) /
2;
}
@
SuppressWarnings("unused")
private void createGPX
(String gpxName,
Map<Coord, Coord
> replacements
) {
if (DEBUG_PATH ==
null || gpxName ==
null)
return;
if (gpxName.
isEmpty())
gpxName = Utils.
joinPath(DEBUG_PATH, id +
"_no_info");
// print lines after change
Coord c = getReplacement
(center,
null, replacements
);
List<Coord
> alternatives = c.
getAlternativePositions();
for (int i =
0; i
< neighbours.
size(); i++
) {
CenterOfAngle n = neighbours.
get(i
);
Coord nc = getReplacement
(n.
center,
null, replacements
);
if (nc ==
null)
continue; // skip removed neighbour
if (i ==
0 && !alternatives.
isEmpty()) {
GpxCreator.
createGpx(gpxName +
"_" + i,
Arrays.
asList(c, nc
), alternatives
);
} else {
GpxCreator.
createGpx(gpxName +
"_" + i,
Arrays.
asList(c, nc
));
}
}
if (neighbours.
isEmpty()) {
GpxCreator.
createGpx(gpxName +
"_empty",
Arrays.
asList(c, c
), alternatives
);
}
}
}
private void writeOSM
(String name,
List<ConvertedWay
> convertedWays
) {
if (DEBUG_PATH
!=
null) {
//TODO: comment before release
// uk.me.parabola.mkgmap.osmstyle.optional.DebugWriter.writeOSM(bbox, DEBUG_PATH, name, convertedWays);
}
}
private static double calcBearingError
(Coord p1, Coord p2
) {
if (p1.
equals(p2
) || p1.
highPrecEquals(p2
)) {
return Double.
MAX_VALUE;
}
double realBearing = p1.
bearingTo(p2
);
double displayedBearing = p1.
getDisplayedCoord().
bearingTo(p2.
getDisplayedCoord());
double err = displayedBearing - realBearing
;
while (err
> 180)
err -=
360;
while (err
< -
180)
err +=
360;
return Math.
abs(err
);
}
/**
* Calculate the rounding error tolerance for a given point.
* The latitude error may be max higher. Maybe this should be
* @param p0
* @return the rounding error tolerance for a given point
*/
private static double calcMaxErrorDistance
(Coord p0
) {
Coord test =
new Coord
(p0.
getLatitude(), p0.
getLongitude() +
1);
return p0.
getDisplayedCoord().
distance(test
) /
2;
}
/**
* Remove obsolete points on straight lines and spikes
* and some wrong angles caused by rounding errors.
* TODO: optimise by moving
* @param points list of coordinates that form a shape
* @return reduced list
*/
public static List<Coord
> fixAnglesInShape
(List<Coord
> points
) {
List<Coord
> modifiedPoints =
new ArrayList<>(points.
size());
double maxErrorDistance = calcMaxErrorDistance
(points.
get(0));
int n = points.
size();
// scan through the way's points looking for points which are
// on almost straight line and therefore obsolete
for (int i =
0; i +
1 < points.
size(); i++
) {
Coord c1
;
if (!modifiedPoints.
isEmpty()) {
c1 = modifiedPoints.
get(modifiedPoints.
size() -
1);
} else {
c1 =
(i
> 0) ? points.
get(i -
1) : points.
get(n -
2);
}
Coord cm = points.
get(i
);
if (cm.
highPrecEquals(c1
)) {
if (modifiedPoints.
size() > 1) {
modifiedPoints.
remove(modifiedPoints.
size() -
1);
c1 = modifiedPoints.
get(modifiedPoints.
size() -
1); // might be part of spike
} else {
if (modifiedPoints.
isEmpty()) {
modifiedPoints.
add(c1
);
}
continue;
}
}
Coord c2 = points.
get(i +
1);
int straightTest = Utils.
isHighPrecStraight(c1, cm, c2
);
if (straightTest == Utils.
STRICTLY_STRAIGHT || straightTest == Utils.
STRAIGHT_SPIKE) {
continue;
}
double realAngle = Utils.
getAngle(c1, cm, c2
);
if (Math.
abs(realAngle
) < MAX_DIFF_ANGLE_STRAIGHT_LINE
) {
double distance = cm.
distToLineSegment(c1, c2
);
if (distance
< maxErrorDistance
)
continue;
}
modifiedPoints.
add(cm
);
}
if (modifiedPoints.
size() > 1 && modifiedPoints.
get(0) != modifiedPoints.
get(modifiedPoints.
size() -
1))
modifiedPoints.
add(modifiedPoints.
get(0));
return modifiedPoints
;
}
/**
* Use Douglas-Peucker Filter with a very small allowed distance so obsolete points are removed before the
* complex angle calculations. This helps especially for heavily over-sampled ways where many points are used to build
* circular ways.
* @param convertedWays list of ways to filter
* @param modifiedRoads if ways are routable we add the modified ways to this map
*/
private void prepWithDouglasPeucker
(Map<Long, ConvertedWay
> modifiedRoads
) {
// we don't want to remove end points of ways
markEndPoints
(convertedWays,
true);
double maxErrorDistance =
0.05;
Way lastWay =
null;
for (ConvertedWay cw : convertedWays
) {
if (!cw.
isValid() || cw.
getWay().
equals(lastWay
))
continue;
Way way = cw.
getWay();
lastWay = way
;
List<Coord
> points = way.
getPoints();
List<Coord
> coords =
new ArrayList<>(points
);
// Loop runs downwards, as the list length gets modified while
// running
int endIndex = coords.
size() -
1;
for (int i = endIndex -
1; i
> 0; i--
) {
Coord p = coords.
get(i
);
// If a point has to be kept in the line use the douglas peucker algorithm for
// upper segment
if (!allowedToRemove
(p
)) {
// point is "preserved", don't remove it
DouglasPeuckerFilter.
douglasPeucker(coords, i, endIndex, maxErrorDistance
);
endIndex = i
;
}
}
// Simplify the rest
DouglasPeuckerFilter.
douglasPeucker(coords,
0, endIndex, maxErrorDistance
);
if (coords.
size() != points.
size()) {
if (cw.
isRoad()) {
modifiedRoads.
put(way.
getId(), cw
);
}
points.
clear();
points.
addAll(coords
);
}
}
markEndPoints
(convertedWays,
false);
}
private static void markEndPoints
(List<ConvertedWay
> convertedWays,
boolean b
) {
Way lastWay =
null;
for (ConvertedWay cw : convertedWays
) {
if (!cw.
isValid() || cw.
getWay().
equals(lastWay
))
continue;
Way way = cw.
getWay();
lastWay = way
;
way.
getFirstPoint().
setEndOfWay(b
);
way.
getLastPoint().
setEndOfWay(b
);
}
}
private static String getUsableId
(Way w
) {
return "Way " +
(FakeIdGenerator.
isFakeId(w.
getId()) ? " generated from " :
" ") + w.
getOriginalId();
}
}