Object connections cause moderate viewer lag when downsample factor is less than 1
## IMPORTANT!

* [X] I've definitely found a bug (it you're not sure, please use [image.sc](https://forum.image.sc/tags/qupath) instead)
* [X] I've checked https://qupath.github.io for a new release that might already have fixed the issue
* [X] I've checked the [Changelog](https://github.com/qupath/qupath/blob/master/CHANGELOG.md) to see if the bug has already been fixed in the next release
* [X] I've checked for existing GitHub issues describing the same problem

## Bug report

**Describe the bug**
Object connections cause moderate viewer lag when downsample factor is less than 1, evident when panning. Very minor and niche issue, but I figured I'd open a ticket anyways.

**To Reproduce**
Steps to reproduce the behavior:
1. Run cell detection across a whole-slide annotation
2. Generate object connections via "Delaunay cluster features 2D"
3.  Set viewer downsample factor to 0.99 or less
4. Observe lag when panning. Unchecking "show object connections" or setting a downsample factor greater than or equal to 1 will resolve this issue.

**Expected behavior**
Visualizing objects overlaid onto images shouldn't result in substantial lag

**Screenshots**
Video recording: https://www.youtube.com/watch?v=qOBp2X6HVUc

**Desktop (please complete the following information):**
 - OS: Windows 10
 - QuPath Version: Version: 0.4.0-SNAPSHOT
Build time: 2022-01-24, 13:48

**Additional context**
A 24-class composite classifier, annotation-generating pixel classifier, and several other spatial analyses were also performed.

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 459ec15c..4e106f3a 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -100,6 +100,7 @@ This is a work-in-progress.
 * It isn't possible to run cell detection on channels with " in the name (https://github.com/qupath/qupath/issues/1022)
 * Fix occasional "One of the arguments' values is out of range" exception with Delaunay triangulation
 * The colors used in pie chart legends were sometimes incorrect (https://github.com/qupath/qupath/issues/1062)
+# Delaunay connection lines could be broken or slow to display (https://github.com/qupath/qupath/pull/1069)
 
 ### Changes through Bio-Formats 6.10.1
 * Bio-Formats 6.10.1 brings several important new features to QuPath, including:
diff --git a/qupath-core/src/main/java/qupath/lib/objects/DefaultPathObjectConnectionGroup.java b/qupath-core/src/main/java/qupath/lib/objects/DefaultPathObjectConnectionGroup.java
index e80fe7d8..c7f9bd2e 100644
--- a/qupath-core/src/main/java/qupath/lib/objects/DefaultPathObjectConnectionGroup.java
+++ b/qupath-core/src/main/java/qupath/lib/objects/DefaultPathObjectConnectionGroup.java
@@ -33,14 +33,19 @@ import java.util.Collections;
 import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.Map;
+import java.util.stream.Collectors;
 
+import org.locationtech.jts.geom.Envelope;
+import org.locationtech.jts.index.SpatialIndex;
+import org.locationtech.jts.index.quadtree.Quadtree;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
+import qupath.lib.regions.ImageRegion;
 import qupath.lib.roi.interfaces.ROI;
 
 /**
- * Simple, default implementation of PathObjectConnectionGroup.
+ * Simple, default implementation of {@link PathObjectConnectionGroup}.
  * 
  * @author Pete Bankhead
  *
@@ -53,6 +58,8 @@ public class DefaultPathObjectConnectionGroup implements PathObjectConnectionGro
 	
 	private Map<PathObject, ObjectConnector> map = new LinkedHashMap<>();
 	
+	private transient SpatialIndex index;
+	
 	/**
 	 * Key to use when storing object connections as a property of an ImageData object.
 	 */
@@ -71,11 +78,6 @@ public class DefaultPathObjectConnectionGroup implements PathObjectConnectionGro
 	public DefaultPathObjectConnectionGroup(final PathObjectConnectionGroup connections) {
 		connections.getPathObjects().stream().forEach(p -> map.put(p, new ObjectConnector(p, connections.getConnectedObjects(p))));
 	}
-	
-	private void breakConnection(final PathObject pathObject1, final PathObject pathObject2) {
-		if (map.get(pathObject1).breakConnection(pathObject2))
-			map.get(pathObject2).breakConnection(pathObject1);		
-	}
 
 	@Override
 	public Collection<PathObject> getPathObjects() {
@@ -87,31 +89,68 @@ public class DefaultPathObjectConnectionGroup implements PathObjectConnectionGro
 		ObjectConnector connector = map.get(pathObject);
 		if (connector == null)
 			return Collections.emptyList();
-		return Collections.unmodifiableList(connector.getConnections());
+		return connector.getConnections();
 	}
 	
+	private static double centroidDistanceSquared(final PathObject pathObject1, final PathObject pathObject2) {
+		return centroidDistanceSquared(PathObjectTools.getROI(pathObject1, true), PathObjectTools.getROI(pathObject2, true));
+	}
 	
-	private void sortByDistance() {
-		for (ObjectConnector connector : map.values())
-			connector.sortConnectionsByDistance();
+	private static double centroidDistanceSquared(final ROI roi1, final ROI roi2) {
+		double dx = roi1.getCentroidX() - roi2.getCentroidX();
+		double dy = roi1.getCentroidY() - roi2.getCentroidY();
+		return dx*dx + dy*dy;
 	}
 	
-	private static double centroidDistance(final PathObject pathObject1, final PathObject pathObject2) {
-		return Math.sqrt(centroidDistanceSquared(pathObject1.getROI(), pathObject2.getROI()));
+	
+	@Override
+	public Collection<PathObject> getPathObjectsForRegion(ImageRegion region) {
+		if (index == null) {
+			synchronized(this) {
+				if (index == null)
+					index = buildIndex();
+			}
+		}
+		var envelope = getEnvelope(region);
+		return ((Collection<PathObject>)index.query(envelope))
+				.stream()
+				.filter(p -> p.getROI().getZ() == region.getZ() && p.getROI().getT() == region.getT())
+				.collect(Collectors.toSet());
 	}
 	
-	private static double centroidDistance(final ROI roi1, final ROI roi2) {
-		return Math.sqrt(centroidDistanceSquared(roi1, roi2));
+	
+	private SpatialIndex buildIndex() {
+		long startTime = System.currentTimeMillis();
+		var index = new Quadtree();
+		
+		for (var entry : map.entrySet()) {
+			var pathObject = entry.getKey();
+			var envelope = getEnvelope(pathObject.getROI());
+			
+			var connector = entry.getValue();
+			if (connector != null) {
+				var connectedObjects = connector.getConnections();
+				for (var connected : connectedObjects) {
+					envelope.expandToInclude(getEnvelope(connected.getROI()));
+				}
+			}
+			
+			index.insert(envelope, pathObject);
+		}
+		long endTime = System.currentTimeMillis();
+		logger.debug("Spatial index built in {} ms", endTime - startTime);
+		return index;
 	}
 	
-	private static double centroidDistanceSquared(final PathObject pathObject1, final PathObject pathObject2) {
-		return centroidDistanceSquared(PathObjectTools.getROI(pathObject1, true), PathObjectTools.getROI(pathObject2, true));
+	
+	private static Envelope getEnvelope(ImageRegion region) {
+		return new Envelope(region.getMinX(), region.getMaxX(), region.getMinY(), region.getMaxY());
 	}
 	
-	private static double centroidDistanceSquared(final ROI roi1, final ROI roi2) {
-		double dx = roi1.getCentroidX() - roi2.getCentroidX();
-		double dy = roi1.getCentroidY() - roi2.getCentroidY();
-		return dx*dx + dy*dy;
+	
+	private static Envelope getEnvelope(ROI roi) {
+		return new Envelope(roi.getBoundsX(), roi.getBoundsX() + roi.getBoundsWidth(),
+				roi.getBoundsY(), roi.getBoundsY() + roi.getBoundsHeight());
 	}
 	
 	
@@ -124,6 +163,8 @@ public class DefaultPathObjectConnectionGroup implements PathObjectConnectionGro
 		private PathObject pathObject;
 		private List<PathObject> connections = new ArrayList<>();
 		
+		private transient List<PathObject> connectionsUnmodifiable;
+		
 		public ObjectConnector() {}
 		
 		ObjectConnector(final PathObject pathObject) {
@@ -151,6 +192,12 @@ public class DefaultPathObjectConnectionGroup implements PathObjectConnectionGro
 			return connections;
 		}
 		
+		public List<PathObject> getConnectionsUnmodifiable() {
+			if (connectionsUnmodifiable == null)
+				connectionsUnmodifiable = Collections.unmodifiableList(connections);
+			return connectionsUnmodifiable;
+		}
+		
 		public void sortConnectionsByDistance() {
 			Collections.sort(connections, (o1, o2) -> Double.compare(
 					centroidDistanceSquared(pathObject, o1),
diff --git a/qupath-core/src/main/java/qupath/lib/objects/PathObjectConnectionGroup.java b/qupath-core/src/main/java/qupath/lib/objects/PathObjectConnectionGroup.java
index 2b58f623..488fa046 100644
--- a/qupath-core/src/main/java/qupath/lib/objects/PathObjectConnectionGroup.java
+++ b/qupath-core/src/main/java/qupath/lib/objects/PathObjectConnectionGroup.java
@@ -25,6 +25,9 @@ package qupath.lib.objects;
 
 import java.util.Collection;
 import java.util.List;
+import java.util.stream.Collectors;
+
+import qupath.lib.regions.ImageRegion;
 
 /**
  * Interface defining a basic structure to represent relationships between PathObjects that do not fit with  
@@ -63,5 +66,20 @@ public interface PathObjectConnectionGroup {
 	 * @return
 	 */
 	public List<PathObject> getConnectedObjects(final PathObject pathObject);
+	
+	
+	/**
+	 * Get all the objects with connections that <i>may</i> intersect the specified region.
+	 * @param region
+	 * @return 
+	 * @implNote the default implementation simply checks the z and t values of the region, and ensures they 
+	 *           match with the ROI of an object being returned. Subclasses should provide more optimized implementations.
+	 */
+	public default Collection<PathObject> getPathObjectsForRegion(ImageRegion region) {
+		return getPathObjects()
+				.stream()
+				.filter(p -> p.getROI().getZ() == region.getZ() && p.getROI().getT() == region.getT())
+				.collect(Collectors.toList());
+	}
 
 }
diff --git a/qupath-gui-fx/src/main/java/qupath/lib/gui/images/servers/PathHierarchyImageServer.java b/qupath-gui-fx/src/main/java/qupath/lib/gui/images/servers/PathHierarchyImageServer.java
index b1d53f3f..d198c5b6 100644
--- a/qupath-gui-fx/src/main/java/qupath/lib/gui/images/servers/PathHierarchyImageServer.java
+++ b/qupath-gui-fx/src/main/java/qupath/lib/gui/images/servers/PathHierarchyImageServer.java
@@ -237,7 +237,13 @@ public class PathHierarchyImageServer extends AbstractTileableImageServer implem
 		
 		// See if we have any connections to draw
 		if (connections != null) {
-			PathHierarchyPaintingHelper.paintConnections(connections, hierarchy, g2d, imageData.isFluorescence() ? ColorToolsAwt.TRANSLUCENT_WHITE : ColorToolsAwt.TRANSLUCENT_BLACK, downsampleFactor);
+			PathHierarchyPaintingHelper.paintConnections(
+					connections,
+					hierarchy,
+					g2d,
+					imageData.isFluorescence() ? ColorToolsAwt.TRANSLUCENT_WHITE : ColorToolsAwt.TRANSLUCENT_BLACK,
+					downsampleFactor,
+					tileRequest.getPlane());
 		}
 		
 		
diff --git a/qupath-gui-fx/src/main/java/qupath/lib/gui/viewer/PathHierarchyPaintingHelper.java b/qupath-gui-fx/src/main/java/qupath/lib/gui/viewer/PathHierarchyPaintingHelper.java
index 04d7c862..aae7d74a 100644
--- a/qupath-gui-fx/src/main/java/qupath/lib/gui/viewer/PathHierarchyPaintingHelper.java
+++ b/qupath-gui-fx/src/main/java/qupath/lib/gui/viewer/PathHierarchyPaintingHelper.java
@@ -43,8 +43,10 @@ import java.awt.geom.RectangularShape;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 import java.util.WeakHashMap;
 
 import org.slf4j.Logger;
@@ -73,6 +75,7 @@ import qupath.lib.objects.hierarchy.PathObjectHierarchy;
 import qupath.lib.objects.hierarchy.TMAGrid;
 import qupath.lib.objects.hierarchy.events.PathObjectSelectionModel;
 import qupath.lib.plugins.ParallelTileObject;
+import qupath.lib.regions.ImagePlane;
 import qupath.lib.regions.ImageRegion;
 import qupath.lib.roi.EllipseROI;
 import qupath.lib.roi.LineROI;
@@ -842,15 +845,16 @@ public class PathHierarchyPaintingHelper {
 		 * @param g2d
 		 * @param color
 		 * @param downsampleFactor
+		 * @param plane
 		 */
-		public static void paintConnections(final PathObjectConnections connections, final PathObjectHierarchy hierarchy, Graphics2D g2d, final Color color, final double downsampleFactor) {
+		public static void paintConnections(final PathObjectConnections connections, final PathObjectHierarchy hierarchy, Graphics2D g2d, final Color color, final double downsampleFactor, final ImagePlane plane) {
 			if (hierarchy == null || connections == null || connections.isEmpty())
 				return;
 
 			float alpha = (float)(1f - downsampleFactor / 5);
-			alpha = Math.min(alpha, 0.25f);
+			alpha = Math.min(alpha, 0.4f);
 			float thickness = PathPrefs.detectionStrokeThicknessProperty().get();
-			if (alpha < .1f || thickness / downsampleFactor <= 0.5)
+			if (alpha < .1f || thickness / downsampleFactor <= 0.25)
 				return;
 
 			g2d = (Graphics2D)g2d.create();
@@ -861,81 +865,61 @@ public class PathHierarchyPaintingHelper {
 			//		g2d.setColor(ColorToolsAwt.getColorWithOpacity(getPreferredOverlayColor(), 1));
 
 			g2d.setColor(ColorToolsAwt.getColorWithOpacity(color.getRGB(), alpha));
-//			g2d.setColor(Color.BLACK);
-			Line2D line = new Line2D.Double();
 			
-			// We can have trouble whenever two objects are outside the clip, but their connections would be inside it
-			// Here, we just enlarge the region (by quite a lot)
-			// It's not guaranteed to work, but it usually does... and avoids much expensive computations
+			// We only need to draw connections that intersect with the bounds
 			Rectangle bounds = g2d.getClipBounds();
-			int factor = 1;
-			Rectangle bounds2 = factor > 0 ? new Rectangle(bounds.x-bounds.width*factor, bounds.y-bounds.height*factor, bounds.width*(factor*2+1), bounds.height*(factor*2+1)) : bounds;
-			ImageRegion imageRegion = AwtTools.getImageRegion(bounds2, 0, 0);
-//			ImageRegion imageRegion = AwtTools.getImageRegion(bounds, 0, 0);
 
 			g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_OFF);
 			g2d.setRenderingHint(RenderingHints.KEY_RENDERING, RenderingHints.VALUE_RENDER_SPEED);
-
-//			g2d.draw(g2d.getClipBounds());
 			
-			Collection<PathObject> pathObjects = hierarchy.getObjectsForRegion(PathDetectionObject.class, imageRegion, null);
-//			Collection<PathObject> pathObjects = hierarchy.getObjects(null, PathDetectionObject.class);
-			//		double threshold = downsampleFactor*downsampleFactor*4;
-				for (PathObject pathObject : pathObjects) {
+			
+			// We need all the detections since *potentially* both ends might be outside the visible bounds, 
+			// but their connecting line intersects the bounds.
+			// However, this can be a *major* performance issue (until a spatial cache is used), so instead we expand the bounds 
+			// and hope that's enough to get all the objects we need.
+			ImageRegion imageRegion = AwtTools.getImageRegion(bounds, plane.getZ(), plane.getT());
+			
+			// Keep reference to visited objects, to avoid painting the same line twice
+			// (which happened in v0.3.2 and earlier)
+			Set<PathObject> vistedObjects = new HashSet<>();
+
+			// Reuse the line and record counts
+			Line2D line = new Line2D.Double();
+			int nDrawn = 0;
+			int nSkipped = 0;
+
+			long startTime = System.currentTimeMillis();
+			for (PathObjectConnectionGroup dt : connections.getConnectionGroups()) {
+				vistedObjects.clear();
+				for (var pathObject : dt.getPathObjectsForRegion(imageRegion)) {
+					
+					vistedObjects.add(pathObject);
 					ROI roi = PathObjectTools.getROI(pathObject, true);
 					double x1 = roi.getCentroidX();
 					double y1 = roi.getCentroidY();
-					for (PathObjectConnectionGroup dt : connections.getConnectionGroups()) {
 					for (PathObject siblingObject : dt.getConnectedObjects(pathObject)) {
+						if (vistedObjects.contains(siblingObject))
+							continue;
 						ROI roi2 = PathObjectTools.getROI(siblingObject, true);
 						double x2 = roi2.getCentroidX();
 						double y2 = roi2.getCentroidY();
 						if (bounds.intersectsLine(x1, y1, x2, y2)) {
 							line.setLine(x1, y1, x2, y2);
 							g2d.draw(line);
+							// Doesn't seem to be more efficient
+							// g2d.drawLine((int)x1, (int)y1, (int)x2, (int)y2);
+							nDrawn++;
+						} else {
+							nSkipped++;
 						}
 					}
+
 				}
 			}
-
+			long endTime = System.currentTimeMillis();
+			logger.trace("Drawn {} connections in {} ms ({} skipped)", nDrawn, endTime - startTime, nSkipped);
 			g2d.dispose();
 		}
 
 	
-//	@Override
-//	public void draw(Graphics g, Color colorStroke, Color colorFill) {
-//		if (colorStroke == null && colorFill == null)
-//			return;
-//		
-//		// Complex shapes can be very slow to draw - if we require a highly downsampled version,
-//		// then first cache a simplified version and draw that instead
-//		Graphics2D g2d = (Graphics2D)g.create();
-//		// Determine the scale (squared - no need to compute square root)
-//		AffineTransform transform = g2d.getTransform();
-//		double scaleSquared = transform.getScaleX()*transform.getScaleX() + transform.getShearX()*transform.getShearX();
-//		if (scaleSquared > 0.1*0.1) {
-//			super.draw(g, colorStroke, colorFill);
-//			return;
-//		}
-//		
-////		shapeSimplified = null;
-//		if (shapeSimplified == null) {
-//			shapeSimplified = ShapeSimplifier.simplifyPath(shape, 25);
-//		}
-//		if (colorFill != null) {
-//			g2d.setColor(colorFill);
-//			g2d.fill(shapeSimplified); 
-//		}
-//		if (colorStroke != null) {
-//			g2d.setColor(colorStroke);
-//			g2d.draw(shapeSimplified);
-//		}
-//		g2d.dispose();
-//	}
-	
-	
-//	public void draw(Graphics g, Color colorStroke, Color colorFill);
-	
-		
-	
 }
diff --git a/qupath-gui-fx/src/main/java/qupath/lib/gui/viewer/overlays/HierarchyOverlay.java b/qupath-gui-fx/src/main/java/qupath/lib/gui/viewer/overlays/HierarchyOverlay.java
index 5af5ec1a..d8807d5e 100644
--- a/qupath-gui-fx/src/main/java/qupath/lib/gui/viewer/overlays/HierarchyOverlay.java
+++ b/qupath-gui-fx/src/main/java/qupath/lib/gui/viewer/overlays/HierarchyOverlay.java
@@ -201,7 +201,12 @@ public class HierarchyOverlay extends AbstractOverlay {
 				if (overlayOptions.getShowConnections()) {
 					Object connections = imageData.getProperty(DefaultPathObjectConnectionGroup.KEY_OBJECT_CONNECTIONS);
 					if (connections instanceof PathObjectConnections)
-							PathHierarchyPaintingHelper.paintConnections((PathObjectConnections)connections, hierarchy, g2d, imageData.isFluorescence() ? ColorToolsAwt.TRANSLUCENT_WHITE : ColorToolsAwt.TRANSLUCENT_BLACK, downsampleFactor);
+							PathHierarchyPaintingHelper.paintConnections((PathObjectConnections)connections,
+									hierarchy,
+									g2d,
+									imageData.isFluorescence() ? ColorToolsAwt.TRANSLUCENT_WHITE : ColorToolsAwt.TRANSLUCENT_BLACK,
+											downsampleFactor,
+											imageRegion.getPlane());
 				}
 				
 			} else {					
['qupath-core/src/main/java/qupath/lib/objects/DefaultPathObjectConnectionGroup.java', 'qupath-core/src/main/java/qupath/lib/objects/PathObjectConnectionGroup.java', 'CHANGELOG.md', 'qupath-gui-fx/src/main/java/qupath/lib/gui/viewer/PathHierarchyPaintingHelper.java', 'qupath-gui-fx/src/main/java/qupath/lib/gui/images/servers/PathHierarchyImageServer.java', 'qupath-gui-fx/src/main/java/qupath/lib/gui/viewer/overlays/HierarchyOverlay.java']