Timeline for Efficient way to find all polygons of the same shape within a set, regardless of position, scale, or rotation
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 13, 2022 at 16:15 | vote | accept | Polynomial | ||
| Nov 15, 2022 at 16:18 | comment | added | Polynomial | @JaapScherphuis Good point on the bounding circle; I hadn't considered that as a source of error. | |
| Nov 15, 2022 at 15:54 | comment | added | Jaap Scherphuis | 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. | |
| Nov 15, 2022 at 14:38 | answer | added | Polynomial | timeline score: 1 | |
| Nov 15, 2022 at 1:08 | comment | added | Polynomial | 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. | |
| Nov 15, 2022 at 1:01 | comment | added | WWM | 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. | |
| Nov 15, 2022 at 0:56 | comment | added | Polynomial | 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. | |
| Nov 15, 2022 at 0:51 | comment | added | WWM | 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. | |
| Nov 15, 2022 at 0:22 | history | asked | Polynomial | CC BY-SA 4.0 |