Find duplicate vertices in an array?

EvanReese

Anyone have a good suggestion on finding duplicate vertices in an array? Id like to find them and be able to remove duplicates.

I was considering looping over the whole array, and comparing each item to a copy of the array with that item removed in a nested loop. Is that a decent direction or is there a simpler way?

xTimRice

I think you could use deduplicate()
https://cad.onshape.com/FsDoc/library.html#deduplicate-array

_anton

Easy (quadratic) algorithm is to make a result array, iterate over the input array, check if the current vertex is within a tolerance of any of the verts in the result array - if not, then append to the result array. Performance with modestly-sized input should be all right.

Alex_Kempen

deduplicate won't work for vertices, as deduplicate uses map key access (so ==) for comparison, not tolerantEquals. Practically speaking, == is probably okay, but there are edge cases like selecting a vertex in sketch A and a vertex in sketch B which has been coincidented to the vertex in sketch A where == will fail.

The best alternative to deduplicate is likely qUniqueVertices, although that requires you to have original queries. Otherwise, clusterPoints should do the trick. If you do use it, you'll probably want to pass `TOLERANCE.zeroLength * meter` as the tolerance, and note the output is of the following form:
Given an input `[vertex a, vertex b, vertex c, vertex a]`, clusterPoints will return `[[0, 3], [1], [2]]`. Hopefully it's clear how you can convert the given result back into a list of vertices.

EvanReese

Here's what I ended up going with. Thanks, Alex!

/**
 * Takes an array of vectors and returns it with duplicates removed.
 */
export function deduplicatePoints(points is array) returns array
{
    const pointClusters = clusterPoints(points, TOLERANCE.zeroLength * meter);

    var result = [];
    for (var pointCluster in pointClusters)
        result = append(result, points[pointCluster[0]]);
    return result;
}

xTimRice

I think you could use deduplicate()
https://cad.onshape.com/FsDoc/library.html#deduplicate-array

_anton

Easy (quadratic) algorithm is to make a result array, iterate over the input array, check if the current vertex is within a tolerance of any of the verts in the result array - if not, then append to the result array. Performance with modestly-sized input should be all right.

EvanReese

@TimRice
That's exactly what I'm looking for, and Anton, thanks for the rundown. That makes sense too. I was searching for it with autocomplete, but it wasn't there because deduplicate() isn't part of common.fs or geometry.fs. Thanks!

Alex_Kempen

deduplicate won't work for vertices, as deduplicate uses map key access (so ==) for comparison, not tolerantEquals. Practically speaking, == is probably okay, but there are edge cases like selecting a vertex in sketch A and a vertex in sketch B which has been coincidented to the vertex in sketch A where == will fail.

The best alternative to deduplicate is likely qUniqueVertices, although that requires you to have original queries. Otherwise, clusterPoints should do the trick. If you do use it, you'll probably want to pass `TOLERANCE.zeroLength * meter` as the tolerance, and note the output is of the following form:
Given an input `[vertex a, vertex b, vertex c, vertex a]`, clusterPoints will return `[[0, 3], [1], [2]]`. Hopefully it's clear how you can convert the given result back into a list of vertices.

_anton

> qUniqueVertices/clusterPoints

I totally didn't forget about these and just didn't want to steal your thunder. 

EvanReese

Here's what I ended up going with. Thanks, Alex!

/**
 * Takes an array of vectors and returns it with duplicates removed.
 */
export function deduplicatePoints(points is array) returns array
{
    const pointClusters = clusterPoints(points, TOLERANCE.zeroLength * meter);

    var result = [];
    for (var pointCluster in pointClusters)
        result = append(result, points[pointCluster[0]]);
    return result;
}