Efficient Packing Algorithm for Regular Polygons
I'm looking for a packing algorithm which will reduce a regular polygon into rectangles and right triangles. The algorithm should attempt to use as few such shapes as possible and should be relatively easy to implement (given the difficulty of the challenge).
If possible, the answer to this question should explain the general heuristics used in the suggested algorithm.
Solution
I think the answer is fairly simple for regular polygons.
Find an axis of symmetry, and draw a line between each vertex and its mirror. This divides the polygon into trapezoids. Each trapezoid can be turned into a rectangle and two right triangles.
- Is it possible to divide points to regions only based on their minimum distance to region-dividing curves?
- How can I find a number in a list (smaller than a given bound but the biggest one)?
- Balanced Partition greedy approach
- Algorithm for minimizing (s[i]-s[j]+d)/(i-j)
- Find longest substring
- Fish codility excercise
- Next prime number algorithm
- Using Loop invariant to prove correctness of merge sort (Initialization , Maintenance , Termination)
- Allocate bikes to people - First Priority (Closest bike to closest person)
- Isolation Forest Sklearn for 1D array or list and how to tune hyper parameters
- If the n-body problem is chaotic, why isn't it used as a RNG?
- Implementing Miller-Rabin in C
- Prove or disprove: there exists three vertexes a,b,c in a connected but incomplete graph satisfying a and b have a common neighbor c
- Boolean formula for a graph vertex-colouring algorithm
- heapq with custom compare predicate
- Algorithm to calculate number of intersecting discs
- Verifying the minimum cost from each node to a sink node in linear time
- Variations with repetition of r integers in {0...k} that sum to u
- How to reconstrunct a binary tree from an array produced by preorder tree traversal
- Two implementation methods of BFS for finding the shortest path, which one is the obvious winner?
- Determining coefficient of x^m term in (x^2 + x + 1)^n is even or odd
- How to merge 3 sorted arrays into 1 sorted array in Big-O(N) time?
- what is the best algorithm for this game?
- codility absolute distinct count from an array
- Avoid duplicates in N Queen iterative solutions (No Recursion Allowed)
- Split a binary search Tree
- minimum number of steps to reduce number to 1
- How to fix 'Codility FrogJump' Algorithm?
- Suffix tree VS Tries - in plain English , what's the difference?
- Pollard Rho factorization method implementation