Unexpected output from FontGlyphReader for truetype fonts

[therealryan]

This test illustrates the issue:

import static org.junit.jupiter.api.Assertions.assertEquals;

import java.awt.Font;
import java.awt.FontFormatException;
import java.io.IOException;
import java.io.InputStream;
import java.net.URI;
import java.net.URISyntaxException;

import org.junit.jupiter.api.Test;
import org.locationtech.jts.awt.FontGlyphReader;
import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.geom.GeometryFactory;
import org.locationtech.jts.geom.MultiPolygon;
import org.locationtech.jts.geom.Polygon;

/**
 * Illustrating unexpected output from {@link FontGlyphReader}
 */
@SuppressWarnings("static-method")
class FontGlyphReaderTest {

    private static final GeometryFactory GF = new GeometryFactory();
    private static final Font SERIF = Font.decode( FontGlyphReader.FONT_SERIF );
    private static final Font KRYPTON;
    static {
        try( InputStream is = new URI(
                "https://github.com/githubnext/monaspace/raw/main/fonts/otf/MonaspaceKrypton-Regular.otf" )
                        .toURL().openStream() ) {
            KRYPTON = Font.createFont( Font.TRUETYPE_FONT, is );
        }
        catch( FontFormatException | IOException | URISyntaxException e ) {
            throw new IllegalStateException( e );
        }
    }

    /**
     * For simple characters (completely connected, no holes), both fonts produce
     * {@link Polygon} geometry with no interior rings, as we'd expect.
     */
    @Test
    void simple() {
        assertEquals( "Polygon with 0 interior rings",
                details( FontGlyphReader.read( "z", SERIF, GF ) ) );
        assertEquals( "Polygon with 0 interior rings",
                details( FontGlyphReader.read( "z", KRYPTON, GF ) ) );
    }

    /**
     * For characters with two disconnected elements the built-in font produces the
     * multipolygon you'd expect, while the truetype font produces a single polygon
     * with a hole
     */
    @Test
    void disconnected() {
        assertEquals( "MultiPolygon with 2 constituents",
                details( FontGlyphReader.read( "=", SERIF, GF ) ) );
        assertEquals( "Polygon with 1 interior rings",
                details( FontGlyphReader.read( "=", KRYPTON, GF ) ) );
    }

    /**
     * For characters with holes the truetype font now swings the <i>other</i> way
     */
    @Test
    void holes() {
        assertEquals( "Polygon with 1 interior rings",
                details( FontGlyphReader.read( "o", SERIF, GF ) ) );
        assertEquals( "MultiPolygon with 2 constituents",
                details( FontGlyphReader.read( "o", KRYPTON, GF ) ) );
    }

    private static String details( Geometry g ) {
        StringBuilder sb = new StringBuilder();
        sb.append( g.getClass().getSimpleName() );
        if( g instanceof Polygon p ) {
            sb.append( " with " ).append( p.getNumInteriorRing() ).append( " interior rings" );
        }
        else if( g instanceof MultiPolygon mp ) {
            sb.append( " with " ).append( mp.getNumGeometries() ).append( " constituents" );
        }
        return sb.toString();
    }

}

I suspect that the winding order of the font is messing things up - drawing the geometries reveals that the vertices are in the opposite order in the truetype font when compared against the standard font. For this font the holes are at least specified in the opposite winding order to the shell, but this SA question suggests that there is no standard for the winding order of the vertices in a font, or even any assurance that the polygon shell is specified before the holes.

[therealryan]

I'm currently avoiding the effects of this issue by: edit: deleted something that didn't work - transforming multipolygons into polygons with holes and vice versa

[therealryan]

That workaround quickly proved to be touchingly naive - it failed on more complex glyphs like % (multiple elements, some with holes) and 0 (a polygon within a hole within a polygon).

As always, stepping away from the problem provoked the solution into revealing itself: stop using FontGlyphReader completely and implement a solution that assumes less about the font geometry. The approach is to:

1. Extract the line loops from the font
2. Build a tree structure of loops-that-contain-loops
3. Descend the tree building polygons (if the loops on level n of the tree represent polygon shells, then the direct children on level n+1 are their holes)
4. Combine those polygons into a multipolygon.

Extracting loops

char[] chars = { character };
GlyphVector gv = font.createGlyphVector( FRC, chars );
List<LinearRing> rings = new ArrayList<>();
for( int i = 0; i < gv.getNumGlyphs(); i++ ) {
    @SuppressWarnings("unchecked")
    List<Coordinate[]> loops = ShapeReader.toCoordinates(
            gv.getGlyphOutline( i ).getPathIterator(
                    AffineTransform.getScaleInstance( 1, -1 ),
                    font.getSize() / 400.0f ) );
    for( Coordinate[] loop : loops ) {
        // remove repeated vertices - they mess up triangulation
        CoordinateList cl = new CoordinateList( loop, false );
        rings.add( GEO_FACT.createLinearRing( cl.toCoordinateArray() ) );
    }
}
MultiPolygon geometry = EvenOddPolygonBuilder.build(
        GEO_FACT, rings.toArray( LinearRing[]::new ) );

Combining loops into polygons:

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;

import org.locationtech.jts.geom.GeometryFactory;
import org.locationtech.jts.geom.LinearRing;
import org.locationtech.jts.geom.MultiPolygon;
import org.locationtech.jts.geom.Polygon;

/**
 * Combines multiple non-intersecting {@link LinearRing}s into a
 * {@link MultiPolygon} where the interior is defined by the even-odd winding
 * rule
 */
public class EvenOddPolygonBuilder {

    /**
     * Applies the even-odd winding rule to a set of line loops
     *
     * @param geoFact utility methods
     * @param rings   A set of simple line loops with no mutual intersections
     * @return the geometry of applying the even-odd rule to the rings
     */
    public static MultiPolygon build( GeometryFactory geoFact, LinearRing... rings ) {
        for( int i = 0; i < rings.length; i++ ) {
            for( int j = i + 1; j < rings.length; j++ ) {
                if( rings[i].intersects( rings[j] ) ) {
                    throw new IllegalArgumentException( rings[i] + " intersects with " + rings[j] );
                }
            }
        }

        ContainmentNode root = new ContainmentNode( null );
        for( LinearRing ring : rings ) {
            root.add( geoFact.createPolygon( ring ) );
        }
        return geoFact.createMultiPolygon(
                root.buildPolygons( geoFact, false, new ArrayList<>() )
                        .toArray( Polygon[]::new ) );
    }

    private static class ContainmentNode {
        public Polygon area;
        public final Collection<ContainmentNode> contents = new ArrayList<>();

        ContainmentNode( Polygon area ) {
            this.area = area;
        }

        boolean add( Polygon candidate ) {
            if( area == null || area.contains( candidate ) ) {

                // does it belong to any of the children?
                for( ContainmentNode content : contents ) {
                    if( content.add( candidate ) ) {
                        return true;
                    }
                }

                // it's not contained by any of the children, so it must be ours
                ContainmentNode node = new ContainmentNode( candidate );

                // check if any of our current children _actually_ belong to our new child
                Iterator<ContainmentNode> children = contents.iterator();
                while( children.hasNext() ) {
                    ContainmentNode child = children.next();
                    if( node.area.contains( child.area ) ) {
                        children.remove();
                        node.contents.add( child );
                    }
                }

                contents.add( node );
                return true;
            }
            return false;
        }

        List<Polygon> buildPolygons( GeometryFactory geoFact, boolean isPolygon,
                List<Polygon> polygons ) {

            if( isPolygon ) {
                // this level of the tree represents polygons - our direct children are the
                // holes in our shell
                Polygon polygon = geoFact.createPolygon(
                        area.getExteriorRing(),
                        contents.stream()
                                .map( child -> child.area.getExteriorRing() )
                                .toArray( LinearRing[]::new ) );
                polygon.normalize();
                polygons.add( polygon );
            }

            // recurse to the next level, flipping the polygon/hole flag as we go
            for( ContainmentNode child : contents ) {
                child.buildPolygons( geoFact, !isPolygon, polygons );
            }

            return polygons;
        }
    }
}