5
$\begingroup$

I've got a big set of 2D polygons described as a set of points. I would like to take this set of polygons and find any that are the same shape, regardless of rotation, translation, or scale.

Each polygon has 3 or more points, and in some cases may have hundreds or thousands of points. There are hundreds of polygons in total. The polygons are optimised to remove runs of points that would form a straight line, e.g. the sequence $[(0,0), (10,10), (20,20)]$ would not be allowed. The polygons also aren't allowed to intersect themselves.

The context for this problem is geometry instancing in 3D rendering, specifically rendering polygon regions and fills from PCB designs. Polygon regions are frequently repeated or copy-pasted around boards, so I would like to reduce the number of draw calls I need per frame by finding any polygon that I can instance using a transformation matrix.

My first idea was to normalise the scale of all polygons, then compare the line lengths and angles between line vectors. Two polygons with the same shape should be composed from the same line lengths and same angles in the same order.

I started implementing this, using the following procedure:

  1. Group all polygons by point count.
  2. Discard any groups that contain only one polygon, since they are guaranteed to be unique in shape.
  3. Center each polygon to $(0,0)$ and normalise its scale to a 1x1 bounding box.
  4. Calculate a "hash" for each polygon based on the sum of the magnitudes of all points, i.e. $\sum \sqrt{{x_i}^2 + {y_i}^2}$, which for any two polygons sharing the same shape should be equal.
  5. Further group the polygons by this hash, and discard any groups that have only one member. This acts as a fast filtering step to quickly reject any polygons which are obviously not the same.
  6. Turn each polygon's point list into a circular list of angle-distance pairs, $(\theta,d)$, where $\theta$ is the angle formed between the vectors meeting at the point, and $d$ is the length of the next clockwise vector.
  7. Within each group, compare all of the lists to each other to find matches.

This works in theory, but I ran into two issues. First, "clockwise" isn't well-defined for arbitrary polygons that may have both concave and convex regions. This can be solved by traversing the lists in both directions during the final step, which has the added bonus of finding mirror-image copies of the same polygon, which could be described as a negative scale in one or both of the axes, and which I can handle just fine in the instancing code. Second, and more importantly, I couldn't come up with an efficient way to compare the two circular lists of points without knowing the correct starting offsets.

It occurs to me that there might be some efficient mathematical way of identifying whether two circular sequences of number pairs contain the same ordered sequence of values regardless of whether the sequences are offset from each other.

For example, $[1,2,3,5,2]$ and $[3,5,2,1,2]$ should be considered equal because they are the same set of numbers in the same order, just with a different starting offset (the latter is the former shifted two places left). However, $[1,2,3,5,2]$ and $[2,5,3,2,1]$ should not be considered equal, because the ordering is incorrect despite the same numbers appearing in the set. In practice the elements in each list would actually be a pair of numbers rather than a single number, but that's an implementation detail.

Is there a clever way to solve this?

If not, is there an alternative approach to the polygon shape comparison problem?

$\endgroup$
6
  • $\begingroup$ Maybe a brute force approach, but you could write a function that takes in two lists of length $n$, duplicates the first list and joins the copies end to beginning, and then brute force searches for list equality checking the duplicated list elements $i,...,i+n-1$, with $i=1,...n$ against the other list. You are guaranteed to find a match for lists that are circular permutations of one another, and if the algorithm terminates, the lists are not related by that transformation. $\endgroup$ Commented Nov 15, 2022 at 0:51
  • $\begingroup$ Someone on Twitter has pointed out that for two sets $a$ and $b$ you can concatenate $b$ to itself to get $b+b$, and $a$ will be a subset of that longer sequence if it contains the same points in the same order. That reduces the problem to a string search, which isn't quite $O(n)$ but is pretty close. $\endgroup$
    – Polynomial
    Commented Nov 15, 2022 at 0:56
  • $\begingroup$ I think the real bottleneck here is finding the potential candidates for circular permutations. That would require you to find lists with exactly the same elements after sorting them as a first step , and then checking for circularity if they have the exact same matrix elements. $\endgroup$ Commented Nov 15, 2022 at 1:01
  • $\begingroup$ I don't think you even need to do that. The polygon shape is uniquely described by its normalised $(\theta,d)$ values, regardless of rotation/scaling/translation, and we're comparing two sets of equal length, so if $a \subset b^\frown b$ then that guarantees that the two polygons are the same shape. Something like KMP should do the job for the string search. Repeating with $a$ reversed finds mirrored copies, too. $\endgroup$
    – Polynomial
    Commented Nov 15, 2022 at 1:08
  • $\begingroup$ I'm not so sure about step 3. Scaling to a bounding box will make the scaling factor dependent on its orientation. For example an axis-aligned square becomes the same size as the bounding box, but a rotated square will become smaller. You should center it and then scale it to fit within a bounding circle. To ensure the centering is also not rotation dependent, calculate the centre of the polygon as the average of the vertex coordinates and subtract that. BTW, you don't need the square roots in step 4 (or 6), so get rid of them to speed it up. $\endgroup$ Commented Nov 15, 2022 at 15:54

1 Answer 1

1
$\begingroup$

Luckily I hang out with a bunch of people on Twitter and Mastodon who are way smarter than me, and they came up with some great ideas.

The core solution here is to concatenate one of the lists being compared to itself. For two equal-length sets $A$ and $B$, if $A \subset B^\frown B$ then $A$ must be the same sequence of $B$ with some rotation. This reduces the problem to a string search.

To demonstrate:

$$A = [1,2,3,5,2]$$ $$B = [3,5,2,1,2]$$ $$B' = B^\frown B = [3,5,2,\mathbf{1,2,3,5,2},1,2]$$ $$A \subset B'$$

For those not familiar with the notation (and for me when I inevitably come back to this answer in a year and I've forgotten set notation) the approach is essentially:

let a = "12352";
let b = "35212";
let b2 = b + b;
return b2.includes(a);

This can be optimised in a few ways.

First, the concatenation does not have to use $O(2n)$ memory, since the search can be performed on the original set by computing the search pointer (or array index) modulo the set length.

A KMP string search has a worst-case performance of $O(m)$ pre-processing and $O(n)$ matching, where $m$ is length of the string we're searching for and $n$ is the length of the string we're searching in. Since all polygons in each hash group need to be compared to each other, the pre-processing can be reused for repeated comparisons.

The KMP approach can then be modified a little to find a lexicographically minimal string rotation during the pre-processing step. This improves the average-case search performance a lot, because it is far more likely that $A$ and $B$ will have matching rotations. It's also a free optimisation, because it has the same $O(m)$ time complexity as the regular KMP pre-processing step.

Credit to @goopypanther for first suggesting the subset approach, and Jannis Harder (@jix) for suggesting the lexicographical rotation trick.

$\endgroup$
2
  • $\begingroup$ Hi, How does this approach handle changes in rotation? I assume that since your coordinates are listed by distance angle pairs, the rotation in global space is irrelevant - is that right? $\endgroup$
    – G.H.
    Commented Aug 30, 2023 at 4:16
  • 1
    $\begingroup$ @G.H. I believe that is the approach I used here, yes. Essentially the angles are taken between vertices, by whatever metric you like as long as it is consistent and only locally dependent, and then each element in the sequence being compared ends up being a (length, angle) tuple. $\endgroup$
    – Polynomial
    Commented Sep 1, 2023 at 17:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .