Add method to easy check equal polygons

[karolis-k]

Hi,

Here is unit test:

describe('arePolygonsSame', () => {
    it('test for infinite loop2', () => {
        const pf1 = new Flatten.Polygon([
            Flatten.point([128.38777744543145, 71.69121218006293]),
            Flatten.point([157.9999999995936, 71.69121218006293]),
            Flatten.point([157.9999999995936, 114.70291380862872]),
            Flatten.point([128.38777744543145, 114.70291380862872]),
        ]);
        const pf2 = new Flatten.Polygon([
            Flatten.point([128.38777744543145, 71.69121218006293]),
            Flatten.point([158, 71.69121218006293]),
            Flatten.point([158, 114.70291380767586]),
            Flatten.point([128.38777744543145, 114.70291380767586]),
        ]);
        expect(equal(pf1, pf2)).toBe(true);
    });
});

And error:

Chrome 111.0.0.0 (Windows 10) arePolygonsSame test for infinite loop2 FAILED
        Error: Infinite loop
            at Function.INFINITE_LOOP (node_modules/@flatten-js/core/dist/main.esm.js:180:16)
            at Function.testInfiniteLoop (node_modules/@flatten-js/core/dist/main.esm.js:236:38)
            at restoreFaces (node_modules/@flatten-js/core/dist/main.esm.js:1343:20)

It seems that I can avoid the error if I round the numbers.

It's a pleasure to use this library. Please let me know if I can help with something.

Karolis

[tansanDOTeth]

I got this occasionally too. Thanks for reporting this.

[alexbol99]

Hi, @karolis-k , Do you use equal method from Relations?

[karolis-k]

Yes: import equal = Flatten.Relations.equal;

[alexbol99]

This method uses boolean operations to calculate relations. Very close values cause accuracy problems, it is difficult to solve them Maybe, need to create simple method that check equality by compare vertices, what do you think?

[karolis-k]

For my purposes I created a method which does that, but it's not that simple :) and it doesn't cover all cases, e.g. loops.

// Polygons with loops are not supported.
export function arePolygonsSame(p1: L.LatLngLiteral[], p2: L.LatLngLiteral[]): boolean {
    function arePolygonsSameNonInvertedOrder(
        pi1: L.LatLngLiteral[],
        pi2: L.LatLngLiteral[]
    ): boolean {
        const points1 = pi1.map(latLngToPoint);
        const points2 = pi2.map(latLngToPoint);
        const ind1 = points2.findIndex(p => arePoints2DSame(p, points1[0]));
        if (ind1 < 0) {
            return false;
        }

        let i = 0;
        let j = ind1;
        while (i < points1.length) {
            if (j === points2.length) {
                j = 0;
            }

            // While next point in first array is duplicate - skip it.
            while (arePoints2DSame(points1[i], points1[i + 1 !== points1.length ? i + 1 : 0])) {
                // All elements till end were checked.
                if (i + 1 === points1.length) {
                    break;
                }
                i++;
            }

            // While next point in second array is duplicate - skip it.
            while (arePoints2DSame(points2[j], points2[j + 1 !== points2.length ? j + 1 : 0])) {
                if (j + 1 === points2.length) {
                    j = 0;
                } else {
                    j++;
                }
                if ((j + 1 !== points2.length ? j + 1 : 0) === ind1) {
                    break;
                }
            }

            if (!arePoints2DSame(points1[i], points2[j])) {
                return false;
            }

            i++;
            j++;
        }
        if (j === points2.length) {
            j = 0;
        }
        if (j !== ind1) {
            // First array is all checked, but not in second.
            return false;
        }
        return true;
    }

    return (
        arePolygonsSameNonInvertedOrder(p1, p2) || arePolygonsSameNonInvertedOrder(p1.reverse(), p2)
    );
}

I have unit tests if you'll need.

[alexbol99]

Yes, this method does not support the case when polygon has more than one loop (face). But even with one loop equal polygons may have kind of shift in the vertex order, this case is not supported too.

I think need to locate an edge on the second polygon with findEdgeByPoint() and then iterate both loops checking equality of the edges. Need to take into consideration that some edges may be arcs.

But this method will be ok for simple cases.

[karolis-k]

If understood the problem correctly - it should match polygons correctly if order is shifted, e.g. this unit test passes:

    it('returns true for two identical polygons in reversed order', () => {
        const p1 = [
            { lat: 0, lng: 0 },
            { lat: 0, lng: 1 },
            { lat: 1, lng: 1 },
            { lat: 1, lng: 0 },
            { lat: 1, lng: 0 },
            { lat: 1, lng: 0 },
        ];
        const p2 = [
            { lat: 1, lng: 0 },
            { lat: 1, lng: 1 },
            { lat: 0, lng: 1 },
            { lat: 0, lng: 0 },
        ];
        expect(arePolygonsSame(p1, p2)).toBe(true);
    });

Pay attention to this line: const ind1 = points2.findIndex(p => arePoints2DSame(p, points1[0]));

[alexbol99]

You are right, I missed this line

[karolis-k]

About arcs - you are correct. If you'd like to add it to this library then it would need to be adapted. I am not sure how easy it would be to check for arcs though. Adding face support maybe wouldn't be very hard (if it doesn't have to be very performant).