WebSVN - mkgmap - Rev 4246 - /branches/default-typ/src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java

/*
* Copyright (C) 2011-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.reader.osm;

import java.awt.Polygon;
import java.awt.Rectangle;
import java.awt.geom.Area;
import java.awt.geom.Line2D;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.ListIterator;
import java.util.Locale;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.logging.Level;

import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.log.Logger;
import uk.me.parabola.util.Java2DConverter;

/**
* Representation of an OSM Multipolygon Relation.<br/>
* The different way of the multipolygon are joined to polygons and inner
* polygons are cut out from the outer polygons.
*
* @author WanMil
*/
public class MultiPolygonRelation extends Relation {
private static final Logger log = Logger.getLogger(MultiPolygonRelation.class);

public static final String STYLE_FILTER_TAG = "mkgmap:stylefilter";
public static final String STYLE_FILTER_LINE = "polyline";
public static final String STYLE_FILTER_POLYGON = "polygon";

/** A tag that is set with value true on each polygon that is created by the mp processing */
public static final String MP_CREATED_TAG = "mkgmap:mp_created";

private final Map<Long, Way> tileWayMap;
private final Map<Long, String> roleMap = new HashMap<>();

private Map<Long, Way> mpPolygons = new LinkedHashMap<>();

protected ArrayList<BitSet> containsMatrix;
protected ArrayList<JoinedWay> polygons;
protected Set<JoinedWay> intersectingPolygons;

protected double largestSize;
protected JoinedWay largestOuterPolygon;

protected Set<Way> outerWaysForLineTagging;
protected Map<String, String> outerTags;

private final uk.me.parabola.imgfmt.app.Area tileBounds;
private Area tileArea;

private Coord cOfG = null;

// the sum of all outer polygons area size
private double mpAreaSize = 0;

/**
* A point that has a lower or equal squared distance from
* a line is treated as if it lies one the line.<br/>
* 1.0d is very exact. 2.0d covers rounding problems when converting
* OSM locations to mkgmap internal format. A larger value
* is more tolerant against imprecise OSM data.
*/
private static final double OVERLAP_TOLERANCE_DISTANCE = 2.0d;

/**
* Create an instance based on an existing relation. We need to do this
* because the type of the relation is not known until after all its tags
* are read in.
*
* @param other
* The relation to base this one on.
* @param wayMap
* Map of all ways.
* @param bbox
* The bounding box of the tile
*/
public MultiPolygonRelation(Relation other, Map<Long, Way> wayMap,
uk.me.parabola.imgfmt.app.Area bbox) {
this.tileWayMap = wayMap;
this.tileBounds = bbox;
// create an Area for the bbox to clip the polygons
tileArea = Java2DConverter.createBoundsArea(tileBounds);

setId(other.getId());
copyTags(other);
this.setTagsIncomplete(other.getTagsIncomplete());

if (log.isDebugEnabled()) {
log.debug("Construct multipolygon", toBrowseURL(), toTagString());
}

for (Map.Entry<String, Element> pair : other.getElements()) {
String role = pair.getKey();
Element el = pair.getValue();
if (log.isDebugEnabled()) {
log.debug(" ", role, el.toBrowseURL(), el.toTagString());
}
if (roleMap.containsKey(el.getId()) )
log.warn("repeated member with id ", el.getId(), "in multipolygon relation",this.getId(),"is ignored");
else {
addElement(role, el);
roleMap.put(el.getId(), role);
}
}
}

/**
* Retrieves the center point of this multipolygon. This is set in the
* {@link #processElements()} methods so it returns <code>null</code>
* before that. It can also return <code>null</code> in case the
* multipolygon could not be processed.<br/>
* The returned point may lie outside the multipolygon area. It is just
* the center point of it.
*
* @return the center point of this multipolygon (maybe <code>null</code>)
*/
public Coord getCofG() {
return cOfG;
}

/**
* Retrieves the mp role of the given element.
*
* @param element
* the element
* @return the role of the element
*/
protected String getRole(Element element) {
String role = roleMap.get(element.getId());
if (role != null && ("outer".equals(role) || "inner".equals(role))) {
return role;
}

return null;
}

/**
* Try to join the two ways.
*
* @param joinWay
* the way to which tempWay is added in case both ways could be
* joined and checkOnly is false.
* @param tempWay
* the way to be added to joinWay
* @param checkOnly
* <code>true</code> checks only and does not perform the join
* operation
* @return <code>true</code> if tempWay way is (or could be) joined to
* joinWay
*/
private static boolean joinWays(JoinedWay joinWay, JoinedWay tempWay, boolean checkOnly) {
boolean reverseTempWay = false;
int insIdx = -1;
int firstTmpIdx = 1;
boolean joinable = false;

// use == or equals as comparator??
if (joinWay.getPoints().get(0) == tempWay.getPoints().get(0)) {
insIdx = 0;
reverseTempWay = true;
firstTmpIdx = 1;
joinable = true;
} else if (joinWay.getPoints().get(joinWay.getPoints().size() - 1) == tempWay
.getPoints().get(0)) {
insIdx = joinWay.getPoints().size();
reverseTempWay = false;
firstTmpIdx = 1;
joinable = true;
} else if (joinWay.getPoints().get(0) == tempWay.getPoints().get(
tempWay.getPoints().size() - 1)) {
insIdx = 0;
reverseTempWay = false;
firstTmpIdx = 0;
joinable = true;
} else if (joinWay.getPoints().get(joinWay.getPoints().size() - 1) == tempWay
.getPoints().get(tempWay.getPoints().size() - 1)) {
insIdx = joinWay.getPoints().size();
reverseTempWay = true;
firstTmpIdx = 0;
joinable = true;
}

if (!checkOnly && joinable){
int lastIdx = tempWay.getPoints().size();
if (firstTmpIdx == 0) {
// the last temp point is already contained in the joined way - do not copy it
lastIdx--;
}

List<Coord> tempCoords = tempWay.getPoints().subList(firstTmpIdx,lastIdx);

if (reverseTempWay) {
// the remp coords need to be reversed so copy the list
tempCoords = new ArrayList<>(tempCoords);
// and reverse it
Collections.reverse(tempCoords);
}

joinWay.getPoints().addAll(insIdx, tempCoords);
joinWay.addWay(tempWay);
}
return joinable;
}

/**
* Combine a list of way segments to a list of maximally joined ways
*
* @param segments
* a list of closed or unclosed ways
* @return a list of closed ways
*/
protected ArrayList<JoinedWay> joinWays(List<Way> segments) {
// TODO check if the closed polygon is valid and implement a
// backtracking algorithm to get other combinations

ArrayList<JoinedWay> joinedWays = new ArrayList<>();
if (segments == null || segments.isEmpty()) {
return joinedWays;
}

// go through all segments and categorize them to closed and unclosed
// list
ArrayList<JoinedWay> unclosedWays = new ArrayList<>();
for (Way orgSegment : segments) {
JoinedWay jw = new JoinedWay(orgSegment);
roleMap.put(jw.getId(), getRole(orgSegment));
if (orgSegment.isClosed()) {
if (orgSegment.isComplete() == false) {
// the way is closed in planet but some points are missing in this tile
// we can close it artificially
if (log.isDebugEnabled())
log.debug("Close incomplete but closed polygon:",orgSegment);
jw.closeWayArtificially();
}
assert jw.hasIdenticalEndPoints() : "way is not closed";
joinedWays.add(jw);
} else {
unclosedWays.add(jw);
}
}

while (!unclosedWays.isEmpty()) {
JoinedWay joinWay = unclosedWays.remove(0);

// check if the current way is already closed or if it is the last
// way
if (joinWay.hasIdenticalEndPoints() || unclosedWays.isEmpty()) {
joinedWays.add(joinWay);
continue;
}

boolean joined = false;

// if we have a way that could be joined but which has a wrong role
// then store it here and check in the end if it's working
JoinedWay wrongRoleWay = null;
String joinRole = getRole(joinWay);

// go through all ways and check if there is a way that can be
// joined with it
// in this case join the two ways
// => add all points of tempWay to joinWay, remove tempWay and put
// joinWay to the beginning of the list
// (not optimal but understandable - can be optimized later)
for (JoinedWay tempWay : unclosedWays) {
if (tempWay.hasIdenticalEndPoints()) {
continue;
}

String tempRole = getRole(tempWay);
// if a role is not 'inner' or 'outer' then it is used as
// universal
// check if the roles of the ways are matching
if ((!"outer".equals(joinRole) && !"inner"
.equals(joinRole))
|| (!"outer".equals(tempRole) && !"inner"
.equals(tempRole))
|| (joinRole != null && joinRole.equals(tempRole))) {
// the roles are matching => try to join both ways
joined = joinWays(joinWay, tempWay, false);
} else {
// the roles are not matching => test if both ways would
// join

// as long as we don't have an alternative way with wrong
// role
// or if the alternative way is shorter then check if
// the way with the wrong role could be joined
if (wrongRoleWay == null
|| wrongRoleWay.getPoints().size() < tempWay
.getPoints().size()) {
if (joinWays(joinWay, tempWay, true)) {
// save this way => maybe we will use it in the end
// if we don't find any other way
wrongRoleWay = tempWay;
}
}
}

if (joined) {
// we have joined the way
unclosedWays.remove(tempWay);
break;
}
}

if (!joined && wrongRoleWay != null) {

log.warn("Join ways with different roles. Multipolygon: "
+ toBrowseURL());
log.warn("Way1 Role:", getRole(joinWay));
logWayURLs(Level.WARNING, "-", joinWay);
log.warn("Way2 Role:", getRole(wrongRoleWay));
logWayURLs(Level.WARNING, "-", wrongRoleWay);

joined = joinWays(joinWay, wrongRoleWay, false);
if (joined) {
// we have joined the way
unclosedWays.remove(wrongRoleWay);
break;
}
}

if (joined) {
if (joinWay.hasIdenticalEndPoints()) {
// it's closed => don't process it again
joinedWays.add(joinWay);
} else if (unclosedWays.isEmpty()) {
// no more ways to join with
// it's not closed but we cannot join it more
joinedWays.add(joinWay);
} else {
// it is not yet closed => process it once again
unclosedWays.add(0, joinWay);
}
} else {
// it's not closed but we cannot join it more
joinedWays.add(joinWay);
}
}

return joinedWays;
}

/**
* Try to close all unclosed ways in the given list of ways.
*
* @param wayList
* a list of ways
*/
protected void closeWays(ArrayList<JoinedWay> wayList, double maxCloseDist) {
for (JoinedWay way : wayList) {
if (way.hasIdenticalEndPoints() || way.getPoints().size() < 3) {
continue;
}
Coord p1 = way.getPoints().get(0);
Coord p2 = way.getPoints().get(way.getPoints().size() - 1);

if (tileBounds.insideBoundary(p1) == false
&& tileBounds.insideBoundary(p2) == false) {
// both points lie outside the bbox or on the bbox

// check if both points are on the same side of the bounding box
if ((p1.getLatitude() <= tileBounds.getMinLat() && p2.getLatitude() <= tileBounds
.getMinLat())
|| (p1.getLatitude() >= tileBounds.getMaxLat() && p2
.getLatitude() >= tileBounds.getMaxLat())
|| (p1.getLongitude() <= tileBounds.getMinLong() && p2
.getLongitude() <= tileBounds.getMinLong())
|| (p1.getLongitude() >= tileBounds.getMaxLong() && p2
.getLongitude() >= tileBounds.getMaxLong())) {
// they are on the same side outside of the bbox
// so just close them without worrying about if
// they intersect itself because the intersection also
// is outside the bbox
way.closeWayArtificially();
log.info("Endpoints of way", way,
"are both outside the bbox. Closing it directly.");
continue;
}
}

Line2D closingLine = new Line2D.Float(p1.getLongitude(), p1
.getLatitude(), p2.getLongitude(), p2.getLatitude());

boolean intersects = false;
Coord lastPoint = null;
// don't use the first and the last point
// the closing line can intersect only in one point or complete.
// Both isn't interesting for this check
for (Coord thisPoint : way.getPoints().subList(1,
way.getPoints().size() - 1)) {
if (lastPoint != null) {
if (closingLine.intersectsLine(lastPoint.getLongitude(),
lastPoint.getLatitude(), thisPoint.getLongitude(),
thisPoint.getLatitude())) {
intersects = true;
break;
}
}
lastPoint = thisPoint;
}

if (!intersects) {
// close the polygon
// the new way segment does not intersect the rest of the polygon
boolean doClose = true;
if (maxCloseDist > 0) {
// calc the distance to close
double closeDist = way.getPoints().get(0).distance(way.getPoints().get(way.getPoints().size()-1));
doClose = closeDist < maxCloseDist;
}
if (doClose) {
log.info("Closing way", way);
log.info("from", way.getPoints().get(0).toOSMURL());
log.info("to", way.getPoints().get(way.getPoints().size() - 1)
.toOSMURL());
// mark this ways as artificially closed
way.closeWayArtificially();
}
}
}
}

protected static class ConnectionData {
public Coord c1;
public Coord c2;
public JoinedWay w1;
public JoinedWay w2;
// sometimes the connection of both points cannot be done directly but with an intermediate point
public Coord imC;
public double distance;

public ConnectionData() {

}
}

protected boolean connectUnclosedWays(List<JoinedWay> allWays) {
List<JoinedWay> unclosed = new ArrayList<>();

for (JoinedWay w : allWays) {
if (w.hasIdenticalEndPoints() == false) {
unclosed.add(w);
}
}
// try to connect ways lying outside or on the bbox
if (unclosed.size() >= 2) {
log.debug("Checking",unclosed.size(),"unclosed ways for connections outside the bbox");
Map<Coord, JoinedWay> outOfBboxPoints = new IdentityHashMap<>();

// check all ways for endpoints outside or on the bbox
for (JoinedWay w : unclosed) {
Coord c1 = w.getPoints().get(0);
Coord c2 = w.getPoints().get(w.getPoints().size()-1);
if (tileBounds.insideBoundary(c1)==false) {
log.debug("Point",c1,"of way",w.getId(),"outside bbox");
outOfBboxPoints.put(c1, w);
}

if (tileBounds.insideBoundary(c2)==false) {
log.debug("Point",c2,"of way",w.getId(),"outside bbox");
outOfBboxPoints.put(c2, w);
}
}

if (outOfBboxPoints.size() < 2) {
log.debug(outOfBboxPoints.size(),"point outside the bbox. No connection possible.");
return false;
}

List<ConnectionData> coordPairs = new ArrayList<>();
ArrayList<Coord> coords = new ArrayList<>(outOfBboxPoints.keySet());
for (int i = 0; i < coords.size(); i++) {
for (int j = i + 1; j < coords.size(); j++) {
ConnectionData cd = new ConnectionData();
cd.c1 = coords.get(i);
cd.c2 = coords.get(j);
cd.w1 = outOfBboxPoints.get(cd.c1);
cd.w2 = outOfBboxPoints.get(cd.c2);

if (lineCutsBbox(cd.c1, cd.c2 )) {
// Check if the way can be closed with one additional point
// outside the bounding box.
// The additional point is combination of the coords of both endpoints.
// It works if the lines from the endpoints to the additional point does
// not cut the bounding box.
// This can be removed when the splitter guarantees to provide logical complete
// multi-polygons.
Coord edgePoint1 = new Coord(cd.c1.getLatitude(), cd.c2
.getLongitude());
Coord edgePoint2 = new Coord(cd.c2.getLatitude(), cd.c1
.getLongitude());

if (lineCutsBbox(cd.c1, edgePoint1) == false
&& lineCutsBbox(edgePoint1, cd.c2) == false) {
cd.imC = edgePoint1;
} else if (lineCutsBbox(cd.c1, edgePoint2) == false
&& lineCutsBbox(edgePoint2, cd.c2) == false) {
cd.imC = edgePoint1;
} else {
// both endpoints are on opposite sides of the bounding box
// automatically closing such points would create wrong polygons in most cases
continue;
}
cd.distance = cd.c1.distance(cd.imC) + cd.imC.distance(cd.c2);
} else {
cd.distance = cd.c1.distance(cd.c2);
}
coordPairs.add(cd);
}
}

if (coordPairs.isEmpty()) {
log.debug("All potential connections cross the bbox. No connection possible.");
return false;
} else {
// retrieve the connection with the minimum distance
ConnectionData minCon = Collections.min(coordPairs,
new Comparator<ConnectionData>() {
public int compare(ConnectionData o1,
ConnectionData o2) {
return Double.compare(o1.distance, o2.distance);
}
});

if (minCon.w1 == minCon.w2) {
log.debug("Close a gap in way",minCon.w1);
if (minCon.imC != null)
minCon.w1.getPoints().add(minCon.imC);
minCon.w1.closeWayArtificially();
} else {
log.debug("Connect", minCon.w1, "with", minCon.w2);

if (minCon.w1.getPoints().get(0) == minCon.c1) {
Collections.reverse(minCon.w1.getPoints());
}
if (minCon.w2.getPoints().get(0) != minCon.c2) {
Collections.reverse(minCon.w2.getPoints());
}

minCon.w1.getPoints().addAll(minCon.w2.getPoints());
minCon.w1.addWay(minCon.w2);
allWays.remove(minCon.w2);
return true;
}
}
}
return false;
}

/**
* Removes all ways non closed ways from the given list (
* <code>{@link Way#hasIdenticalEndPoints()} == false</code>)
*
* @param wayList
* list of ways
*/
protected void removeUnclosedWays(ArrayList<JoinedWay> wayList) {
Iterator<JoinedWay> it = wayList.iterator();
boolean firstWarn = true;
while (it.hasNext()) {
JoinedWay tempWay = it.next();
if (!tempWay.hasIdenticalEndPoints()) {
// warn only if the way intersects the bounding box
boolean inBbox = tempWay.intersects(tileBounds);
if (inBbox) {
if (firstWarn) {
log.warn(
"Cannot join the following ways to closed polygons. Multipolygon",
toBrowseURL(), toTagString());
firstWarn = false;
}
logWayURLs(Level.WARNING, "- way:", tempWay);
logFakeWayDetails(Level.WARNING, tempWay);
}

it.remove();

if (inBbox) {
String role = getRole(tempWay);
if (role == null || "".equals(role) || "outer".equals(role)) {
// anyhow add the ways to the list for line tagging
outerWaysForLineTagging.addAll(tempWay.getOriginalWays());
}
}
}
}
}

/**
* Removes all ways that are completely outside the bounding box.
* This reduces error messages from problems on the tile bounds.
* @param wayList list of ways
*/
protected void removeWaysOutsideBbox(ArrayList<JoinedWay> wayList) {
ListIterator<JoinedWay> wayIter = wayList.listIterator();
while (wayIter.hasNext()) {
JoinedWay w = wayIter.next();
boolean remove = true;
// check all points
for (Coord c : w.getPoints()) {
if (tileBounds.contains(c)) {
// if one point is in the bounding box the way should not be removed
remove = false;
break;
}
}

if (remove) {
// check if the polygon contains the complete bounding box
if (w.getBounds().contains(tileArea.getBounds())) {
remove = false;
}
}

if (remove) {
if (log.isDebugEnabled()) {
log.debug("Remove way", w.getId(),
"because it is completely outside the bounding box.");
}
wayIter.remove();
}
}
}

/**
* Find all polygons that are not contained by any other polygon.
*
* @param candidates
* all polygons that should be checked
* @param roleFilter
* an additional filter
* @return all polygon indexes that are not contained by any other polygon
*/
private BitSet findOutmostPolygons(BitSet candidates, BitSet roleFilter) {
BitSet realCandidates = ((BitSet) candidates.clone());
realCandidates.and(roleFilter);
return findOutmostPolygons(realCandidates);
}

/**
* Finds all polygons that are not contained by any other polygons and that match
* to the given role. All polygons with index given by <var>candidates</var>
* are used.
*
* @param candidates
* indexes of the polygons that should be used
* @return the bits of all outermost polygons are set to true
*/
protected BitSet findOutmostPolygons(BitSet candidates) {
BitSet outmostPolygons = new BitSet();

// go through all candidates and check if they are contained by any
// other candidate
for (int candidateIndex = candidates.nextSetBit(0); candidateIndex >= 0; candidateIndex = candidates
.nextSetBit(candidateIndex + 1)) {
// check if the candidateIndex polygon is not contained by any
// other candidate polygon
boolean isOutmost = true;
for (int otherCandidateIndex = candidates.nextSetBit(0); otherCandidateIndex >= 0; otherCandidateIndex = candidates
.nextSetBit(otherCandidateIndex + 1)) {
if (contains(otherCandidateIndex, candidateIndex)) {
// candidateIndex is not an outermost polygon because it is
// contained by the otherCandidateIndex polygon
isOutmost = false;
break;
}
}
if (isOutmost) {
// this is an outermost polygon
// put it to the bitset
outmostPolygons.set(candidateIndex);
}
}

return outmostPolygons;
}

protected ArrayList<PolygonStatus> getPolygonStatus(BitSet outmostPolygons,
String defaultRole) {
ArrayList<PolygonStatus> polygonStatusList = new ArrayList<>();
for (int polyIndex = outmostPolygons.nextSetBit(0); polyIndex >= 0; polyIndex = outmostPolygons
.nextSetBit(polyIndex + 1)) {
// polyIndex is the polygon that is not contained by any other
// polygon
JoinedWay polygon = polygons.get(polyIndex);
String role = getRole(polygon);
// if the role is not explicitly set use the default role
if (role == null || "".equals(role)) {
role = defaultRole;
}
polygonStatusList.add(new PolygonStatus("outer".equals(role), polyIndex, polygon));
}
// sort by role and then by number of points, this improves performance
// in the routines which add the polygons to areas
if (polygonStatusList.size() > 2){
Collections.sort(polygonStatusList, new Comparator<PolygonStatus>() {
public int compare(PolygonStatus o1, PolygonStatus o2) {
if (o1.outer != o2.outer)
return (o1.outer) ? -1 : 1;
return o1.polygon.getPoints().size() - o2.polygon.getPoints().size();
}
});
}
return polygonStatusList;
}

/**
* Creates a list of all original ways of the multipolygon.
* @return all source ways
*/
protected List<Way> getSourceWays() {
ArrayList<Way> allWays = new ArrayList<>();

for (Map.Entry<String, Element> r_e : getElements()) {
if (r_e.getValue() instanceof Way) {
if (((Way)r_e.getValue()).getPoints().isEmpty()) {
log.warn("Way",r_e.getValue(),"has no points and cannot be used for the multipolygon",toBrowseURL());
} else {
allWays.add((Way) r_e.getValue());
}
} else if (r_e.getValue() instanceof Node == false ||
("admin_centre".equals(r_e.getKey()) == false && "label".equals(r_e.getKey()) == false)) {
log.warn("Non way member in role", r_e.getKey(), r_e.getValue().toBrowseURL(),
"in multipolygon", toBrowseURL(), toTagString());
}
}
return allWays;
}

// unfinishedPolygons marks which polygons are not yet processed
protected BitSet unfinishedPolygons;

// create bitsets which polygons belong to the outer and to the inner role
protected BitSet innerPolygons;
protected BitSet taggedInnerPolygons;
protected BitSet outerPolygons;
protected BitSet taggedOuterPolygons;

/**
* Process the ways in this relation. Joins way with the role "outer" Adds
* ways with the role "inner" to the way with the role "outer"
*/
public void processElements() {
log.info("Processing multipolygon", toBrowseURL());

List<Way> allWays = getSourceWays();

// check if it makes sense to process the mp
if (isMpProcessable(allWays) == false) {
log.info("Do not process multipolygon",getId(),"because it has no style relevant tags.");
return;
}

// join all single ways to polygons, try to close ways and remove non closed ways
polygons = joinWays(allWays);

outerWaysForLineTagging = new HashSet<>();
outerTags = new HashMap<>();

do {
closeWays(polygons, getMaxCloseDist());
} while (connectUnclosedWays(polygons));

removeUnclosedWays(polygons);

// now only closed ways are left => polygons only

// check if we have at least one polygon left
boolean hasPolygons = !polygons.isEmpty();

removeWaysOutsideBbox(polygons);

if (polygons.isEmpty()) {
// do nothing
if (log.isInfoEnabled()) {
if (hasPolygons)
log.info("Multipolygon", toBrowseURL(),
"is completely outside the bounding box. It is not processed.");
else
log.info("Multipolygon " + toBrowseURL() + " does not contain a closed polygon.");
}
tagOuterWays();
cleanup();
return;
}

// the intersectingPolygons marks all intersecting/overlapping polygons
intersectingPolygons = new HashSet<>();

// check which polygons lie inside which other polygon
createContainsMatrix(polygons);

// unfinishedPolygons marks which polygons are not yet processed
unfinishedPolygons = new BitSet(polygons.size());
unfinishedPolygons.set(0, polygons.size());

// create bitsets which polygons belong to the outer and to the inner role
innerPolygons = new BitSet();
taggedInnerPolygons = new BitSet();
outerPolygons = new BitSet();
taggedOuterPolygons = new BitSet();

int wi = 0;
for (Way w : polygons) {
w.setFullArea(w.getFullArea()); // trigger setting area before start cutting...
// do like this to disguise function with side effects
String role = getRole(w);
if ("inner".equals(role)) {
innerPolygons.set(wi);
taggedInnerPolygons.set(wi);
} else if ("outer".equals(role)) {
outerPolygons.set(wi);
taggedOuterPolygons.set(wi);
} else {
// unknown role => it could be both
innerPolygons.set(wi);
outerPolygons.set(wi);
}
wi++;
}

if (outerPolygons.isEmpty()) {
log.warn("Multipolygon", toBrowseURL(),
"does not contain any way tagged with role=outer or empty role.");
cleanup();
return;
}

Queue<PolygonStatus> polygonWorkingQueue = new LinkedBlockingQueue<>();
BitSet nestedOuterPolygons = new BitSet();
BitSet nestedInnerPolygons = new BitSet();

BitSet outmostPolygons;
BitSet outmostInnerPolygons = new BitSet();
boolean outmostInnerFound;
do {
outmostInnerFound = false;
outmostPolygons = findOutmostPolygons(unfinishedPolygons);

if (outmostPolygons.intersects(taggedInnerPolygons)) {
outmostInnerPolygons.or(outmostPolygons);
outmostInnerPolygons.and(taggedInnerPolygons);

if (log.isDebugEnabled())
log.debug("wrong inner polygons: " + outmostInnerPolygons);
// do not process polygons tagged with role=inner but which are
// not contained by any other polygon
unfinishedPolygons.andNot(outmostInnerPolygons);
outmostPolygons.andNot(outmostInnerPolygons);
outmostInnerFound = true;
}
} while (outmostInnerFound);

if (!outmostPolygons.isEmpty()) {
polygonWorkingQueue.addAll(getPolygonStatus(outmostPolygons, "outer"));
}

boolean outmostPolygonProcessing = true;

while (!polygonWorkingQueue.isEmpty()) {

// the polygon is not contained by any other unfinished polygon
PolygonStatus currentPolygon = polygonWorkingQueue.poll();

// this polygon is now processed and should not be used by any
// further step
unfinishedPolygons.clear(currentPolygon.index);

BitSet polygonContains = new BitSet();
polygonContains.or(containsMatrix.get(currentPolygon.index));
// use only polygon that are contained by the polygon
polygonContains.and(unfinishedPolygons);
// polygonContains is the intersection of the unfinished and
// the contained polygons

// get the holes
// these are all polygons that are in the main polygon
// and that are not contained by any other polygon
boolean holesOk;
BitSet holeIndexes;
do {
holeIndexes = findOutmostPolygons(polygonContains);
holesOk = true;

if (currentPolygon.outer) {
// for role=outer only role=inner is allowed
if (holeIndexes.intersects(taggedOuterPolygons)) {
BitSet addOuterNestedPolygons = new BitSet();
addOuterNestedPolygons.or(holeIndexes);
addOuterNestedPolygons.and(taggedOuterPolygons);
nestedOuterPolygons.or(addOuterNestedPolygons);
holeIndexes.andNot(addOuterNestedPolygons);
// do not process them
unfinishedPolygons.andNot(addOuterNestedPolygons);
polygonContains.andNot(addOuterNestedPolygons);

// recalculate the holes again to get all inner polygons
// in the nested outer polygons
holesOk = false;
}
} else {
// for role=inner both role=inner and role=outer is supported
// although inner in inner is not officially allowed
if (holeIndexes.intersects(taggedInnerPolygons)) {
// process inner in inner but issue a warning later
BitSet addInnerNestedPolygons = new BitSet();
addInnerNestedPolygons.or(holeIndexes);
addInnerNestedPolygons.and(taggedInnerPolygons);
nestedInnerPolygons.or(addInnerNestedPolygons);
}
}
} while (!holesOk);

ArrayList<PolygonStatus> holes = getPolygonStatus(holeIndexes,
(currentPolygon.outer ? "inner" : "outer"));

// these polygons must all be checked for holes
polygonWorkingQueue.addAll(holes);

if (currentPolygon.outer) {
// add the original ways to the list of ways that get the line tags of the mp
// the joined ways may be changed by the auto closing algorithm
outerWaysForLineTagging.addAll(currentPolygon.polygon.getOriginalWays());
}

// calculate the size of the polygon
double outerAreaSize = currentPolygon.polygon.getSizeOfArea();
if (outerAreaSize > largestSize) {
// subtract the holes
for (PolygonStatus hole : holes) {
outerAreaSize -= hole.polygon.getSizeOfArea();
}
// is it still larger than the largest known polygon?
if (outerAreaSize > largestSize) {
largestOuterPolygon = currentPolygon.polygon;
largestSize = outerAreaSize;
}
}

// check if the polygon is an outer polygon or
// if there are some holes
boolean processPolygon = currentPolygon.outer
|| (holes.isEmpty()==false);

if (processPolygon) {
List<Way> singularOuterPolygons;
if (holes.isEmpty()) {
singularOuterPolygons = Collections
.singletonList((Way) new JoinedWay(currentPolygon.polygon));
} else {
List<Way> innerWays = new ArrayList<>(holes.size());
for (PolygonStatus polygonHoleStatus : holes) {
innerWays.add(polygonHoleStatus.polygon);
}

MultiPolygonCutter cutter = new MultiPolygonCutter(this, tileArea);
singularOuterPolygons = cutter.cutOutInnerPolygons(currentPolygon.polygon, innerWays);
}

if (singularOuterPolygons.isEmpty()==false) {
// handle the tagging
if (currentPolygon.outer && hasStyleRelevantTags(this)) {
// use the tags of the multipolygon
for (Way p : singularOuterPolygons) {
// overwrite all tags
p.copyTags(this);
p.deleteTag("type");
}
// remove the multipolygon tags in the original ways of the current polygon
removeTagsInOrgWays(this, currentPolygon.polygon);
} else {
// use the tags of the original ways
currentPolygon.polygon.mergeTagsFromOrgWays();
for (Way p : singularOuterPolygons) {
// overwrite all tags
p.copyTags(currentPolygon.polygon);
}
// remove the current polygon tags in its original ways
removeTagsInOrgWays(currentPolygon.polygon, currentPolygon.polygon);
}

if (currentPolygon.outer && outmostPolygonProcessing) {
// this is the outer most polygon - copy its tags. They will be used
// later for tagging of the lines

// all cut polygons have the same tags - copy them from the first polygon
Way outerWay = singularOuterPolygons.get(0);
for (Entry<String, String> tag : outerWay.getTagEntryIterator()) {
outerTags.put(tag.getKey(), tag.getValue());
}
outmostPolygonProcessing = false;
}

long fullArea = currentPolygon.polygon.getFullArea();
for (Way mpWay : singularOuterPolygons) {
// put the cut out polygons to the
// final way map
if (log.isDebugEnabled())
log.debug(mpWay.getId(),mpWay.toTagString());

mpWay.setFullArea(fullArea);
// mark this polygons so that only polygon style rules are applied
mpWay.addTag(STYLE_FILTER_TAG, STYLE_FILTER_POLYGON);
mpWay.addTag(MP_CREATED_TAG, "true");

if (currentPolygon.outer) {
mpWay.addTag("mkgmap:mp_role", "outer");
if (isAreaSizeCalculated())
mpAreaSize += calcAreaSize(mpWay.getPoints());
} else {
mpWay.addTag("mkgmap:mp_role", "inner");
}

getMpPolygons().put(mpWay.getId(), mpWay);
}
}
}
}

if (log.isLoggable(Level.WARNING) &&
(outmostInnerPolygons.cardinality()+unfinishedPolygons.cardinality()+nestedOuterPolygons.cardinality()+nestedInnerPolygons.cardinality() >= 1)) {
log.warn("Multipolygon", toBrowseURL(), toTagString(), "contains errors.");

BitSet outerUnusedPolys = new BitSet();
outerUnusedPolys.or(unfinishedPolygons);
outerUnusedPolys.or(outmostInnerPolygons);
outerUnusedPolys.or(nestedOuterPolygons);
outerUnusedPolys.or(nestedInnerPolygons);
outerUnusedPolys.or(unfinishedPolygons);
// use only the outer polygons
outerUnusedPolys.and(outerPolygons);
for (JoinedWay w : getWaysFromPolygonList(outerUnusedPolys)) {
outerWaysForLineTagging.addAll(w.getOriginalWays());
}

runIntersectionCheck(unfinishedPolygons);
runOutmostInnerPolygonCheck(outmostInnerPolygons);
runNestedOuterPolygonCheck(nestedOuterPolygons);
runNestedInnerPolygonCheck(nestedInnerPolygons);
runWrongInnerPolygonCheck(unfinishedPolygons, innerPolygons);

// we have at least one polygon that could not be processed
// Probably we have intersecting or overlapping polygons
// one possible reason is if the relation overlaps the tile
// bounds
// => issue a warning
List<JoinedWay> lostWays = getWaysFromPolygonList(unfinishedPolygons);
for (JoinedWay w : lostWays) {
log.warn("Polygon", w, "is not processed due to an unknown reason.");
logWayURLs(Level.WARNING, "-", w);
}
}

if (hasStyleRelevantTags(this) == false) {
// add tags to the multipolygon that are taken from the outer ways
// they may be required by some hooks (e.g. Area2POIHook)
for (Entry<String, String> tags : outerTags.entrySet()) {
addTag(tags.getKey(), tags.getValue());
}
}
String mpAreaSizeStr = null;
if (isAreaSizeCalculated()) {
// calculate tag value for mkgmap:cache_area_size only once
mpAreaSizeStr = String.format(Locale.US, "%.3f", mpAreaSize);
}
// Go through all original outer ways, create a copy, tag them
// with the mp tags and mark them only to be used for polyline processing
// This enables the style file to decide if the polygon information or
// the simple line information should be used.
for (Way orgOuterWay : outerWaysForLineTagging) {
Way lineTagWay = new Way(getOriginalId(), orgOuterWay.getPoints());
lineTagWay.setFakeId();
lineTagWay.addTag(STYLE_FILTER_TAG, STYLE_FILTER_LINE);
lineTagWay.addTag(MP_CREATED_TAG, "true");
if (mpAreaSizeStr != null) {
// assign the area size of the whole multipolygon to all outer polygons
lineTagWay.addTag("mkgmap:cache_area_size", mpAreaSizeStr);
}
for (Entry<String,String> tag : outerTags.entrySet()) {
lineTagWay.addTag(tag.getKey(), tag.getValue());

// remove the tag from the original way if it has the same value
if (tag.getValue().equals(orgOuterWay.getTag(tag.getKey()))) {
removeTagsInOrgWays(orgOuterWay, tag.getKey());
}
}

if (log.isDebugEnabled())
log.debug("Add line way", lineTagWay.getId(), lineTagWay.toTagString());
tileWayMap.put(lineTagWay.getId(), lineTagWay);
}

postProcessing();
cleanup();
}

protected double getMaxCloseDist() {
return -1; //
}

protected void postProcessing() {

if (isAreaSizeCalculated()) {
// assign the area size of the whole multipolygon to all outer polygons
String mpAreaSizeStr = String.format(Locale.US, "%.3f", mpAreaSize);
addTag("mkgmap:cache_area_size", mpAreaSizeStr);
for (Way w : mpPolygons.values()) {
if ("outer".equals(w.getTag("mkgmap:mp_role"))) {
w.addTag("mkgmap:cache_area_size", mpAreaSizeStr);
}
}
}

for (Way w : mpPolygons.values()) {
w.deleteTag("mkgmap:mp_role");
}
// copy all polygons created by the multipolygon algorithm to the global way map
tileWayMap.putAll(mpPolygons);

if (largestOuterPolygon != null) {
// check if the mp contains a node with role "label"
for (Map.Entry<String, Element> r_e : getElements()) {
if (r_e.getValue() instanceof Node && "label".equals(r_e.getKey())) {
// yes => use the label node as reference point
cOfG = ((Node)r_e.getValue()).getLocation();
break;
}
}

if (cOfG == null) {
// use the center of the largest polygon as reference point
cOfG = largestOuterPolygon.getCofG();
}
}
}

private void runIntersectionCheck(BitSet unfinishedPolys) {
if (intersectingPolygons.isEmpty()) {
// nothing to do
return;
}

log.warn("Some polygons are intersecting. This is not allowed in multipolygons.");

boolean oneOufOfBbox = false;
for (JoinedWay polygon : intersectingPolygons) {
int pi = polygons.indexOf(polygon);
unfinishedPolys.clear(pi);

boolean outOfBbox = false;
for (Coord c : polygon.getPoints()) {
if (!tileBounds.contains(c)) {
outOfBbox = true;
oneOufOfBbox = true;
break;
}
}

logWayURLs(Level.WARNING, (outOfBbox ? "*" : "-"), polygon);
}

for (JoinedWay polygon : intersectingPolygons) {
// print out the details of the original ways
logFakeWayDetails(Level.WARNING, polygon);
}

if (oneOufOfBbox) {
log.warn("Some of these intersections/overlaps may be caused by incomplete data on bounding box edges (*).");
}
}

private void runNestedOuterPolygonCheck(BitSet nestedOuterPolygons) {
// just print out warnings
// the check has been done before
for (int wiIndex = nestedOuterPolygons.nextSetBit(0); wiIndex >= 0; wiIndex = nestedOuterPolygons
.nextSetBit(wiIndex + 1)) {
JoinedWay outerWay = polygons.get(wiIndex);
log.warn("Polygon", outerWay, "carries role outer but lies inside an outer polygon. Potentially its role should be inner.");
logFakeWayDetails(Level.WARNING, outerWay);
}
}

private void runNestedInnerPolygonCheck(BitSet nestedInnerPolygons) {
// just print out warnings
// the check has been done before
for (int wiIndex = nestedInnerPolygons.nextSetBit(0); wiIndex >= 0; wiIndex = nestedInnerPolygons
.nextSetBit(wiIndex + 1)) {
JoinedWay innerWay = polygons.get(wiIndex);
log.warn("Polygon", innerWay, "carries role", getRole(innerWay), "but lies inside an inner polygon. Potentially its role should be outer.");
logFakeWayDetails(Level.WARNING, innerWay);
}
}

private void runOutmostInnerPolygonCheck(BitSet outmostInnerPolygons) {
// just print out warnings
// the check has been done before
for (int wiIndex = outmostInnerPolygons.nextSetBit(0); wiIndex >= 0; wiIndex = outmostInnerPolygons
.nextSetBit(wiIndex + 1)) {
JoinedWay innerWay = polygons.get(wiIndex);
log.warn("Polygon", innerWay, "carries role", getRole(innerWay), "but is not inside any other polygon. Potentially it does not belong to this multipolygon.");
logFakeWayDetails(Level.WARNING, innerWay);
}
}

private void runWrongInnerPolygonCheck(BitSet unfinishedPolygons,
BitSet innerPolygons) {
// find all unfinished inner polygons that are not contained by any
BitSet wrongInnerPolygons = findOutmostPolygons(unfinishedPolygons, innerPolygons);
if (log.isDebugEnabled()) {
log.debug("unfinished", unfinishedPolygons);
log.debug("inner", innerPolygons);
// other polygon
log.debug("wrong", wrongInnerPolygons);
}
if (!wrongInnerPolygons.isEmpty()) {
// we have an inner polygon that is not contained by any outer polygon
// check if
for (int wiIndex = wrongInnerPolygons.nextSetBit(0); wiIndex >= 0; wiIndex = wrongInnerPolygons
.nextSetBit(wiIndex + 1)) {
BitSet containedPolygons = new BitSet();
containedPolygons.or(unfinishedPolygons);
containedPolygons.and(containsMatrix.get(wiIndex));

JoinedWay innerWay = polygons.get(wiIndex);
if (containedPolygons.isEmpty()) {
log.warn("Polygon", innerWay, "carries role", getRole(innerWay),
"but is not inside any outer polygon. Potentially it does not belong to this multipolygon.");
logFakeWayDetails(Level.WARNING, innerWay);
} else {
log.warn("Polygon", innerWay, "carries role", getRole(innerWay),
"but is not inside any outer polygon. Potentially the roles are interchanged with the following",
(containedPolygons.cardinality() > 1 ? "ways" : "way"), ".");

for (int wrIndex = containedPolygons.nextSetBit(0); wrIndex >= 0; wrIndex = containedPolygons
.nextSetBit(wrIndex + 1)) {
logWayURLs(Level.WARNING, "-", polygons.get(wrIndex));
unfinishedPolygons.set(wrIndex);
wrongInnerPolygons.set(wrIndex);
}
logFakeWayDetails(Level.WARNING, innerWay);
}

unfinishedPolygons.clear(wiIndex);
wrongInnerPolygons.clear(wiIndex);
}
}
}

protected void cleanup() {
mpPolygons = null;
roleMap.clear();
containsMatrix = null;
polygons = null;
tileArea = null;
intersectingPolygons = null;
outerWaysForLineTagging = null;
outerTags = null;

unfinishedPolygons = null;
innerPolygons = null;
taggedInnerPolygons = null;
outerPolygons = null;
taggedOuterPolygons = null;

largestOuterPolygon = null;
}

/**
* Retrieves if the given element contains tags that may be relevant
* for style processing. If it has no relevant tag it will probably be
* dropped by the style.
*
* @param element the OSM element
* @return <code>true</code> has style relevant tags
*/
protected boolean hasStyleRelevantTags(Element element) {
if (element instanceof MultiPolygonRelation) {
if (((MultiPolygonRelation) element).getTagsIncomplete()) {
return true;
}
}

for (Map.Entry<String, String> tagEntry : element.getTagEntryIterator()) {
String tagName = tagEntry.getKey();
// all tags are style relevant
// except: type (for relations), mkgmap:*
boolean isStyleRelevant = (element instanceof Relation && tagName.equals("type")) == false
&& tagName.startsWith("mkgmap:") == false;
if (isStyleRelevant) {
return true;
}
}
return false;
}

/**
* Checks if this mp should be processed or if it is needless to process it
* because there is no result.
* @param ways the list of ways of the mp
* @return <code>true</code> the mp processing will have a result;
* <code>false</code> the mp processing will fail
*/
private boolean isMpProcessable(Collection<Way> ways) {
// Check if the multipolygon itself or the member ways have a
// tag. If not it does not make sense to process the mp because
// the output will not change anything
if (hasStyleRelevantTags(this)) {
return true;
}

for (Way w : ways) {
if (hasStyleRelevantTags(w)) {
return true;
}
}
return false;
}

/**
* Creates a matrix which polygon contains which polygon. A polygon does not
* contain itself.
*
* @param polygonList
* a list of polygons
*/
protected void createContainsMatrix(List<JoinedWay> polygonList) {
containsMatrix = new ArrayList<>();
for (int i = 0; i < polygonList.size(); i++) {
containsMatrix.add(new BitSet());
}

long t1 = System.currentTimeMillis();

if (log.isDebugEnabled())
log.debug("createContainsMatrix listSize:", polygonList.size());

// use this matrix to check which matrix element has been
// calculated
ArrayList<BitSet> finishedMatrix = new ArrayList<>(polygonList
.size());

for (int i = 0; i < polygonList.size(); i++) {
BitSet matrixRow = new BitSet();
// a polygon does not contain itself
matrixRow.set(i);
finishedMatrix.add(matrixRow);
}

for (int rowIndex = 0; rowIndex < polygonList.size(); rowIndex++) {
JoinedWay potentialOuterPolygon = polygonList.get(rowIndex);
BitSet containsColumns = containsMatrix.get(rowIndex);
BitSet finishedCol = finishedMatrix.get(rowIndex);

// the polygon need to be created only sometimes
// so use a lazy creation to improve performance
WayAndLazyPolygon lazyPotOuterPolygon = new WayAndLazyPolygon(potentialOuterPolygon);

// get all non calculated columns of the matrix
for (int colIndex = finishedCol.nextClearBit(0); colIndex >= 0
&& colIndex < polygonList.size(); colIndex = finishedCol
.nextClearBit(colIndex + 1)) {

JoinedWay innerPolygon = polygonList.get(colIndex);

if (potentialOuterPolygon.getBounds().intersects(
innerPolygon.getBounds()))
{
boolean contains = contains(lazyPotOuterPolygon, innerPolygon);

if (contains) {
containsColumns.set(colIndex);

// we also know that the inner polygon does not contain the
// outer polygon
// so we can set the finished bit for this matrix
// element
finishedMatrix.get(colIndex).set(rowIndex);

// additionally we know that the outer polygon contains all
// polygons that are contained by the inner polygon
containsColumns.or(containsMatrix.get(colIndex));
finishedCol.or(containsColumns);
}
} else {
// both polygons do not intersect
// we can flag both matrix elements as finished
finishedMatrix.get(colIndex).set(rowIndex);
finishedMatrix.get(rowIndex).set(colIndex);
}
// this matrix element is calculated now
finishedCol.set(colIndex);
}
}

if (log.isDebugEnabled()) {
long t2 = System.currentTimeMillis();
log.debug("createMatrix for", polygonList.size(), "polygons took",
(t2 - t1), "ms");

log.debug("Containsmatrix:");
int i = 0;
boolean noContained = true;
for (BitSet b : containsMatrix) {
if (b.isEmpty()==false) {
log.debug(i,"contains",b);
noContained = false;
}
i++;
}
if (noContained) {
log.debug("Matrix is empty");
}
}
}

/**
* This is a helper class that creates a high precision polygon for a way
* on request only.
*/
private static class WayAndLazyPolygon {
private final JoinedWay way;
private Polygon polygon;

public WayAndLazyPolygon(JoinedWay way) {
this.way = way;
}

public final JoinedWay getWay() {
return this.way;
}

public final Polygon getPolygon() {
if (this.polygon == null) {
this.polygon = Java2DConverter.createHighPrecPolygon(this.way.getPoints());
}
return this.polygon;
}
}

/**
* Checks if the polygon with polygonIndex1 contains the polygon with polygonIndex2.
*
* @return true if polygon(polygonIndex1) contains polygon(polygonIndex2)
*/
private boolean contains(int polygonIndex1, int polygonIndex2) {
return containsMatrix.get(polygonIndex1).get(polygonIndex2);
}

/**
* Checks if polygon1 contains polygon2.
*
* @param polygon1
* a closed way
* @param polygon2
* a 2nd closed way
* @return true if polygon1 contains polygon2
*/
private boolean contains(WayAndLazyPolygon polygon1, JoinedWay polygon2) {
if (!polygon1.getWay().hasIdenticalEndPoints()) {
return false;
}
// check if the bounds of polygon2 are completely inside/enclosed the bounds
// of polygon1
if (!polygon1.getWay().getBounds().contains(polygon2.getBounds())) {
return false;
}

// check first if one point of polygon2 is in polygon1

// ignore intersections outside the bounding box
// so it is necessary to check if there is at least one
// point of polygon2 in polygon1 ignoring all points outside the bounding box
boolean onePointContained = false;
boolean allOnLine = true;
for (Coord px : polygon2.getPoints()) {
if (polygon1.getPolygon().contains(px.getHighPrecLon(), px.getHighPrecLat())){
// there's one point that is in polygon1 and in the bounding
// box => polygon1 may contain polygon2
onePointContained = true;
if (!locatedOnLine(px, polygon1.getWay().getPoints())) {
allOnLine = false;
break;
}
} else if (tileBounds.contains(px)) {
// we have to check if the point is on one line of the polygon1

if (!locatedOnLine(px, polygon1.getWay().getPoints())) {
// there's one point that is not in polygon1 but inside the
// bounding box => polygon1 does not contain polygon2
//allOnLine = false;
return false;
}
}
}

if (allOnLine) {
onePointContained = false;
// all points of polygon2 lie on lines of polygon1
// => the middle of each line polygon must NOT lie outside polygon1
ArrayList<Coord> middlePoints2 = new ArrayList<>(polygon2.getPoints().size());
Coord p1 = null;
for (Coord p2 : polygon2.getPoints()) {
if (p1 != null) {
Coord pm = p1.makeBetweenPoint(p2, 0.5);
middlePoints2.add(pm);
}
p1 = p2;
}

for (Coord px : middlePoints2) {
if (polygon1.getPolygon().contains(px.getHighPrecLon(), px.getHighPrecLat())){
// there's one point that is in polygon1 and in the bounding
// box => polygon1 may contain polygon2
onePointContained = true;
break;
} else if (tileBounds.contains(px)) {
// we have to check if the point is on one line of the polygon1

if (!locatedOnLine(px, polygon1.getWay().getPoints())) {
// there's one point that is not in polygon1 but inside the
// bounding box => polygon1 does not contain polygon2
return false;
}
}
}
}

if (!onePointContained) {
// no point of polygon2 is in polygon1 => polygon1 does not contain polygon2
return false;
}

Iterator<Coord> it1 = polygon1.getWay().getPoints().iterator();
Coord p1_1 = it1.next();

while (it1.hasNext()) {
Coord p1_2 = p1_1;
p1_1 = it1.next();

if (!polygon2.linePossiblyIntersectsWay(p1_1, p1_2)) {
// don't check it - this segment of the outer polygon
// definitely does not intersect the way
continue;
}

int lonMin = Math.min(p1_1.getLongitude(), p1_2.getLongitude());
int lonMax = Math.max(p1_1.getLongitude(), p1_2.getLongitude());
int latMin = Math.min(p1_1.getLatitude(), p1_2.getLatitude());
int latMax = Math.max(p1_1.getLatitude(), p1_2.getLatitude());

// check all lines of way1 and way2 for intersections
Iterator<Coord> it2 = polygon2.getPoints().iterator();
Coord p2_1 = it2.next();

// for speedup we divide the area around the second line into
// a 3x3 matrix with lon(-1,0,1) and lat(-1,0,1).
// -1 means below min lon/lat of bbox line p1_1-p1_2
// 0 means inside the bounding box of the line p1_1-p1_2
// 1 means above max lon/lat of bbox line p1_1-p1_2
int lonField = p2_1.getLongitude() < lonMin ? -1 : p2_1
.getLongitude() > lonMax ? 1 : 0;
int latField = p2_1.getLatitude() < latMin ? -1 : p2_1
.getLatitude() > latMax ? 1 : 0;

int prevLonField = lonField;
int prevLatField = latField;

while (it2.hasNext()) {
Coord p2_2 = p2_1;
p2_1 = it2.next();

int changes = 0;
// check if the field of the 3x3 matrix has changed
if ((lonField >= 0 && p1_1.getLongitude() < lonMin)
|| (lonField <= 0 && p1_1.getLongitude() > lonMax)) {
changes++;
lonField = p1_1.getLongitude() < lonMin ? -1 : p1_1
.getLongitude() > lonMax ? 1 : 0;
}
if ((latField >= 0 && p1_1.getLatitude() < latMin)
|| (latField <= 0 && p1_1.getLatitude() > latMax)) {
changes++;
latField = p1_1.getLatitude() < latMin ? -1 : p1_1
.getLatitude() > latMax ? 1 : 0;
}

// an intersection is possible if
// latField and lonField has changed
// or if we come from or go to the inner matrix field
boolean intersectionPossible = (changes == 2)
|| (latField == 0 && lonField == 0)
|| (prevLatField == 0 && prevLonField == 0);

boolean intersects = intersectionPossible
&& linesCutEachOther(p1_1, p1_2, p2_1, p2_2);

if (intersects) {
if ((polygon1.getWay().isClosedArtificially() && !it1.hasNext())
|| (polygon2.isClosedArtificially() && !it2.hasNext())) {
// don't care about this intersection
// one of the polygons is closed by this mp code and the
// closing segment causes the intersection
log.info("Polygon", polygon1, "may contain polygon", polygon2,
". Ignoring artificial generated intersection.");
} else if ((!tileBounds.contains(p1_1))
|| (!tileBounds.contains(p1_2))
|| (!tileBounds.contains(p2_1))
|| (!tileBounds.contains(p2_2))) {
// at least one point is outside the bounding box
// we ignore the intersection because the ways may not
// be complete
// due to removals of the tile splitter or osmosis
log.info("Polygon", polygon1, "may contain polygon", polygon2,
". Ignoring because at least one point is outside the bounding box.");
} else {
// store them in the intersection polygons set
// the error message will be printed out in the end of
// the mp handling
intersectingPolygons.add(polygon1.getWay());
intersectingPolygons.add(polygon2);
return false;
}
}

prevLonField = lonField;
prevLatField = latField;
}
}

// don't have any intersection
// => polygon1 contains polygon2
return true;
}

/**
* Checks if the point p is located on one line of the given points.
* @param p a point
* @param points a list of points; all consecutive points are handled as lines
* @return true if p is located on one line given by points
*/
private static boolean locatedOnLine(Coord p, List<Coord> points) {
Coord cp1 = null;
for (Coord cp2 : points) {
if (p.highPrecEquals(cp2)) {
return true;
}

try {
if (cp1 == null) {
// first init
continue;
}

if (p.getHighPrecLon() < Math.min(cp1.getHighPrecLon(), cp2.getHighPrecLon())) {
continue;
}
if (p.getHighPrecLon() > Math.max(cp1.getHighPrecLon(), cp2.getHighPrecLon())) {
continue;
}
if (p.getHighPrecLat() < Math.min(cp1.getHighPrecLat(), cp2.getHighPrecLat())) {
continue;
}
if (p.getHighPrecLat() > Math.max(cp1.getHighPrecLat(), cp2.getHighPrecLat())) {
continue;
}

double dist = Line2D.ptSegDistSq(cp1.getHighPrecLon(), cp1.getHighPrecLat(),
cp2.getHighPrecLon(), cp2.getHighPrecLat(),
p.getHighPrecLon(), p.getHighPrecLat());

if (dist <= OVERLAP_TOLERANCE_DISTANCE) {
log.debug("Point", p, "is located on line between", cp1, "and",
cp2, ". Distance:", dist);
return true;
}
} finally {
cp1 = cp2;
}
}
return false;
}

private boolean lineCutsBbox(Coord p1_1, Coord p1_2) {
Coord nw = new Coord(tileBounds.getMaxLat(), tileBounds.getMinLong());
Coord sw = new Coord(tileBounds.getMinLat(), tileBounds.getMinLong());
Coord se = new Coord(tileBounds.getMinLat(), tileBounds.getMaxLong());
Coord ne = new Coord(tileBounds.getMaxLat(), tileBounds.getMaxLong());
return linesCutEachOther(nw, sw, p1_1, p1_2)
|| linesCutEachOther(sw, se, p1_1, p1_2)
|| linesCutEachOther(se, ne, p1_1, p1_2)
|| linesCutEachOther(ne, nw, p1_1, p1_2);
}

/**
* XXX: This code presumes that certain tests were already done!
* Check if the line p1_1 to p1_2 cuts line p2_1 to p2_2 in two pieces and vice versa.
* This is a form of intersection check where it is allowed that one line ends on the
* other line or that the two lines overlap.
* @param p1_1 first point of line 1
* @param p1_2 second point of line 1
* @param p2_1 first point of line 2
* @param p2_2 second point of line 2
* @return true if both lines intersect somewhere in the middle of each other
*/
private static boolean linesCutEachOther(Coord p1_1, Coord p1_2, Coord p2_1, Coord p2_2) {
long width1 = p1_2.getHighPrecLon() - p1_1.getHighPrecLon();
long width2 = p2_2.getHighPrecLon() - p2_1.getHighPrecLon();

long height1 = p1_2.getHighPrecLat() - p1_1.getHighPrecLat();
long height2 = p2_2.getHighPrecLat() - p2_1.getHighPrecLat();

long denominator = ((height2 * width1) - (width2 * height1));
if (denominator == 0) {
// the lines are parallel
// they might overlap but this is ok for this test
return false;
}

long x1Mx3 = p1_1.getHighPrecLon() - p2_1.getHighPrecLon();
long y1My3 = p1_1.getHighPrecLat() - p2_1.getHighPrecLat();

double isx = (double)((width2 * y1My3) - (height2 * x1Mx3))
/ denominator;
if (isx <= 0 || isx >= 1) {
return false;
}

double isy = (double)((width1 * y1My3) - (height1 * x1Mx3))
/ denominator;

if (isy <= 0 || isy >= 1) {
return false;
}
return true;
}

private List<JoinedWay> getWaysFromPolygonList(BitSet selection) {
if (selection.isEmpty()) {
return Collections.emptyList();
}
List<JoinedWay> wayList = new ArrayList<>(selection
.cardinality());
for (int i = selection.nextSetBit(0); i >= 0; i = selection.nextSetBit(i + 1)) {
wayList.add(polygons.get(i));
}
return wayList;
}

private static void logWayURLs(Level level, String preMsg, Way way) {
if (log.isLoggable(level)) {
if (way instanceof JoinedWay) {
if (((JoinedWay) way).getOriginalWays().isEmpty()) {
log.warn("Way", way, "does not contain any original ways");
}
for (Way segment : ((JoinedWay) way).getOriginalWays()) {
if (preMsg == null || preMsg.length() == 0) {
log.log(level, segment.toBrowseURL());
} else {
log.log(level, preMsg, segment.toBrowseURL());
}
}
} else {
if (preMsg == null || preMsg.length() == 0) {
log.log(level, way.toBrowseURL());
} else {
log.log(level, preMsg, way.toBrowseURL());
}
}
}
}

/**
* Logs the details of the original ways of a way with a fake id. This is
* primarily necessary for the sea multipolygon because it consists of
* faked ways only. In this case logging messages can be improved by the
* start and end points of the faked ways.
* @param logLevel the logging level
* @param fakeWay a way composed by other ways with faked ids
*/
private void logFakeWayDetails(Level logLevel, JoinedWay fakeWay) {
if (log.isLoggable(logLevel) == false) {
return;
}

// only log if this is an artificial multipolygon
if (FakeIdGenerator.isFakeId(getId()) == false) {
return;
}

boolean containsOrgFakeWay = false;
for (Way orgWay : fakeWay.getOriginalWays()) {
if (FakeIdGenerator.isFakeId(orgWay.getId())) {
containsOrgFakeWay = true;
}
}

if (containsOrgFakeWay == false) {
return;
}

// the fakeWay consists only of other faked ways
// there should be more information about these ways
// so that it is possible to retrieve the original
// OSM ways
// => log the start and end points

for (Way orgWay : fakeWay.getOriginalWays()) {
log.log(logLevel, " Way",orgWay.getId(),"is composed of other artificial ways. Details:");
log.log(logLevel, " Start:",orgWay.getPoints().get(0).toOSMURL());
if (orgWay.hasEqualEndPoints()) {
// the way is closed so start and end are equal - log the point in the middle of the way
int mid = orgWay.getPoints().size()/2;
log.log(logLevel, " Mid: ",orgWay.getPoints().get(mid).toOSMURL());
} else {
log.log(logLevel, " End: ",orgWay.getPoints().get(orgWay.getPoints().size()-1).toOSMURL());
}
}
}

protected void tagOuterWays() {
Map<String, String> tags;
if (hasStyleRelevantTags(this)) {
tags = new HashMap<>();
for (Entry<String, String> relTag : getTagEntryIterator()) {
tags.put(relTag.getKey(), relTag.getValue());
}
} else {
tags = JoinedWay.getMergedTags(outerWaysForLineTagging);
}

// Go through all original outer ways, create a copy, tag them
// with the mp tags and mark them only to be used for polyline processing
// This enables the style file to decide if the polygon information or
// the simple line information should be used.
for (Way orgOuterWay : outerWaysForLineTagging) {
Way lineTagWay = new Way(getOriginalId(), orgOuterWay.getPoints());
lineTagWay.setFakeId();
lineTagWay.addTag(STYLE_FILTER_TAG, STYLE_FILTER_LINE);
lineTagWay.addTag(MP_CREATED_TAG, "true");
for (Entry<String,String> tag : tags.entrySet()) {
lineTagWay.addTag(tag.getKey(), tag.getValue());

// remove the tag from the original way if it has the same value
if (tag.getValue().equals(orgOuterWay.getTag(tag.getKey()))) {
removeTagsInOrgWays(orgOuterWay, tag.getKey());
}
}

if (log.isDebugEnabled())
log.debug("Add line way", lineTagWay.getId(), lineTagWay.toTagString());
tileWayMap.put(lineTagWay.getId(), lineTagWay);
}
}

/**
* Marks all tags of the original ways of the given JoinedWay that are also
* contained in the given tagElement for removal.
*
* @param tagElement
* an element contains the tags to be removed
* @param way
* a joined way
*/
private void removeTagsInOrgWays(Element tagElement, JoinedWay way) {
for (Entry<String, String> tag : tagElement.getTagEntryIterator()) {
removeTagInOrgWays(way, tag.getKey(), tag.getValue());
}
}

/**
* Mark the given tag of all original ways of the given JoinedWay.
*
* @param way
* a joined way
* @param tagname
* the tag to be removed
* @param tagvalue
* the value of the tag to be removed
*/
private void removeTagInOrgWays(JoinedWay way, String tagname,
String tagvalue) {
for (Way w : way.getOriginalWays()) {
if (w instanceof JoinedWay) {
// remove the tags recursively
removeTagInOrgWays((JoinedWay) w, tagname, tagvalue);
continue;
}

if (tagvalue.equals(w.getTag(tagname))) {
if (log.isDebugEnabled()) {
log.debug("Will remove", tagname + "=" + w.getTag(tagname), "from way", w.getId(), w.toTagString());
}
removeTagsInOrgWays(w, tagname);
}
}
}

protected void removeTagsInOrgWays(Way way, String tag) {
if (tag == null || tag.isEmpty()) {
return;
}
String tagsToRemove = way.getTag(ElementSaver.MKGMAP_REMOVE_TAG_KEY);

if (tagsToRemove == null) {
tagsToRemove = tag;
} else if (tag.equals(tagsToRemove)) {
return;
} else {
String[] keys = tagsToRemove.split(";");
if (Arrays.asList(keys).contains(tag)) {
return;
}
tagsToRemove += ";" + tag;
}
way.addTag(ElementSaver.MKGMAP_REMOVE_TAG_KEY, tagsToRemove);
}

/**
* Flag if the area size of the mp should be calculated and added as tag.
* @return {@code true} area size should be calculated; {@code false} area size should not be calculated
*/
protected boolean isAreaSizeCalculated() {
return true;
}

protected Map<Long, Way> getTileWayMap() {
return tileWayMap;
}

protected Map<Long, Way> getMpPolygons() {
return mpPolygons;
}

protected uk.me.parabola.imgfmt.app.Area getTileBounds() {
return tileBounds;
}

/**
* Calculates a unitless number that gives a value for the size
* of the area. The calculation does not correct to any earth
* coordinate system. It uses the simple rectangular coordinate
* system of garmin coordinates.
*
* @param polygon the points of the area
* @return the size of the area (unitless)
*/
public static double calcAreaSize(List<Coord> polygon) {
if (polygon.size() < 4 || polygon.get(0) != polygon.get(polygon.size()-1)) {
return 0; // line or not closed
}
long area = 0;
Iterator<Coord> polyIter = polygon.iterator();
Coord c2 = polyIter.next();
while (polyIter.hasNext()) {
Coord c1 = c2;
c2 = polyIter.next();
area += (long) (c2.getHighPrecLon() + c1.getHighPrecLon())
* (c1.getHighPrecLat() - c2.getHighPrecLat());
}
// convert from high prec to value in map units
double areaSize = (double) area / (2 * (1<<Coord.DELTA_SHIFT) * (1<<Coord.DELTA_SHIFT));
return Math.abs(areaSize);
}

/**
* This is a helper class that gives access to the original
* segments of a joined way.
*/
public static final class JoinedWay extends Way {
private final List<Way> originalWays;
private boolean closedArtificially;

private int minLat;
private int maxLat;
private int minLon;
private int maxLon;
private Rectangle bounds;

public JoinedWay(Way originalWay) {
super(originalWay.getOriginalId(), originalWay.getPoints());
setFakeId();
originalWays = new ArrayList<>();
addWay(originalWay);

// we have to initialize the min/max values
Coord c0 = originalWay.getPoints().get(0);
minLat = maxLat = c0.getLatitude();
minLon = maxLon = c0.getLongitude();

updateBounds(originalWay.getPoints());
}

public void addPoint(int index, Coord point) {
getPoints().add(index, point);
updateBounds(point);
}

public void addPoint(Coord point) {
super.addPoint(point);
updateBounds(point);
}

private void updateBounds(List<Coord> pointList) {
for (Coord c : pointList) {
updateBounds(c.getLatitude(),c.getLongitude());
}
}

private void updateBounds (JoinedWay other){
updateBounds(other.minLat,other.minLon);
updateBounds(other.maxLat,other.maxLon);
}

private void updateBounds(int lat, int lon) {
if (lat < minLat) {
minLat = lat;
bounds = null;
} else if (lat > maxLat) {
maxLat = lat;
bounds = null;
}

if (lon < minLon) {
minLon = lon;
bounds = null;
} else if (lon > maxLon) {
maxLon = lon;
bounds = null;
}

}
private void updateBounds(Coord point) {
updateBounds(point.getLatitude(), point.getLongitude());
}

/**
* Checks if this way intersects the given bounding box at least with
* one point.
*
* @param bbox
* the bounding box
* @return <code>true</code> if this way intersects or touches the
* bounding box; <code>false</code> else
*/
public boolean intersects(uk.me.parabola.imgfmt.app.Area bbox) {
return (maxLat >= bbox.getMinLat() &&
minLat <= bbox.getMaxLat() &&
maxLon >= bbox.getMinLong() &&
minLon <= bbox.getMaxLong());
}

public Rectangle getBounds() {
if (bounds == null) {
// note that we increase the rectangle by 1 because intersects
// checks
// only the interior
bounds = new Rectangle(minLon - 1, minLat - 1, maxLon - minLon
+ 2, maxLat - minLat + 2);
}

return bounds;
}

public boolean linePossiblyIntersectsWay(Coord p1, Coord p2) {
return getBounds().intersectsLine(p1.getLongitude(),
p1.getLatitude(), p2.getLongitude(), p2.getLatitude());
}

public void addWay(Way way) {
if (way instanceof JoinedWay) {
for (Way w : ((JoinedWay) way).getOriginalWays()) {
addWay(w);
}
updateBounds((JoinedWay)way);
} else {
if (log.isDebugEnabled()) {
log.debug("Joined", this.getId(), "with", way.getId());
}
this.originalWays.add(way);
}
}

public void closeWayArtificially() {
addPoint(getPoints().get(0));
closedArtificially = true;
}

public boolean isClosedArtificially() {
return closedArtificially;
}

public static Map<String,String> getMergedTags(Collection<Way> ways) {
Map<String,String> mergedTags = new HashMap<>();
boolean first = true;
for (Way way : ways) {
if (first) {
// the tags of the first way are copied completely
for (Map.Entry<String, String> tag : way.getTagEntryIterator()) {
mergedTags.put(tag.getKey(), tag.getValue());
}
first = false;
} else {
// for all other ways all non matching tags are removed
ArrayList<String> tagsToRemove = null;
for (Map.Entry<String, String> tag : mergedTags.entrySet()) {
String wayTagValue = way.getTag(tag.getKey());
if (!tag.getValue().equals(wayTagValue)) {
// the tags are different
if (wayTagValue!= null) {
if (tagsToRemove == null) {
tagsToRemove=new ArrayList<>();
}
tagsToRemove.add(tag.getKey());
}
}
}
if (tagsToRemove!=null) {
for (String tag : tagsToRemove) {
mergedTags.remove(tag);
}
}
}
}
return mergedTags;
}

/**
* Tags this way with a merge of the tags of all original ways.
*/
public void mergeTagsFromOrgWays() {
if (log.isDebugEnabled()) {
log.debug("Way",getId(),"merge tags from",getOriginalWays().size(),"ways");
}
removeAllTags();

Map<String,String> mergedTags = getMergedTags(getOriginalWays());
for (Entry<String,String> tag : mergedTags.entrySet()) {
addTag(tag.getKey(),tag.getValue());
}
}

public List<Way> getOriginalWays() {
return originalWays;
}

/**
* Retrieves a measurement of the area covered by this polygon. The
* returned value has no unit. It is just a rough comparable value
* because it uses a rectangular coordinate system without correction.
* @return size of the covered areas (0 if the way is not closed)
*/
public double getSizeOfArea() {
return MultiPolygonRelation.calcAreaSize(getPoints());
}

public String toString() {
StringBuilder sb = new StringBuilder(200);
sb.append(getId());
sb.append("(");
sb.append(getPoints().size());
sb.append("P)(");
boolean first = true;
for (Way w : getOriginalWays()) {
if (first) {
first = false;
} else {
sb.append(",");
}
sb.append(w.getId());
sb.append("[");
sb.append(w.getPoints().size());
sb.append("P]");
}
sb.append(")");
return sb.toString();
}
}

public static class PolygonStatus {
public final boolean outer;
public final int index;
public final JoinedWay polygon;

public PolygonStatus(boolean outer, int index, JoinedWay polygon) {
this.outer = outer;
this.index = index;
this.polygon = polygon;
}

public String toString() {
return polygon+"_"+outer;
}
}
}

Subversion Repositories mkgmap

(root)/branches/default-typ/src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java - Rev 4246