Index: trunk/src/org/openstreetmap/josm/data/osm/BBox.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/osm/BBox.java	(revision 2981)
+++ trunk/src/org/openstreetmap/josm/data/osm/BBox.java	(revision 2982)
@@ -67,4 +67,9 @@
         ymax = Math.max(ymax, y);
         sanity();
+    }
+
+    public void add(BBox box) {
+        add(box.getTopLeft());
+        add(box.getBottomRight());
     }
 
@@ -139,4 +144,18 @@
 
     @Override
+    public int hashCode() {
+        return (int)(ymin * xmin);
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (o instanceof BBox) {
+            BBox b = (BBox)o;
+            return b.xmax == xmax && b.ymax == ymax && b.xmin == xmin && b.ymin == ymin;
+        } else
+            return false;
+    }
+
+    @Override
     public String toString() {
         return "[ x: " + xmin + " -> " + xmax +
Index: trunk/src/org/openstreetmap/josm/data/osm/DataSet.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/osm/DataSet.java	(revision 2981)
+++ trunk/src/org/openstreetmap/josm/data/osm/DataSet.java	(revision 2982)
@@ -136,4 +136,15 @@
     }
 
+    public List<Relation> searchRelations(BBox bbox) {
+        // QuadBuckets might be useful here (don't forget to do reindexing after some of rm is changed)
+        List<Relation> result = new ArrayList<Relation>();
+        for (Relation r: relations) {
+            if (r.getBBox().intersects(bbox)) {
+                result.add(r);
+            }
+        }
+        return result;
+    }
+
     /**
      * All data sources of this DataSet.
@@ -200,5 +211,5 @@
      * Adds a primitive to the dataset
      *
-     * @param primitive the primitive. Ignored if null.
+     * @param primitive the primitive.
      */
     public void addPrimitive(OsmPrimitive primitive) {
@@ -779,33 +790,36 @@
     }
 
-    /**
-     * Reindex all nodes and ways after their coordinates were changed. This is a temporary solution, reindexing should
-     * be automatic in the future
-     * @deprecated Reindexing should be automatic
-     */
-    @Deprecated
-    public void reindexAll() {
-        List<Node> ntmp = new ArrayList<Node>(nodes);
-        nodes.clear();
-        nodes.addAll(ntmp);
-        List<Way> wtmp = new ArrayList<Way>(ways);
-        ways.clear();
-        ways.addAll(wtmp);
-    }
-
     private void reindexNode(Node node) {
         nodes.remove(node);
         nodes.add(node);
-        for (Way way:OsmPrimitive.getFilteredList(node.getReferrers(), Way.class)) {
-            ways.remove(way);
-            way.updatePosition();
-            ways.add(way);
+        for (OsmPrimitive primitive: node.getReferrers()) {
+            if (primitive instanceof Way) {
+                reindexWay((Way)primitive);
+            } else {
+                reindexRelation((Relation) primitive);
+            }
         }
     }
 
     private void reindexWay(Way way) {
+        BBox before = way.getBBox();
         ways.remove(way);
         way.updatePosition();
         ways.add(way);
+        if (!way.getBBox().equals(before)) {
+            for (OsmPrimitive primitive: way.getReferrers()) {
+                reindexRelation((Relation)primitive);
+            }
+        }
+    }
+
+    private void reindexRelation(Relation relation) {
+        BBox before = relation.getBBox();
+        relation.updatePosition();
+        if (!before.equals(relation.getBBox())) {
+            for (OsmPrimitive primitive: relation.getReferrers()) {
+                reindexRelation((Relation) primitive);
+            }
+        }
     }
 
@@ -874,4 +888,5 @@
 
     void fireRelationMembersChanged(Relation r) {
+        reindexRelation(r);
         fireEvent(new RelationMembersChangedEvent(this, r));
     }
Index: trunk/src/org/openstreetmap/josm/data/osm/Relation.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/osm/Relation.java	(revision 2981)
+++ trunk/src/org/openstreetmap/josm/data/osm/Relation.java	(revision 2982)
@@ -23,4 +23,6 @@
      */
     private final List<RelationMember> members = new ArrayList<RelationMember>();
+
+    private BBox bbox;
 
     /**
@@ -336,10 +338,38 @@
     @Override
     public BBox getBBox() {
-        return new BBox(0, 0, 0, 0);
+        if (bbox == null) {
+            calculateBBox(new HashSet<PrimitiveId>());
+            if (bbox == null) {
+                bbox = new BBox(0, 0, 0, 0); // No members
+            }
+        }
+        return  bbox;
+    }
+
+    private BBox calculateBBox(Set<PrimitiveId> visitedRelations) {
+        if (visitedRelations.contains(this))
+            return null;
+        visitedRelations.add(this);
+        if (members.isEmpty())
+            return null;
+        else {
+            BBox result = null;
+            for (RelationMember rm:members) {
+                BBox box = rm.isRelation()?rm.getRelation().calculateBBox(visitedRelations):rm.getMember().getBBox();
+                if (box != null) {
+                    if (result == null) {
+                        result = box;
+                    } else {
+                        result.add(box);
+                    }
+                }
+            }
+            return result;
+        }
     }
 
     @Override
     public void updatePosition() {
-        // Do nothing for now
+        bbox = calculateBBox(new HashSet<PrimitiveId>());
     }
 
@@ -355,5 +385,5 @@
             for (RelationMember rm: members) {
                 if (rm.getMember().getDataSet() != dataSet)
-                    throw new DataIntegrityProblemException("Relation member must be part of the same dataset as relation");
+                    throw new DataIntegrityProblemException(String.format("Relation member must be part of the same dataset as relation(%s, %s)", getPrimitiveId(), rm.getMember().getPrimitiveId()));
             }
         }
Index: trunk/src/org/openstreetmap/josm/data/osm/visitor/paint/MapPaintVisitor.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/osm/visitor/paint/MapPaintVisitor.java	(revision 2981)
+++ trunk/src/org/openstreetmap/josm/data/osm/visitor/paint/MapPaintVisitor.java	(revision 2982)
@@ -244,4 +244,5 @@
 
     public void drawRestriction(Relation r) {
+
         Way fromWay = null;
         Way toWay = null;
@@ -674,5 +675,5 @@
 
             /*** RELATIONS ***/
-            for (final Relation osm: data.getRelations()) {
+            for (final Relation osm: data.searchRelations(bbox)) {
                 if (osm.isDrawable()) {
                     paintUnselectedRelation(osm);
@@ -699,5 +700,5 @@
 
             /*** RELATIONS ***/
-            for (final Relation osm: data.getRelations()) {
+            for (final Relation osm: data.searchRelations(bbox)) {
                 if (osm.isDrawable()) {
                     paintUnselectedRelation(osm);
Index: trunk/src/org/openstreetmap/josm/gui/conflict/pair/ListMerger.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/conflict/pair/ListMerger.java	(revision 2981)
+++ trunk/src/org/openstreetmap/josm/gui/conflict/pair/ListMerger.java	(revision 2982)
@@ -641,5 +641,5 @@
             ImageIcon icon = ImageProvider.get("dialogs/conflict", "useallleft.png");
             putValue(Action.SMALL_ICON, icon);
-            putValue(Action.SHORT_DESCRIPTION, tr("Use all mine elements"));
+            putValue(Action.SHORT_DESCRIPTION, tr("Use all my elements"));
         }
 
Index: trunk/src/org/openstreetmap/josm/gui/layer/OsmDataLayer.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/layer/OsmDataLayer.java	(revision 2981)
+++ trunk/src/org/openstreetmap/josm/gui/layer/OsmDataLayer.java	(revision 2982)
@@ -397,32 +397,33 @@
     protected PurgePrimitivesCommand buildPurgeCommand() {
         ArrayList<OsmPrimitive> toPurge = new ArrayList<OsmPrimitive>();
-        conflictLoop: for (Conflict<?> c: conflicts) {
-            if (c.getMy().isDeleted() && !c.getTheir().isVisible()) {
-                // Local and server version of the primitive are deleted. We
-                // can purge it from the local dataset.
-                //
-                toPurge.add(c.getMy());
-            } else if (!c.getMy().isModified() && ! c.getTheir().isVisible()) {
-                // We purge deleted *ways* and *relations* automatically if they are
-                // deleted on the server and if they aren't modified in the local
-                // dataset.
-                //
-                if (c.getMy() instanceof Way || c.getMy() instanceof Relation) {
+        conflictLoop:
+            for (Conflict<?> c: conflicts) {
+                if (c.getMy().isDeleted() && !c.getTheir().isVisible()) {
+                    // Local and server version of the primitive are deleted. We
+                    // can purge it from the local dataset.
+                    //
                     toPurge.add(c.getMy());
-                    continue conflictLoop;
-                }
-                // We only purge nodes if they aren't part of a modified way.
-                // Otherwise the number of nodes of a modified way could drop
-                // below 2 and we would lose the modified data when the way
-                // gets purged.
-                //
-                for (OsmPrimitive parent: c.getMy().getReferrers()) {
-                    if (parent.isModified() && parent instanceof Way) {
+                } else if (!c.getMy().isModified() && ! c.getTheir().isVisible()) {
+                    // We purge deleted *ways* and *relations* automatically if they are
+                    // deleted on the server and if they aren't modified in the local
+                    // dataset.
+                    //
+                    if (c.getMy() instanceof Way || c.getMy() instanceof Relation) {
+                        toPurge.add(c.getMy());
                         continue conflictLoop;
                     }
+                    // We only purge nodes if they aren't part of a modified way.
+                    // Otherwise the number of nodes of a modified way could drop
+                    // below 2 and we would lose the modified data when the way
+                    // gets purged.
+                    //
+                    for (OsmPrimitive parent: c.getMy().getReferrers()) {
+                        if (parent.isModified() && parent instanceof Way) {
+                            continue conflictLoop;
+                        }
+                    }
+                    toPurge.add(c.getMy());
                 }
-                toPurge.add(c.getMy());
-            }
-        }
+            }
         if (toPurge.isEmpty()) return null;
         PurgePrimitivesCommand cmd = new PurgePrimitivesCommand(this, toPurge);
Index: trunk/test/unit/org/openstreetmap/josm/data/osm/RelationTest.java
===================================================================
--- trunk/test/unit/org/openstreetmap/josm/data/osm/RelationTest.java	(revision 2981)
+++ trunk/test/unit/org/openstreetmap/josm/data/osm/RelationTest.java	(revision 2982)
@@ -2,9 +2,12 @@
 package org.openstreetmap.josm.data.osm;
 
+import static org.junit.Assert.assertFalse;
+
+import org.junit.Assert;
 import org.junit.Test;
-
-import static org.junit.Assert.*;
+import org.openstreetmap.josm.data.coor.LatLon;
 
 public class RelationTest {
+
     @Test(expected=NullPointerException.class)
     public void createNewRelation() {
@@ -18,3 +21,47 @@
     }
 
+    @Test
+    public void testBBox() {
+        DataSet ds = new DataSet();
+
+        Node n1 = new Node(new LatLon(10, 10));
+        Node n2 = new Node(new LatLon(20, 20));
+        Node n3 = new Node(new LatLon(30, 30));
+        Way w1 = new Way();
+        w1.addNode(n1);
+        w1.addNode(n2);
+        Relation r1 = new Relation();
+        Relation r2 = new Relation();
+        ds.addPrimitive(r1);
+        ds.addPrimitive(r2);
+        ds.addPrimitive(n1);
+        ds.addPrimitive(n2);
+        ds.addPrimitive(n3);
+        ds.addPrimitive(w1);
+        r1.addMember(new RelationMember("", n1));
+        r1.addMember(new RelationMember("", w1));
+        r1.addMember(new RelationMember("", r1));
+        r1.addMember(new RelationMember("", r2));
+        r2.addMember(new RelationMember("", r1));
+        r2.addMember(new RelationMember("", n3));
+
+        BBox bbox = new BBox(w1);
+        bbox.add(n3.getBBox());
+        Assert.assertEquals(bbox, r1.getBBox());
+        Assert.assertEquals(bbox, r2.getBBox());
+
+        n3.setCoor(new LatLon(40, 40));
+        bbox.add(n3.getBBox());
+        Assert.assertEquals(bbox, r1.getBBox());
+        Assert.assertEquals(bbox, r2.getBBox());
+
+        r1.removeMembersFor(r2);
+        Assert.assertEquals(w1.getBBox(), r1.getBBox());
+        Assert.assertEquals(bbox, r2.getBBox());
+
+        w1.addNode(n3);
+        Assert.assertEquals(w1.getBBox(), r1.getBBox());
+        Assert.assertEquals(w1.getBBox(), r2.getBBox());
+    }
+
 }
