Determining the minimal number of axis to test against in the SAT (Separating Axis Theorem)
Most implementations of the SAT algorithm I've seen involve testing each axis in either shape being tested against for collisions. But I recently implemented the SAT algorithm in python and noticed that for every single test case that worked when testing against all axes of either shape, it ALSO worked for every case when testing against only the axes of the shape with the GREATEST number of sides.
However, I have absolutely no clue how to prove or disprove this theory and I have minimal mathematical knowledge in proofs. Could someone help me out and prove or disprove this theory that the only axes I need to test against for the SAT are the ones on the shape with the greatest number of sides?
If you have a triangle and a square and only check the square's axes (X and Y), it will yield an erroneous collision if it's only separated via the diagonal axis.
Look at the picture for a better explain.
- What is the complexity of the sorted() function?
- Implementation for a Monotonic Increasing Queue
- Java, Shifting Elements in an Array
- Differences between backtracking and brute-force search
- Number of partition of `n` into sum of three squares (fast algorithm)
- Big Number Subtraction in C
- If the n-body problem is chaotic, why isn't it used as a RNG?
- Using BFS for Weighted Graphs
- Removing a node in an undirected graph that destroys a path between two other nodes
- Binary search function is correct but it returns undefined
- Algorithm to reverse an array/string only in terms of rotate operations
- Correctness of Deletion algorithm of BST in CLRS
- Time Complexities n(log(n)) and log(n^n)
- How do I find the closest possible sum of an array's elements to a particular value?
- Split on regex (more than a character, maybe variable width) and keep the separator like GNU awk
- Find the minimum number of edits to balance parentheses?
- How to improve pandas DF processing time on different combinations of calculated data
- Efficiently calculate an availability date from a list of project assignments and known capacity
- Optimized algorithm to schedule tasks with dependency?
- Difference between back tracking and dynamic programming
- Javascript data structures library
- Segmentation error when implementing the Hoare quick sort method
- Which of these implementations is canonical: storing the head and size variables, or storing the head, tail, and size?
- Visualization of calendar events. Algorithm to layout events with maximum width
- Tracing edges of pixels in a mask
- Longest Subarray with Maximum Bitwise AND
- Assigning codes to nodes such that codes are unique and create two groups which share common properties
- Randomly Split a Graph into Mini Graphs
- Recursion relation and overlapping sub problems
- Calculating the 90th percentile in O(n) time