I created a static utility class for generating accurate Shape instances for a given String and Graphics2D rendering surface which will efficiently calculate intersection detection without the error associated with only using bounding boxes.
/**
* Provides methods for generating accurate shapes describing the area a particular {@link String} will occupy when
* drawn alongside methods which can calculate the intersection of those shapes efficiently and accurately.
*
* @author Emily Mabrey (emabrey@users.noreply.github.com)
*/
public class TextShapeIntersectionCalculator {
/**
* An {@link AffineTransform} which returns the given {@link Area} unchanged.
*/
private static final AffineTransform NEW_AREA_COPY = new AffineTransform();
/**
* Calculates the delta between two single coordinate values.
*
* @param coordinateA
* The origination coordinate which we are calculating from
* @param coordinateB
* The destination coordinate which the delta takes us to
* @return A coordinate value delta which expresses the change from A to B
*/
private static int getCoordinateDelta(final int coordinateA, final int coordinateB) {
return coordinateB - coordinateA;
}
/**
* Calls {@link #getTextShape(TextLayout)} using a {@link TextLayout} generated from the provided objects and
* returns the generated {@link Shape}.
*
* @param graphicsContext
* A non-null {@link Graphics2D} object with the configuration of the desired drawing surface
* @param string
* An {@link AttributedString} containing the data describing which characters to draw alongside the
* {@link Attribute Attributes} describing how those characters should be drawn.
* @return A {@link Shape} generated via {@link #getTextShape(TextLayout)}
*/
public static Shape getTextShape(final Graphics2D graphicsContext, final AttributedString string) {
final FontRenderContext fontContext = graphicsContext.getFontRenderContext();
final TextLayout textLayout = new TextLayout(string.getIterator(), fontContext);
return getTextShape(textLayout);
}
/**
* Calls {@link #getTextShape(TextLayout)} using a {@link TextLayout} generated from the provided objects and
* returns the generated {@link Shape}.
*
* @param graphicsContext
* A non-null {@link Graphics2D} object with the configuration of the desired drawing surface
* @param attributes
* A non-null {@link Map} object populated with {@link Attribute} objects which will be used to determine the
* glyphs and styles for rendering the character data
* @param string
* A {@link String} containing the character data which is to be drawn
* @return A {@link Shape} generated via {@link #getTextShape(TextLayout)}
*/
public static Shape getTextShape(final Graphics2D graphicsContext, final Map<? extends Attribute, ?> attributes,
final String string) {
final FontRenderContext fontContext = graphicsContext.getFontRenderContext();
final TextLayout textLayout = new TextLayout(string, attributes, fontContext);
return getTextShape(textLayout);
}
/**
* Calls {@link #getTextShape(TextLayout)} using a {@link TextLayout} generated from the provided objects and
* returns the generated {@link Shape}.
*
* @param graphicsContext
* A non-null {@link Graphics2D} object with the configuration of the desired drawing surface
* @param outputFont
* A non-null {@link Font} object used to determine the glyphs and styles for rendering the character data
* @param string
* A {@link String} containing the character data which is to be drawn
* @return A {@link Shape} generated via {@link #getTextShape(TextLayout)}
*/
public static Shape getTextShape(final Graphics2D graphicsContext, final Font outputFont, final String string) {
final FontRenderContext fontContext = graphicsContext.getFontRenderContext();
final TextLayout textLayout = new TextLayout(string, outputFont, fontContext);
return getTextShape(textLayout);
}
/**
* Determines the {@link Shape} which should be generated by rendering the given {@link TextLayout} object using the
* internal {@link Graphics2D} rendering state alongside the internal {@link String} and {@link Font}. The returned
* {@link Shape} is a potentially disjoint union of all the glyph shapes generated from the character data. Note that
* the states of the mutable contents of the {@link TextLayout}, such as {@link Graphics2D}, will not be modified.
*
* @param textLayout
* A {@link TextLayout} with an available {@link Graphics2D} object
* @return A {@link Shape} which is likely a series of disjoint polygons
*/
public static Shape getTextShape(final TextLayout textLayout) {
final int firstSequenceEndpoint = 0, secondSequenceEndpoint = textLayout.getCharacterCount();
final Shape generatedCollisionShape = textLayout.getBlackBoxBounds(firstSequenceEndpoint, secondSequenceEndpoint);
return generatedCollisionShape;
}
/**
* Converts the absolute coordinates of {@link Shape Shapes} a and b into relative coordinates and uses the converted
* coordinates to call and return the result of {@link #checkForIntersection(Shape, Shape, int, int)}.
*
* @param a
* A shape located with a user space location
* @param aX
* The x coordinate of {@link Shape} a
* @param aY
* The y coordinate of {@link Shape} a
* @param b
* A shape located with a user space location
* @param bX
* The x coordinate of {@link Shape} b
* @param bY
* The x coordinate of {@link Shape} b
* @return True if the two shapes at the given locations intersect, false if they do not intersect.
*/
public static boolean checkForIntersection(final Shape a, final int aX, final int aY, final Shape b, final int bX,
final int bY) {
return checkForIntersection(a, b, getCoordinateDelta(aX, bX), getCoordinateDelta(aY, bY));
}
/**
* Detects if two shapes with relative user space locations intersect. The intersection is checked in a way which
* fails quickly if there is no intersection and which succeeds using the least amount of calculation required to
* determine there is an intersection. The location of {@link Shape} a is considered to be the origin and the position
* of {@link Shape} b is defined relative to the position of {@link Shape} a using the provided coordinate deltas.
*
* @param a
* The shape placed at what is considered the origin
* @param b
* The shape placed in the position relative to a
* @param relativeDeltaX
* The delta x coordinate of {@link Shape} b compared to the x coordination of {@link Shape} a (which is always
* 0).
* @param relativeDeltaY
* The delta y coordinate of {@link Shape} b compared to the y coordination of {@link Shape} a (which is always
* 0).
* @return True to indicate the provided {@link Shape Shapes} intersect when placed in the indicated locations.
*/
public static boolean checkForIntersection(final Shape a, final Shape b, int relativeDeltaX, int relativeDeltaY) {
return isIntersectionUsingSimpleBounds(a, b, relativeDeltaX, relativeDeltaY)
&& isIntersectionUsingAdvancedBounds(a, b, relativeDeltaX, relativeDeltaY)
&& isIntersectionUsingExactAreas(a, b, relativeDeltaX, relativeDeltaY);
}
/**
* Detects if two shapes with relative user space locations intersect. The intersection is checked using a fast but
* extremely simplified bounding box calculation. The location of {@link Shape} a is considered to be the origin and
* the position of {@link Shape} b is defined relative to the position of {@link Shape} a using the provided
* coordinate deltas.
*
* @param a
* The shape placed at what is considered the origin
* @param b
* The shape placed in the position relative to a
* @param relativeDeltaX
* The delta x coordinate of {@link Shape} b compared to the x coordination of {@link Shape} a (which is always
* 0).
* @param relativeDeltaY
* The delta y coordinate of {@link Shape} b compared to the y coordination of {@link Shape} a (which is always
* 0).
* @return True to indicate the provided {@link Shape Shapes} intersect when placed in the indicated locations.
*/
private static boolean isIntersectionUsingSimpleBounds(final Shape a, final Shape b, int relativeDeltaX,
int relativeDeltaY) {
final Rectangle rectA = a.getBounds();
final Rectangle rectB = b.getBounds();
rectB.setLocation(rectA.getLocation());
rectB.translate(relativeDeltaX, relativeDeltaY);
return rectA.contains(rectB);
}
/**
* Detects if two shapes with relative user space locations intersect. The intersection is checked using a slightly
* simplified bounding box calculation. The location of {@link Shape} a is considered to be the origin and the
* position of {@link Shape} b is defined relative to the position of {@link Shape} a using the provided coordinate
* deltas.
*
* @param a
* The shape placed at what is considered the origin
* @param b
* The shape placed in the position relative to a
* @param relativeDeltaX
* The delta x coordinate of {@link Shape} b compared to the x coordination of {@link Shape} a (which is always
* 0).
* @param relativeDeltaY
* The delta y coordinate of {@link Shape} b compared to the y coordination of {@link Shape} a (which is always
* 0).
* @return True to indicate the provided {@link Shape Shapes} intersect when placed in the indicated locations.
*/
private static boolean isIntersectionUsingAdvancedBounds(final Shape a, final Shape b, int relativeDeltaX,
int relativeDeltaY) {
final Rectangle2D rectA = a.getBounds();
final Rectangle2D rectB = b.getBounds();
rectB.setRect(rectA.getX() + relativeDeltaX, rectA.getY() + relativeDeltaY, rectB.getWidth(), rectB.getHeight());
return rectA.contains(rectB);
}
/**
* Detects if two shapes with relative user space locations intersect. The intersection is checked using a slow but
* perfectly accurate calculation. The location of {@link Shape} a is considered to be the origin and the position of
* {@link Shape} b is defined relative to the position of {@link Shape} a using the provided coordinate deltas.
*
* @param a
* The shape placed at what is considered the origin
* @param b
* The shape placed in the position relative to a
* @param relativeDeltaX
* The delta x coordinate of {@link Shape} b compared to the x coordination of {@link Shape} a (which is always
* 0).
* @param relativeDeltaY
* The delta y coordinate of {@link Shape} b compared to the y coordination of {@link Shape} a (which is always
* 0).
* @return True to indicate the provided {@link Shape Shapes} intersect when placed in the indicated locations.
*/
private static boolean isIntersectionUsingExactAreas(final Shape a, final Shape b, int relativeDeltaX,
int relativeDeltaY) {
final Area aClone = new Area(a).createTransformedArea(NEW_AREA_COPY);
final Area bClone = new Area(b).createTransformedArea(NEW_AREA_COPY);
bClone.transform(AffineTransform.getTranslateInstance(relativeDeltaX, relativeDeltaY));
aClone.intersect(bClone);
return !aClone.isEmpty();
}
}
Using this class you should be able to draw a String anywhere an actual character glyph isn't, even if the place you want to draw is inside a bounding box for another String.
I rewrote the code you gave me to use my new intersection detection, but while rewriting it I cleaned it up and added some new classes to improve it. These two classes are simply data structures and they are needed alongside my rewrite of your code:
class StringDrawInformation {
public StringDrawInformation(final String s, final Font f, final Color c, final int x, final int y) {
this.text = s;
this.font = f;
this.color = c;
this.x = x;
this.y = y;
}
public final String text;
public final Font font;
public final Color color;
public int x, y;
}
class DrawShape {
public DrawShape(final Shape s, final StringDrawInformation drawInfo) {
this.shape = s;
this.drawInfo = drawInfo;
}
public final Shape shape;
public StringDrawInformation drawInfo;
}
Using my three new classes I rewrote your code to look like this:
private static final Random random = new Random();
public static final List<StringDrawInformation> generateRandomDrawInformation(int newCount) {
ArrayList<StringDrawInformation> newInfos = new ArrayList<>();
for (int i = 0; newCount > i; i++) {
String s = "Popup!";
Font f = new Font("STENCIL", Font.BOLD, random.nextInt(100) + 10);
Color c = Color.WHITE;
int x = random.nextInt(800);
int y = random.nextInt(800);
newInfos.add(new StringDrawInformation(s, f, c, x, y));
}
return newInfos;
}
public static List<DrawShape> generateRenderablePopups(final List<StringDrawInformation> in, Graphics2D g2d) {
List<DrawShape> outShapes = new ArrayList<>();
for (StringDrawInformation currentInfo : in) {
Shape currentShape = TextShapeIntersectionCalculator.getTextShape(g2d, currentInfo.font, currentInfo.text);
boolean placeIntoOut = true;
for (DrawShape nextOutShape : outShapes) {
if (TextShapeIntersectionCalculator.checkForIntersection(nextOutShape.shape, nextOutShape.drawInfo.x,
nextOutShape.drawInfo.y, currentShape, currentInfo.x, currentInfo.y)) {
// we found an intersection so we dont place into out and we stop verifying
placeIntoOut = false;
break;
}
}
if (placeIntoOut) {
outShapes.add(new DrawShape(currentShape, currentInfo));
}
}
return outShapes;
}
private List<StringDrawInformation> popups = generateRandomDrawInformation(20);
public void paintComponent(Graphics g) {
super.paintComponent(g);
Graphics2D g2d = (Graphics2D) g;
g2d.setBackground(Color.BLACK);
for (DrawShape renderablePopup : generateRenderablePopups(popups, g2d)) {
g2d.setColor(renderablePopup.drawInfo.color);
g2d.setFont(renderablePopup.drawInfo.font);
g2d.drawString(renderablePopup.drawInfo.text, renderablePopup.drawInfo.x, renderablePopup.drawInfo.y);
}
}
The rewritten code is easily modified to use more shapes, different fonts, different colors, etc. instead of being extremely hard to modify. I wrapped the different data into super-types which encapsulated the smaller data types to make them easier to use. My rewrite is no means perfect, but hopefully this helps.
I haven't actually tested this code yet, just wrote it by hand. So hopefully it works as intended. I will get around to testing it eventually, it was hard enough to find time to write what I already accomplished. If you have any question feel free to ask them. Sorry it took me so long to make my answer!
Edit: a small afterthought - the order of the StringDrawInformation List passed to generateRenderabePopups(...) is in order of priority. Each list element is compared against all currently validated elements. The first unchecked element always validates successfully, because there are no comparisons. The 2nd unchecked element is checked against the 1st because the 1st was validated. The 3rd unchecked may be checked against up to 2 other elements, the 4th up to 3. Basically, an element in position i might be checked against i-1 other elements. So, if it matters, put the more important text earlier in the list and the least important text later in the list.
