Ignore:
Timestamp:
2014-05-02T16:52:55+02:00 (6 years ago)
Author:
Balaitous
Message:

fix #9951 - "Join Overlapping Areas" gives strange multipolygons

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java

    r7025 r7052  
    185185     * Assumes you are going in clockwise orientation.
    186186     * @author viesturs
    187      *
    188187     */
    189188    private static class WayTraverser {
    190189
     190        /** Set of {@link WayInPolygon} to be joined by walk algorithm */
    191191        private Set<WayInPolygon> availableWays;
     192        /** Current state of walk algorithm */
    192193        private WayInPolygon lastWay;
     194        /** Direction of current way */
    193195        private boolean lastWayReverse;
    194196
     197        /** Constructor */
    195198        public WayTraverser(Collection<WayInPolygon> ways) {
    196 
    197199            availableWays = new HashSet<>(ways);
    198200            lastWay = null;
    199201        }
    200202
     203        /**
     204         *  Remove ways from available ways
     205         *  @param ways Collection of WayInPolygon
     206         */
    201207        public void removeWays(Collection<WayInPolygon> ways) {
    202208            availableWays.removeAll(ways);
    203209        }
    204210
     211        /**
     212         * Remove a single way from available ways
     213         * @param way WayInPolygon
     214         */
    205215        public void removeWay(WayInPolygon way) {
    206216            availableWays.remove(way);
    207217        }
    208218
     219        /**
     220         * Reset walk algorithm to a new start point
     221         * @param way New start point
     222         */
    209223        public void setStartWay(WayInPolygon way) {
    210224            lastWay = way;
     
    212226        }
    213227
     228        /**
     229         * Reset walk algorithm to a new start point.
     230         * @return The new start point or null if no available way remains
     231         */
    214232        public WayInPolygon startNewWay() {
    215233            if (availableWays.isEmpty()) {
     
    224242
    225243        /**
     244         * Walking through {@link WayInPolygon} segments, head node is the current position
     245         * @return Head node
     246         */
     247        private Node getHeadNode() {
     248            return !lastWayReverse ? lastWay.way.lastNode() : lastWay.way.firstNode();
     249        }
     250
     251        /**
     252         * Node just before head node.
     253         * @return Previous node
     254         */
     255        private Node getPrevNode() {
     256            return !lastWayReverse ? lastWay.way.getNode(lastWay.way.getNodesCount() - 2) : lastWay.way.getNode(1);
     257        }
     258
     259        /**
     260         * Oriented angle (N1N2, N1N3) in range [0; 2*Math.PI[
     261         */
     262        private static double getAngle(Node N1, Node N2, Node N3) {
     263            EastNorth en1 = N1.getEastNorth();
     264            EastNorth en2 = N2.getEastNorth();
     265            EastNorth en3 = N3.getEastNorth();
     266            double angle = Math.atan2(en3.getY() - en1.getY(), en3.getX() - en1.getX()) -
     267                    Math.atan2(en2.getY() - en1.getY(), en2.getX() - en1.getX());
     268            while(angle >= 2*Math.PI)
     269                angle -= 2*Math.PI;
     270            while(angle < 0)
     271                angle += 2*Math.PI;
     272            return angle;
     273        }
     274
     275        /**
    226276         * Get the next way creating a clockwise path, ensure it is the most right way. #7959
    227277         * @return The next way.
    228278         */
    229279        public  WayInPolygon walk() {
    230             Node headNode = !lastWayReverse ? lastWay.way.lastNode() : lastWay.way.firstNode();
    231             Node prevNode = !lastWayReverse ? lastWay.way.getNode(lastWay.way.getNodesCount() - 2) : lastWay.way.getNode(1);
     280            Node headNode = getHeadNode();
     281            Node prevNode = getPrevNode();
    232282
    233283            double headAngle = Math.atan2(headNode.getEastNorth().east() - prevNode.getEastNorth().east(),
     
    276326            lastWay = bestWay;
    277327            lastWayReverse = bestWayReverse;
    278 
    279328            return lastWay;
     329        }
     330
     331        /**
     332         * Search for an other way coming to the same head node at left side from last way. #9951
     333         * @return left way or null if none found
     334         */
     335        public WayInPolygon leftComingWay() {
     336            Node headNode = getHeadNode();
     337            Node prevNode = getPrevNode();
     338
     339            WayInPolygon mostLeft = null; // most left way connected to head node
     340            boolean comingToHead = false; // true if candidate come to head node
     341            double angle = 2*Math.PI;
     342
     343            for (WayInPolygon candidateWay : availableWays) {
     344                boolean candidateComingToHead;
     345                Node candidatePrevNode;
     346
     347                if(candidateWay.way.firstNode().equals(headNode)) {
     348                    candidateComingToHead = !candidateWay.insideToTheRight;
     349                    candidatePrevNode = candidateWay.way.getNode(1);
     350                } else if(candidateWay.way.lastNode().equals(headNode)) {
     351                     candidateComingToHead = candidateWay.insideToTheRight;
     352                     candidatePrevNode = candidateWay.way.getNode(candidateWay.way.getNodesCount() - 2);
     353                } else
     354                    continue;
     355                if(candidateWay.equals(lastWay) && candidateComingToHead)
     356                    continue;
     357
     358                double candidateAngle = getAngle(headNode, candidatePrevNode, prevNode);
     359
     360                if(mostLeft == null || candidateAngle < angle || (candidateAngle == angle && !candidateComingToHead)) {
     361                    // Candidate is most left
     362                    mostLeft = candidateWay;
     363                    comingToHead = candidateComingToHead;
     364                    angle = candidateAngle;
     365                }
     366            }
     367
     368            return comingToHead ? mostLeft : null;
    280369        }
    281370    }
     
    9591048     * @return A list of ways that form the outer and inner boundaries of the multigon.
    9601049     */
    961     public static List<AssembledPolygon> findBoundaryPolygons(Collection<WayInPolygon> multigonWays, List<Way> discardedResult) {
     1050    public static List<AssembledPolygon> findBoundaryPolygons(Collection<WayInPolygon> multigonWays,
     1051            List<Way> discardedResult) {
    9621052        //first find all discardable ways, by getting outer shells.
    9631053        //this will produce incorrect boundaries in some cases, but second pass will fix it.
     
    9801070        while((startWay = traverser.startNewWay()) != null) {
    9811071            ArrayList<WayInPolygon> path = new ArrayList<>();
     1072            List<WayInPolygon> startWays = new ArrayList<>();
    9821073            path.add(startWay);
    9831074            while(true) {
     1075                WayInPolygon leftComing;
     1076                while((leftComing = traverser.leftComingWay()) != null) {
     1077                    if(startWays.contains(leftComing))
     1078                        break;
     1079                    // Need restart traverser walk
     1080                    path.clear();
     1081                    path.add(leftComing);
     1082                    traverser.setStartWay(leftComing);
     1083                    startWays.add(leftComing);
     1084                    break;
     1085                }
    9841086                WayInPolygon nextWay = traverser.walk();
    9851087                if(nextWay == null)
    9861088                    throw new RuntimeException("Join areas internal error.");
    9871089                if(path.get(0) == nextWay) {
     1090                    // path is closed -> stop here
    9881091                    AssembledPolygon ring = new AssembledPolygon(path);
    9891092                    if(ring.getNodes().size() <= 2) {
Note: See TracChangeset for help on using the changeset viewer.