CODEWITHSUNDEEP
c#wpfalgorithmlabeloverlap
John Petrak
John Petrak

Reputation: 2928

How to handle overlapping of dynamically placed labels

I am creating a visualizer in WPF to display flowfield information for a game I am writing and have come across a problem with some labels being very close to each other.

Flowfield Visualizer

In the above screen shot, sector (0,0) is the top left. In sector (1,1) I have highlighted two labels with arrows that are very close to each other. In sector (2,1) I have circled two labels that overlap completly. I need to be able to place labels in a way so that they do not overlap and have a margin of distance. I am after preferably a simple algorithm that allows me to place labels on a contended spot.

The blue/black cells are virtualized items on an Items Control with a canvas as the ItemsPanel. The red sector squares are on one adorner while the green lines, boxes, bezier curves and red cost labels are on a second adorner. Both adorners use the drawing context with everything dynamically created upon render.

var typeface = new Typeface(new FontFamily("Segoe UI"), FontStyles.Normal, FontWeights.Normal, FontStretches.Normal);
var formattedText = new FormattedText(curve.Cost.ToString(), CultureInfo.CurrentUICulture, FlowDirection.LeftToRight, typeface, 12, Brushes.Red, null, TextFormattingMode.Display);

var textLocation = new Point(midPoint2.X - (formattedText.WidthIncludingTrailingWhitespace / 2), midPoint2.Y - formattedText.Height);
drawingContext.DrawText(formattedText, textLocation);

Upvotes: 2

Views: 1353

Answers (2)

John Petrak
John Petrak

Reputation: 2928

After considering several ways to place labels includng Word Clouds, physics based approaches, voronoi diagrams. I decided to base my approach on An Empirical Study of Algorithms for Point-Feature Label Placement as I could see a simple and quick way to position labels. Page 2 gave me the idea of having four possible locations for a desired point and I built my own implementation with very simple rules.

I created a class called PointLabelPlacer with two methods AddLabel ComputeNewPositions

I would send all my labels along with the point to the AddLabel method. Once I was done and ready I would call ComputeNewPositions. This would for all four possible locations count the number of locations from another labels that have overlapped.

I would also flag a location if it overlapped an original point of another label.

If two labels overlapped exactly, i would again choose the first one without overlaps, but I would mark all the other labels location as used

Then I would just choose the first one I found with the lowest number of overlaps and did not overlap another point and was not marked as used.

If after all that no alternate location could be found, I default to the top left and allow overlaps.

This is with the alternate locations displayed in yellow Alternate locations displayed

This is the final result Final Result

Upvotes: 1

user1196549
user1196549

Reputation:

A suggestion:

The Voronoi diagram of a set of geometric entities is the partition of the plane into regions where points are closer to a given entity than to all others. enter image description here

If you construct the Voronoi diagram of your curves, and if you place the labels wholly in the corresponding regions, this solves your problem.

Assuming that all labels have the same extent (same bounding box), you can find suitable empty spaces by applying an erosion operation, i.e. removing layers of pixels on the region outlines for the desired width/height. The remaining pixels are possible centers for the labels.

In the general case, computing a Voronoi diagram by geometric means is extremely difficult. But if you work with a digital image, it suffices to draw the geometric entities and compute the distance map from them.

This requires that you be somewhat familiar with the techniques of digital image processing.

Upvotes: 4

Related Questions