GeometryValidator: incorrect result for polygon in left-handed CRS

[jechterhoff]

Hello,

The GeometryValidator produces incorrect results when checking the orientation of the exterior and interior boundaries of a surface whose coordinates are given in a left-handed CRS. I've added a small test program at the end of this message.

Apparently, the determination of whether a given ring is counter-clockwise or not using the JTS CGAlgorithms.isCCW(...) in GeometryValidator.java, method validatePatch(...), requires that the coordinates are given in a right-handed CRS.

The OGC CITE tests transform the coordinates of a ring to a right-handed CRS, if necessary. See https://github.com/opengeospatial/ets-gml32/blob/master/src/main/java/org/opengis/cite/iso19136/data/spatial/GeometryAssert.java and https://github.com/opengeospatial/geomatics-geotk/blob/master/src/main/java/org/opengis/cite/geomatics/GeodesyUtils.java (search for transformRingToRightHandedCS).

The big question is: How could/should the GeometryValidator be fixed? Or am I missing something?

I've tried a similar approach as CITE, relying solely on Apache SIS. That works, but it would introduce a dependency that may not be necessary. Can deegree realise the necessary transformation on its own?

If the answer is no, could we introduce a template method in GeometryValidator.java, which would be called before invoking the orientation check? Like:

Coordinate[] transCoords = transformRingToRightHandedCS(ring_coords,crs);
boolean isClockwise = !CGAlgorithms.isCCW(transCoords);
...
public Coordinate[] transformRingToRightHandedCS(Coordinate[] coords, ICRS crs) {+
// Default is to simply return the coordinates.
return coords;
}

Then a subclass of GeometryValidator could override the method and transform the coordiantes to a right-handed CRS, using - for example - Apache SIS.

Comments and suggestions are welcome.

Best regards,
Johannes

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.deegree.cs.coordinatesystems.ICRS;
import org.deegree.cs.persistence.CRSManager;
import org.deegree.geometry.Geometry;
import org.deegree.geometry.GeometryFactory;
import org.deegree.geometry.primitive.Ring;
import org.deegree.geometry.standard.points.PackedPoints;
import org.deegree.geometry.validation.GeometryValidationEventHandler;
import org.deegree.geometry.validation.GeometryValidator;
import org.deegree.geometry.validation.event.ExteriorRingOrientation;
import org.deegree.geometry.validation.event.GeometryValidationEvent;
import org.deegree.geometry.validation.event.InteriorRingOrientation;

/**
 * @author echterhoff
 *
 */
public class GeometryValidatorTest implements GeometryValidationEventHandler {

	private List<String> messages = new ArrayList<>();

	public static void main(String[] args) {

		GeometryFactory geomFactory = new GeometryFactory();

		/*
		 * Create a geometry with a left-handed CRS. Coordinates are given as
		 * pairs of lat/long values.
		 */
		ICRS crs = CRSManager.getCRSRef("urn:ogc:def:crs:epsg::4326");
		Ring exterior = geomFactory.createLinearRing("lr_ext", crs,
				new PackedPoints(crs, new double[] { 0, 2, 1, 1, 1, -1, 1, -2, -1, -2, 0, 2 }, 2));
		Ring interior = geomFactory.createLinearRing("lr_int", crs,
				new PackedPoints(crs, new double[] { 0, 1, -0.25, 0, 0, -1, 1, 0, 0, 1 }, 2));

		/*
		 * NOTE: Using 'epsg:4326' as CRS would result in the right-handed
		 * version of EPSG 4326, also called not axis aware on
		 * https://github.com/deegree/deegree3/wiki/Axis-order-handling. The
		 * coordinates of the following rings are given as pairs of long/lat
		 * values. The orientation of the boundaries of the resulting polygon
		 * would be valid.
		 */
		// ICRS crs = CRSManager.getCRSRef("EPSG:4326");
		// Ring exterior = geomFactory.createLinearRing("lr_ext", crs,
		// new PackedPoints(crs, new double[] { 2, 0, 1, 1, -1, 1, -2, 1, -2,
		// -1, 2, 0 }, 2));
		// Ring interior = geomFactory.createLinearRing("lr_int", crs,
		// new PackedPoints(crs, new double[] { 1, 0, 0, -0.25, -1, 0, 0, 1, 1,
		// 0 }, 2));

		Geometry geom = geomFactory.createPolygon("testgeometry", crs, exterior,
				new ArrayList<Ring>(Arrays.asList(interior)));

		GeometryValidatorTest eventHandler = new GeometryValidatorTest();

		GeometryValidator validator = new GeometryValidator(eventHandler);

		validator.validateGeometry(geom);

		if (eventHandler.messages.isEmpty()) {
			System.out.println("Orientation is valid.");
		} else {
			System.out.println("Orientation is invalid:");
			for (String msg : eventHandler.messages) {
				System.out.println(msg);
			}
		}
	}

	protected boolean exteriorRingOrientation(ExteriorRingOrientation evt) {
		if (evt.isClockwise()) {
			this.messages.add("Exterior ring is oriented clockwise.");
			return true;
		} else {
			return false;
		}
	}

	protected boolean interiorRingOrientation(InteriorRingOrientation evt) {
		if (evt.isClockwise()) {
			return false;
		} else {
			this.messages.add("Interior ring is oriented counterclockwise.");
			return true;
		}
	}

	@Override
	public boolean fireEvent(GeometryValidationEvent event) {
		if (event instanceof ExteriorRingOrientation) {
			return exteriorRingOrientation((ExteriorRingOrientation) event);
		} else if (event instanceof InteriorRingOrientation) {
			return interiorRingOrientation((InteriorRingOrientation) event);
		} else {
			return false;
		}
	}
}

[tfr42]

Affects https://github.com/deegree/deegree3/blob/master/deegree-core/deegree-core-geometry/src/main/java/org/deegree/geometry/validation/GeometryValidator.java

[jratike80]

Could you write the example geometry to use longitude values >90 for making it self-evident which numbers are latitudes and which ones longitudes?

[jechterhoff]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.deegree.cs.coordinatesystems.ICRS;
import org.deegree.cs.persistence.CRSManager;
import org.deegree.geometry.Geometry;
import org.deegree.geometry.GeometryFactory;
import org.deegree.geometry.primitive.Ring;
import org.deegree.geometry.standard.points.PackedPoints;
import org.deegree.geometry.validation.GeometryValidationEventHandler;
import org.deegree.geometry.validation.GeometryValidator;
import org.deegree.geometry.validation.event.ExteriorRingOrientation;
import org.deegree.geometry.validation.event.GeometryValidationEvent;
import org.deegree.geometry.validation.event.InteriorRingOrientation;

/**
 * @author echterhoff
 *
 */
public class GeometryValidatorTest implements GeometryValidationEventHandler {

	private List<String> messages = new ArrayList<>();

	public static void main(String[] args) {

		GeometryFactory geomFactory = new GeometryFactory();

		/*
		 * Create a geometry with a left-handed CRS. Coordinates are given as
		 * pairs of lat/long values.
		 */
		ICRS crs = CRSManager.getCRSRef("urn:ogc:def:crs:epsg::4326");
		Ring exterior = geomFactory.createLinearRing("lr_ext", crs,
				new PackedPoints(crs, new double[] { 0, 120, 10, 100, 10, -100,
						10, -120, -10, -120, 0, 120 }, 2));
		Ring interior = geomFactory.createLinearRing("lr_int", crs,
				new PackedPoints(crs,
						new double[] { 0, 100, -5, 0, 0, -100, 10, 0, 0, 100 },
						2));

		/*
		 * NOTE: Using 'epsg:4326' as CRS would result in the right-handed
		 * version of EPSG 4326, also called not axis aware on
		 * https://github.com/deegree/deegree3/wiki/Axis-order-handling. The
		 * coordinates of the following rings are given as pairs of long/lat
		 * values. The orientation of the boundaries of the resulting polygon
		 * would be valid.
		 */
		// ICRS crs = CRSManager.getCRSRef("EPSG:4326");
		// Ring exterior = geomFactory.createLinearRing("lr_ext", crs,
		// new PackedPoints(crs,
		// new double[] { 120, 0, 100, 10, -100, 10, -120, 10, -120, -10, 120, 0
		// },
		// 2));
		// Ring interior = geomFactory.createLinearRing("lr_int", crs,
		// new PackedPoints(crs,
		// new double[] { 100, 0, 0, -5, -100, 0, 0, 10, 100, 0 }, 2));

		Geometry geom = geomFactory.createPolygon("testgeometry", crs, exterior,
				new ArrayList<Ring>(Arrays.asList(interior)));

		GeometryValidatorTest eventHandler = new GeometryValidatorTest();

		GeometryValidator validator = new GeometryValidator(eventHandler);

		validator.validateGeometry(geom);

		if (eventHandler.messages.isEmpty()) {
			System.out.println("Orientation is valid.");
		} else {
			System.out.println("Orientation is invalid:");
			for (String msg : eventHandler.messages) {
				System.out.println(msg);
			}
		}
	}

	protected boolean exteriorRingOrientation(ExteriorRingOrientation evt) {
		if (evt.isClockwise()) {
			this.messages.add("Exterior ring is oriented clockwise.");
			return true;
		} else {
			return false;
		}
	}

	protected boolean interiorRingOrientation(InteriorRingOrientation evt) {
		if (evt.isClockwise()) {
			return false;
		} else {
			this.messages.add("Interior ring is oriented counterclockwise.");
			return true;
		}
	}

	@Override
	public boolean fireEvent(GeometryValidationEvent event) {
		if (event instanceof ExteriorRingOrientation) {
			return exteriorRingOrientation((ExteriorRingOrientation) event);
		} else if (event instanceof InteriorRingOrientation) {
			return interiorRingOrientation((InteriorRingOrientation) event);
		} else {
			return false;
		}
	}
}

[josemasensio]

Hi there,
has @jechterhoff solution been implemeted? we are having the same problem.
Regards
Juan

[MarcoMinghini]

Dear all,
this longstanding bug is creating a number of issues within the INSPIRE validation community (cc @michellutz, @cportele), see for example:

• Unexpected validation error on counterclockwise polygon inspire-eu-validation/ets-repository#60
• Issue with gmlas.d.10: Validate geometries (1) regarding outer ring orientation inspire-eu-validation/ets-repository#137
• https://github.com/etf-validator/etf-gmlgeox/issues/20
• Validate geometries inspire-eu-validation/ets-repository#147

Therefore, the INSPIRE Team at the JRC is interested and available to fix this issue. Before working on the fix and submitting a PR, we would like to know from the deegree PSC whether and how this could be integrated in the project roadmap and when we could expect a version including such a fix.
Thank you.

[tfr42]

@MarcoMinghini Any kind of contribution is welcome. Pull requests are the most wanted. So, the best approach to get this issue fixed is to prepare a pull request. Please make yourself familiar with the contribution guidelines at https://github.com/deegree/deegree3/blob/master/CONTRIB.md. Regarding the roadmap or future releases: next planned versions are 3.4.12 (can included bug fixes and enhancements which are semversion safe) and 3.5 (new features and enhancments which change API or configuration). To get things done we recommend to join one of the next TMC meetings. Check our chat log (last was 20191213) or mailing list for the announcements.

[carlospzurita]

To continue our discussion from the TMC meeting, and in order to get some feedback from you, we are going to share a quick outline of our approach in the solution of this issue.

Our main concern here is to maintain compatibility with existing client code. So our proposal is to add a new method on https://github.com/deegree/deegree3/blob/master/deegree-core/deegree-core-geometry/src/main/java/org/deegree/geometry/validation/event/InteriorRingOrientation.java

 public boolean hasLeftHandedSrs() {
    String crs = patch.getInteriorRings().get(ringIdx).getCoordinateSystem().getType().getOriginal();

    // Comparison to list of known left handed CRS
    boolean hasLeftHandedSrs =
        crs.equalsIgnoreCase( "epsg:?????" ) ||
        crs.equalsIgnoreCase( "etrs:?????" ) ||
        // ...
        crs.equalsIgnoreCase( "????:?????" );

    return hasLeftHandedSrs;
}

Using this method, and the already implemented isClockwise() , we can check on the client code the orientation. For example, a snippet for the INSPIRE validator could be

boolean exteriorRingOrientation( ExteriorRingOrientation evt ) {
    PolygonPatch patch = evt.getPatch();
    boolean isExterior = !evt.isClockwise();
   
    if(evt.hasLeftHandedSrs()) {
        isExterior = !isExterior;
    }

    if(!isExterior) {
        String errMessage = ValidatorMessageBundle.getMessage(
                "validator.core.validation.geometry.exteriorRingCW",
                this.currentGmlId,
                this.currentOnderdeelName,
                ValidationUtil.getAffectedCoordinates(patch.getExteriorRing(), 60));
        this.validatorContext.addError(errMessage);
    }

    return isExterior;
}

boolean interiorRingOrientation( InteriorRingOrientation evt ) {
    PolygonPatch patch = evt.getPatch();
    boolean isInterior = evt.isClockwise();

    if(evt.hasLeftHandedSrs()) {
        isInterior = !isInterior;
    }

    if(!isInterior) {
        int idx = evt.getRindIdx();
        String errMessage = ValidatorMessageBundle.getMessage(
                "validator.core.validation.geometry.interiorRingCCW",
                this.currentGmlId,
                this.currentOnderdeelName,
                ValidationUtil.getAffectedCoordinates(patch.getInteriorRings().get(idx), 60),
                idx);
        this.validatorContext.addError(errMessage);
    }

    return isInterior;
}

The list of known left handed CRS cand be specified on a static class, to have a cleaner code in the InteriorRingOrientation.java.

This is the change that we are proposing, trying to interfere the less with the code base and keeping it simple. Of course, any feedback is welcome and we will happy to make any change to this. Also, we can attend the next TMC meeting to discuss the solution.

[stempler]

Regarding the proposed hasLeftHandedSrs method: In hale we use the information on the axis order and direction to determine that. That might be preferable to maintaining a list of CRSes (if that information is available in deegree).

Here is the respective logic. This was implemented by a student some years ago, the naming is not ideal, but I hope you can get the idea from it:
https://github.com/halestudio/hale/blob/b651f8d2eabbc22d9af84034bf3fcfa45030d259/util/plugins/eu.esdihumboldt.util.geometry/src/eu/esdihumboldt/util/geometry/WindingOrder.java#L45

[copierrj]

The TMC discussed this in detail and we would like to make the following observation:

In order to calculate the orientation one needs an additional crs attribute (called by you: hasLeftHandedSrs). We would like to determine this attribute based on the exisiting deegree crs database (https://raw.githubusercontent.com/deegree/deegree3/master/deegree-core/deegree-core-cs/src/main/resources/org/deegree/cs/persistence/deegree/d3/config/crs-definitions.xml) instead of having a list of exceptions in code. If we understand correctly the hale project already has figured out how to do that. Would you be able to write a 'hasLeftHandedSrs' like the one found in hale for use in deegree? And test if this results in the correct behavior.

[carlospzurita]

Yes, we are modifying our approach to include the solution from hale, using the CRS database. We will offer feedback on the solution as soon as we test it.

[tfr42]

Closing since PR #1034 was already merged.

[jenriquesoriano]

Dear deegree community,

we have noticed an issue with the validation of the geometry's orientation results provided by deegree. This is the same issue to which we have contributed some years ago. deegree is reused by the open source ETF validation framework, which is in turn used by the INSPIRE Reference Validator and the latter is the source application where we spotted the issue.

Test results for geometry orientation using deegree and the OGC TEAM Engine are different for the same geometry and declared CRS.
After some investigation, it seems that this issue is related with the coordinates treatment, in particular the algorithm that decides if a CRS is left-handed or right-handed and how to deal with the coordinates.

For this CRS: http://www.opengis.net/def/crs/EPSG/0/3035, the obtained results are as follows:

We have tested it in our own application, but we have created this piece of code to help reproduce the issue (thanks to the source code in the initial comment.

import org.deegree.cs.coordinatesystems.ICRS;
import org.deegree.cs.persistence.CRSManager;
import org.deegree.geometry.Geometry;
import org.deegree.geometry.GeometryFactory;
import org.deegree.geometry.primitive.Ring;
import org.deegree.geometry.standard.points.PackedPoints;
import org.deegree.geometry.validation.GeometryValidationEventHandler;
import org.deegree.geometry.validation.GeometryValidator;
import org.deegree.geometry.validation.event.ExteriorRingOrientation;
import org.deegree.geometry.validation.event.GeometryValidationEvent;
import org.deegree.geometry.validation.event.InteriorRingOrientation;

import java.io.File;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class GeometryValidatorTest implements GeometryValidationEventHandler {

    private final List<String> messages = new ArrayList<>();

    public static void main(String[] args) {

        GeometryFactory geomFactory = new GeometryFactory();

        /*
         * Create a geometry with a left-handed CRS. Coordinates are given as
         * pairs of lat/long values.
         */
        CRSManager crsManager =new CRSManager();
        crsManager.init(new File("/home/manuelaromero/Inspire/IJ/untitled1/src/resources/srsconfig/"));

        ICRS crs = CRSManager.getCRSRef("http://www.opengis.net/def/crs/EPSG/0/3035");
        Ring exterior = geomFactory.createLinearRing("lr_ext", crs,
            //clockwise
            new PackedPoints(crs, new double[] { 2180200, 700120, 2180220, 700120, 2180220, 700100,
                2180200, 700100, 2180200, 700120 }, 2));
            //anti
            //new PackedPoints(crs, new double[] { 0, 120, 0, 100, 20, 100,
            //   20, 120, 0, 120 }, 2));
        Ring interior = geomFactory.createLinearRing("lr_int", crs,
            //anti
            new PackedPoints(crs,
                new double[] { 218005, 700105, 218010, 700105, 218010, 700110, 218005, 700110, 218005, 700105 },
                2));
        //clock
                //new double[] { 5, 105, 5, 110, 10, 110, 10, 105, 5, 105 },
                //2));

        /*
         * NOTE: Using 'epsg:4326' as CRS would result in the right-handed
         * version of EPSG 4326, also called not axis aware on
         * https://github.com/deegree/deegree3/wiki/Axis-order-handling. The
         * coordinates of the following rings are given as pairs of long/lat
         * values. The orientation of the boundaries of the resulting polygon
         * would be valid.
         */
        // ICRS crs = CRSManager.getCRSRef("EPSG:4326");
        // Ring exterior = geomFactory.createLinearRing("lr_ext", crs,
        // new PackedPoints(crs,
        // new double[] { 120, 0, 100, 10, -100, 10, -120, 10, -120, -10, 120, 0
        // },
        // 2));
        // Ring interior = geomFactory.createLinearRing("lr_int", crs,
        // new PackedPoints(crs,
        // new double[] { 100, 0, 0, -5, -100, 0, 0, 10, 100, 0 }, 2));

        Geometry geom = geomFactory.createPolygon("testgeometry", crs, exterior,
            new ArrayList<Ring>(Collections.singletonList(interior)));

        GeometryValidatorTest eventHandler = new GeometryValidatorTest();

        GeometryValidator validator = new GeometryValidator(eventHandler);

        validator.validateGeometry(geom);
        if (eventHandler.messages.isEmpty()) {
            System.out.println("Orientation is valid.");
        } else {
            System.out.println("Orientation is invalid:");
            for (String msg : eventHandler.messages) {
                System.out.println(msg);
            }
        }
    }

    protected boolean exteriorRingOrientation(ExteriorRingOrientation evt) {

        System.out.println(evt.isClockwise());
        if (evt.isExterior()) {
            this.messages.add("Exterior ring valid");
            return true;
        } else {
            this.messages.add("Exterior ring not valid");
            return false;
        }
    }

    protected boolean interiorRingOrientation(InteriorRingOrientation evt) {
        System.out.println(evt.isClockwise());

        if (evt.isInterior()) {
            this.messages.add("Interior ring valid");
            return false;
        } else {
            this.messages.add("Interior ring not valid");
            return true;
        }
    }

    @Override
    public boolean fireEvent(GeometryValidationEvent event) {
        if (event instanceof ExteriorRingOrientation) {
            return exteriorRingOrientation((ExteriorRingOrientation) event);
        } else if (event instanceof InteriorRingOrientation) {
            return interiorRingOrientation((InteriorRingOrientation) event);
        } else {
            return false;
        }
    }
}

We have investigated the issue and it seems to us that it is related to the ExteriorRingOrientation.java class or to how a CRS is considered right-handed or left-handed in the AbstractGeometryValidationEvent.java class.

In the ExteriorRingOrientation.java class the method that would be related to this matter would be is Exterior():

public boolean isExterior() {
        boolean isExterior = !isClockwise;

        if ( isLeftHanded( patch.getExteriorRing().getCoordinateSystem() ) ) {
            isExterior = !isExterior;
        }

        return isExterior;
    }

Or in the AbstractGeometryValidationEvent.java class the method would be isLeftHand():

protected boolean isLeftHanded( ICRS crs ) {
        // get number of dimensions (it should be 2)
        if ( crs.getDimension() == 2 ) {
            int axis1 = crs.getAxis()[0].getOrientation();
            int axis2 = crs.getAxis()[1].getOrientation();

            // check if CRS is left handed
            if ( axis1 == Axis.AO_EAST || axis1 == Axis.AO_WEST ) {
                if ( axis1 == Axis.AO_EAST && ( axis2 == Axis.AO_SOUTH || axis2 == Axis.AO_DOWN ) ) {
                    return true;
                }
                else if ( axis1 == Axis.AO_WEST && ( axis2 == Axis.AO_NORTH || axis2 == Axis.AO_UP ) ) {
                    return true;
                }
            }
            else {
                if ( ( axis1 == Axis.AO_SOUTH || axis1 == Axis.AO_DOWN ) && axis2 == Axis.AO_WEST ) {
                    return true;
                }
                else if ( ( axis1 == Axis.AO_NORTH || axis1 == Axis.AO_UP ) && axis2 == Axis.AO_EAST ) {
                    return true;
                }
            }
        }

        // return false in any other case
        return false;
    }

It may also be that the order of the axis in certain systems when reading them is not the same as the one described in the CRS, causing a different treatment of their coordinates than the one that should be used.

Thus, as the results provided by deegree are different for this left-handed CRSs compared with the OGC TEAM Engine, what would be the correct output so they would both be the same? @tfr42 @jechterhoff

Thanks for your attention.

Best,