The attached patch (against the mp branch) replaces the current approach
of the multipolygon code (just connecting the inner and outer ways, thus
forming polygons with overlapping segments) by a decomposition approach:
The "polygon with holes" is decomposed into "simple" polygons without holes.
To make the further development easier, I have put the decomposition
code into a separate class PolygonDecomposer.
The decomposition code does not yet handle all possible cases - it just
cuts off a quadrilateral for each inner way (which is not much different
from the old approach) and does not yet check wether this quadrilateral
contains or intersects any of the other holes.It should, however,
already work for "normal" cases where the holes are not too complex.
Best wishes
Christian
Index: src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
===================================================================
--- src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
(Revision 1457)
+++ src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
(Arbeitskopie)
@@ -349,44 +348,39 @@
unfinishedRings.andNot(innerIndexes);
// now construct the outer polygon with its
holes
- for (Way innerRing : innerRings) {
- int[] insert =
findCpa(outerRing.getPoints(), innerRing
- .getPoints());
- if (insert[0] >= 0 && insert[1] >= 0) {
- insertPoints(outerRing,
innerRing, insert[0], insert[1]);
- }
- }
-
- // set the tags of the outer ring
- // does the multipolygon itself have any tags?
- boolean validTagFound = false;
- for (Map.Entry<String, String> tagEntry :
getEntryIteratable()) {
+ List<Way> decomposition =
PolygonDecomposer.decompose(outerRing, innerRings);
+ myWayMap.remove(outerRing.getId());
+ for (Way way : decomposition) {
+ // set the tags of the outer ring
+ // does the multipolygon itself have any
tags?
+ boolean validTagFound = false;
+ for (Map.Entry<String, String> tagEntry :
getEntryIteratable()) {
if
(relationTags.contains(tagEntry.getKey())) {
- validTagFound = true;
- break;
+ validTagFound = true;
+ break;
}
- }
+ }
- if (validTagFound) {
+ if (validTagFound) {
// the multipolygon contains tags that
overwhelm the tags
// out the outer ring
- outerRing.copyTags(this);
- } else {
+ way.copyTags(this);
+ } else {
// the multipolygon does not contain
any relevant tag
// use the segments of the outer ring
and merge the tags
for (Way outerRingSegment :
outerRing.getOriginalWays()) {
- // TODO uuh, this is bad => the
last of the outer ring
- // segments win
- // => any better idea?
- for (Map.Entry<String, String>
outSegmentTag : outerRingSegment
-
.getEntryIteratable()) {
-
outerRing.addTag(outSegmentTag.getKey(),
-
outSegmentTag.getValue());
- }
+ // TODO uuh, this is bad => the
last of the outer ring
+ // segments win
+ // => any better idea?
+ for (Map.Entry<String, String>
outSegmentTag : outerRingSegment
+ .getEntryIteratable()) {
+
way.addTag(outSegmentTag.getKey(),
+
outSegmentTag.getValue());
+ }
}
+ }
+ polygonResults.add(way);
}
-
- polygonResults.add(outerRing);
}
}
@@ -601,11 +595,11 @@
* This is a helper class that stores that gives access to the original
segments
* of a joined way.
*/
- private static class JoinedWay extends Way {
+ private static class JoinedWay extends Way {
private final List<Way> originalWays;
public JoinedWay(Way originalWay) {
- super(-originalWay.getId(), new
ArrayList<Coord>(originalWay
+ super(originalWay.getId(), new
ArrayList<Coord>(originalWay
.getPoints()));
this.originalWays = new ArrayList<Way>();
this.originalWays.add(originalWay);
Index: src/uk/me/parabola/mkgmap/reader/osm/Way.java
===================================================================
--- src/uk/me/parabola/mkgmap/reader/osm/Way.java (Revision 1457)
+++ src/uk/me/parabola/mkgmap/reader/osm/Way.java (Arbeitskopie)
@@ -91,7 +91,7 @@
public void reverse() {
int numPoints = points.size();
- for(int i = 0; i < numPoints/2; ++i) {
+ for (int i = 0; i < numPoints/2; ++i) {
Coord t = points.get(i);
points.set(i, points.get(numPoints - 1 - i));
points.set(numPoints - 1 - i, t);
@@ -102,7 +102,21 @@
return !points.isEmpty() &&
points.get(0).equals(points.get(points.size()-1));
}
+ /** Check wether a (closed) way is ordered clockwise.
+ * @return true, if the way is ordered clockwise.
+ */
+ public boolean isClockwise() {
+ double sum = 0;
+ int numPoints = points.size();
+ for (int i=0; i < numPoints-1; i++) {
+ Coord p1 = points.get(i);
+ Coord p2 = points.get(i+1);
+ sum += p2.getLongitude()*p1.getLatitude() -
p1.getLongitude()*p2.getLatitude();
+ }
+ return sum > 0;
+ }
+
/**
* A simple representation of this way.
* @return A string with the name and start point
/*
* Copyright (C) 2010 Christian Gawron
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2 as
* published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
*
* Author: Christian Gawron
* Create date: Jan 1, 2010
*/
package uk.me.parabola.mkgmap.reader.osm;
import java.util.List;
import java.util.Map;
import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.log.Logger;
/** Decompose a polygon (with holes) into simple components */
public class PolygonDecomposer
{
private static final Logger log = Logger.getLogger(PolygonDecomposer.class);
/**
* Decompose the given polygon and place the resulting shapes in the
outputs list.
* @param shape The original shape (with holes).
* @param outputs The output list consisting of polygons without holes.
*/
public static List<Way> decompose(Way outer, List<? extends Way> inners)
{
/*
* Idea:
*
* while there is outer way with an inner way do
* choose an inner way
* find the closest points of approach between inner and outer (Pi
and Po)
* connect a segment of the outer ring at Po to a segment at Pi to
create a quadrilateral shape, add it to the result
* merge the rest of the hole into the outer way (this removes the
hole)
* remove the inner way from the list
*
* This basic approach has to be refined somewhat:
* - The quadrilateral could in principle contain or even intersect
some of the remaining holes.
*/
log.info(String.format("polygon decomposer: %d inner ways",
inners.size()));
List<Way> result = new java.util.ArrayList<Way>();
Map<Way, Way> isInMap = new java.util.HashMap<Way, Way>();
List<Way> outers = new java.util.ArrayList<Way>();
if (!outer.isClockwise()) {
log.warn("outer way not clockwise, reversing it");
outer.reverse();
}
outers.add(outer);
result.add(outer);
for (Way inner : inners) {
if (inner.isClockwise()) {
log.warn("inner way not counter-clockwise, reversing it");
inner.reverse();
}
isInMap.put(inner, outer);
}
while (inners.size() > 0) {
Way inner = inners.remove(0);
log.info("processing inner way " + inner);
int[] insert = findCpa(outer.getPoints(), inner.getPoints());
int o0 = insert[0];
int o1 = o0 > 0 ? o0-1 : outer.getPoints().size()-1;
int i0 = insert[1];
int i1 = i0 < inner.getPoints().size()-1 ? i0+1 : 0;
Way quadrilateral = new Way(inner.getId());
// TODO: check for intersections!!
List<Coord> outList = outer.getPoints();
List<Coord> inList = inner.getPoints();
quadrilateral.addPoint(outList.get(o0));
quadrilateral.addPoint(inList.get(i0));
quadrilateral.addPoint(inList.get(i1));
quadrilateral.addPoint(outList.get(o1));
quadrilateral.addPoint(outList.get(o0));
result.add(quadrilateral);
outers.add(quadrilateral);
// TODO: check if the quadrilateral contains some of the inner ways!
int index = o1 + 1;
for (int i=i1; i < inList.size(); i++) {
outList.add(index++, inList.get(i));
}
for (int i=0; i < i0; i++) {
outList.add(index++, inList.get(i));
}
}
return result;
}
/**
* find the Closest Point of Approach between two coordinate-lists This will
* probably be moved to a Utils class
*
* @param l1
* First list of points.
* @param l2
* Second list of points.
* @return The first element is the index in l1, the second in l2 which are
* the closest together.
*/
private static int[] findCpa(List<Coord> l1, List<Coord> l2) {
double oldDistance = Double.MAX_VALUE;
Coord found1 = null;
Coord found2 = null;
for (Coord c1 : l1) {
for (Coord c2 : l2) {
double newDistance = c1.distanceInDegreesSquared(c2);
if (newDistance < oldDistance) {
oldDistance = newDistance;
found1 = c1;
found2 = c2;
}
}
}
return new int[] { l1.indexOf(found1), l2.indexOf(found2) };
}
}
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
