Find area of 2d polygon formed by rect and line
I'm making game in Unity. There's a rectangle intersected by a straight line. I need to find which part of rect is bigger and how much. Do anyone knows algorithm how to do this?
Rect and lines are set with points (4 for rect and 2 for lines)
The implicit equation of the line is
S(x,y) = (x - x0) (y1 - y0) - (y - y0) (x1 - x0) = 0
When you plug the coordinates of a corner, the sign of S(x, y) tells you on what side of the line you are. And better, if you evaluate Sa and Sb at two corners and they have different signs, the intersection is at a fraction Sa / (Sa - Sb) along the side ab.
Now, process all four edges in turn in clockwise order. For every edge, keep the starting corner if positive and keep the intersection if any. In the end, you'll get 0 to 5 points defining the convex polygon which is in the positive domain.
The area is found by the shoelace formula.
- 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
- Return a new string that sorts between two given strings
- 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)