Data QA: Identifying Non-Consecutive Duplicate Vertices

Introduction

A duplicate vertex (duplicate point) occurs when a geometry has one or more vertices that occur multiple times within the feature. Duplicate vertices are those with identical X, Y, and Z coordinates, to the same number of decimal places as in the data.

Duplicate vertices are not only a sign of lower-quality data but can also be a data format problem. Some formats permit duplicate vertices (for example, MicroStation DGN allows zero-length lines), while others prohibit them (for example, Oracle Spatial).

The duplicate vertex might occur sequentially in the geometry (for example, A, B, C, C, D, E) or out of sequence (A, B, C, D, C, E). It might be duplicated once (A, B, C, C, D), or duplicated multiple times (A, B, C, C, C, D, C, E, C).

Sometimes a duplicate vertex is valid. For example, the start and end points of a polygon should be identical if it is to close properly (A, B, C, D, E, A). Sometimes a linear feature loops around and rejoins at a midpoint (A, B, C, D, E, C). So it is not always easy to identify invalid features on this basis alone.

Several FME transformers can identify duplicate vertices, though some transformers — or combinations of transformers — are much more efficient than others. 

• GeometryValidator: identifies and fixes duplicate vertices that occur consecutively within a single geometry.
• ClosedCurveFilter: identifies features that form a closed loop, and can therefore be used to detect (or eliminate from suspicion) features with duplicate end points.
• CoordinateExtractor: extracts a list of coordinates from a feature, which can then be analyzed to look for duplicates.

In general, GeometryValidator is used more often because consecutive duplicate vertices are a more obvious issue.

However, CoordinateExtractor is better at detecting out-of-sequence duplicate vertices, enabling further investigation.

This example uses a combination of ClosedCurveFilter and CoordinateExtractor to identify unsequenced duplicate points. Another example uses the GeometryValidator transformer to identify duplicate points in sequence.

In this scenario, the data will be validated, issues will be recorded and isolated before it is passed for further production use.

The source data is a MicroStation Design file, buildings.dgn, containing line features that represent building footprints.

Step-by-Step Instructions

Locating non-consecutive duplicate vertices is not as straightforward as consecutive duplicates. However, it can be done. Follow these steps to discover one method to locate non-consecutive duplicate vertices.

Part 1: Isolating Open (Not Closed) Lines

This part adds the source data and uses the ClosedCurveFilter transformer to isolate features that do not form a closed loop, which may indicate a duplicate vertex problem.

1. Add Source Data

Open FME Workbench and begin with an empty canvas. On the toolbar, click Add Reader. In the Add Reader dialog, set the following:

• Format: Bentley MicroStation Design (V8)
• Dataset: buildings.dgn
• Parameters:
  • Advanced:
    • Remove Duplicate Points: Disabled

Ensure this parameter is turned off. As part of the data QA process, the goal is to identify where and how many duplicate vertices exist.

Click OK to add the reader. If prompted, select the BuildingFootprints level as the data to read.

2. Inspect the Data

Click the BuildingFootprints reader feature type on the canvas to open the mini toolbar. Click View Source Data to view the data in Data Preview. Examine the data. The data looks correct at a glance, and it is difficult to identify any duplicate vertices.

3. Add a ClosedCurveFilter Transformer

On the toolbar, click Add Transformer. In the Add Transformer dialog, search for ClosedCurveFilter and click OK to add it to the canvas. Connect the BuildingFootprints MicroStation V8 reader to the ClosedCurveFilter transformer. Run the workspace.

4. Inspect the Data

Click the ClosedCurveFilter transformer on the canvas to open the mini toolbar. Click the green Inspect Data Cache button. The Graphics Inspect window automatically highlights the open feature. Color the ClosedCurveFilter_Open feature and change the drawing order in the Display Control window to differentiate the results. It identifies an open feature like this:

This feature has a duplicate vertex, but it does not close as a polygon would. It may or may not be considered a problem feature, but since this is meant to be a building, it can probably be assumed to be incorrect.

Part 2: Exposing Non-Consecutive Duplicate Vertices

It is important not to confuse points on different features, and not to include the start or end point of polygons. Because the data lacks a unique ID for each feature, create one using a Counter transformer. This ensures identical points on different features are not confused.

1. Add a Counter Transformer

On the toolbar, click Add Transformer. In the Add Transformer dialog, search for Counter and click OK to add it to the canvas. Connect the Counter transformer to the ClosedCurveFilter Closed port. Open the transformer parameters and confirm the default settings match the following:

• General:
  • Count Start: 0
• Output Attribute Names:
  • Count: _count

2. Add a CoordinateExtractor Transformer

On the toolbar, click Add Transformer. In the Add Transformer dialog, search for CoordinateExtractor and click OK to add it to the canvas. Connect the Counter transformer to the CoordinateExtractor transformer. Open the transformer parameters and confirm the default settings match the following:

• Mode:
  • Mode: All Coordinates
• All Coordinates:
  • Coordinates List Name: _indices

Optionally, run the workspace and inspect the output features. The features in the record information window now have a list called _indices containing the vertex coordinates.

3. Add a ListExploder Transformer

It is not possible to analyze the coordinates list as a list object. There is no list transformer that finds duplicate values among multiple or paired values — for example, the ListDuplicateRemover transformer finds duplicate X values or duplicate Y values, but not a combination of duplicate X and Y. To expose the coordinates, use the ListExploder transformer to explode the list into one feature per list element.

On the toolbar, click Add Transformer. In the Add Transformer dialog, search for ListExploder and click OK to add it to the canvas. Connect the CoordinateExtractor transformer to the ListExploder transformer. Open the transformer parameters and set the following:

• General:
  • List Attribute: _indices{}

Leave the remaining parameters as default.

Optionally, run the workspace and inspect the output from the ListExploder transformer. There is now one feature per vertex. Each vertex has its position in the list recorded as _element_index, and the parent feature polygon is recorded as _count:

The above shows that building 0 has 5 vertices, numbered 0 to 4. The first and last vertices match, meaning it is a closed polygon.

Duplicate vertices at the beginning and end of a feature are the start and end nodes. This is required for closed polygons and lines, and should not be considered as part of this data QA check.

Part 3: Isolating Non-Consecutive Duplicate Vertices

Now remove vertices that are not, or do not count as, duplicates.

1. Removing Non-Duplicate Vertices

To remove the intentional start and end duplicate vertices, drop the first vertex in each element. On the toolbar, click Add Transformer. In the Add Transformer dialog, search for Tester and click OK to add it to the canvas. Connect the ListExploder transformer to the Tester transformer. Set the parameters as follows:

• Test Clauses:
  • Left Value: _element_index
  • Operator: =
  • Right Value: 0

This transformer passes all remaining vertices into the Failed output for further processing.

2. Add a DuplicateFilter Transformer

On the toolbar, click Add Transformer. In the Add Transformer dialog, search for DuplicateFilter and click OK to add it to the canvas. Connect the Failed port of the Tester transformer to the DuplicateFilter transformer. Set the parameters as follows:

• General:
  • Key Attributes: _count x y z

3. Inspect the Data

Run the workspace. Click the DuplicateFilter transformer on the canvas to open the mini toolbar. Click the green inspect data cache button on the Duplicate output. The result looks like this:

There is one unclosed feature and six features flagged with duplicate vertices. There is a feature for every duplicate vertex on a building, so if a building has two duplicate vertices, there will be two features to represent it. The x, y, and z attributes of the feature identify where the duplicate vertex lies.

Part 4: Counting Non-Consecutive Duplicate Vertices

Counting the number of invalid features and bad points is easy because they have already been filtered out. The StatisticsCalculator transformer can be used to generate data QA insights as an attribute, such as counts of duplicate values.

1. Add a StatisticsCalculator Transformer

On the toolbar, click Add Transformer. In the Add Transformer dialog, search for StatisticsCalculator and click OK to add it to the canvas. Connect the DuplicateFilter Duplicate output to the StatisticsCalculator transformer. Open the transformer parameters and set the following:

• Statistics to Calculate:
  • Attribute: Any Attribute (e.g. _count)
  • Total Count: Enabled

2. Re-run the Workspace

Run the workspace again. This time, the output includes an attribute indicating how many bad features there are for each type. To change the name of the output attribute from StatisticsCalculator, use the AttributeRenamer transformer.

Troubleshooting

Dropping the first vertex in each element does not introduce a problem. If the sequence is A, A, B, C, D, E, the two A's are consecutive, and could be found with the GeometryValidator transformer. If it is a closed line, E is the same as A, so any subsequent A also matches E. If it is not a closed line, the ClosedCurveFilter transformer already flags this as a possible problem feature.

Fixing problem vertices using this method can have some potential issues. It is technically possible to use the VertexRemover transformer to drop one of the bad vertices, but there is no guarantee the correct vertex is removed. For example, add a VertexRemover transformer after the DuplicateFilter transformer, and set the parameters as follows:

• General:
  • Coordinate Index: _element_index (which is known to be a duplicate)

The result works for some features, but not others:

Because of this, use this technique to identify non-consecutive duplicate coordinates, but not to fix them. Send problem features to another editing tool for fixing.

Additional Resources

Data QA: Identifying Consecutive Duplicate Vertices [Article]

Data QA: Identifying Duplicate Features [Article]

Data Attribution

The data used here originates from open data made available by the City of Vancouver, British Columbia. It contains information licensed under the Open Government License - Vancouver.