Maximizing the number of overlapping vertices between shapes. Is this a combinatronics problem?
Hi! I was trying to mathematically solve a positioning problem for a game I am playing and while I was able to postulate the problem; I feel my education has fallen me short to find a solution. The problem is as follows:
-
You have N shapes compromized of any number of vertices declared as integer offsets from their origin point (the origin point counts as a vertex).
-
Out of the N shapes you have to pick a group of Y size that maximizes the number of overlapping vertices between them with the following rules:
-- The origin point of each shape must be placed on a 2D integer grid.
-- The origin point of each shape must be different from each other shapes origin point.
-- The shapes can be rotated in steps of 90º any number of times.
-- For a vertex to count as overlapping it must be the exact same position as the vertex of at least one other shape and one of the vertices must be the origin point of a shape.
Where could I read material to advance in this problem? Is there an algorithm for these problems?
6 replies
Feels like more of an algorithm problem than combinatorics. Not saying I will know the answer but I can think of a few clarifications:
Hi! Here are some clarifications:
I'll be adding these clarifications up above!
What is the output you are looking for? The minimum number of distinct vertices needed to create all the shapes?
I am looking for a list of origin coordinates and orientations that would occur in the maximum possible number of vector overlaps between these shapes. Maybe looking for the minimum number of distinct vertices helps it?
I am making a small recreation of the system on Godot to see if I understand the problem better.
Like another commenter said, I think this is going to be an algorithmic solution.
Are you shapes able to be translated across the plane, or must they stay in position and just be rotated? If rotated, by some pivot point in the center, or that origin vertex?
Hi! I've advanced a bit more on the and now got a script that calculates the overlaps between pairs of shapes for each of their cardinal orientation. Source code is avaliable on codeberg. It is quite the brute force approach so while it works with the 30 or so possible configurations of the game I doubt it'd scale with the ~~O(n^4) nature of it.
What's left is processing the data structure to figure out which combination of 6 shapes/characters and in which positions and orientations would maximize it.
Regardless, I want to thank you and @[email protected] for helping me clarify through the problem.