मुझे इस समस्या को हल करने के लिए एक एल्गोरिदम की आवश्यकता है: किसी भी कोने में एक साथ दो आयतों को छेड़छाड़ या ओवरलैप करने के लिए, मैं ओवरलैप्ड (चौराहे) क्षेत्र के बिना दो आयताकारों के लिए कुल क्षेत्र कैसे निर्धारित करूं? मतलब चौराहे के क्षेत्र की गणना पहली बार आयत के साथ, या दूसरे के साथ की जानी चाहिए।आयतों को छेड़छाड़ करने का कुल क्षेत्र
यह आसान है। चौराहे के पहले गणना निर्देशांक, जो एक आयताकार भी है। r1.area + r2.area - intersection.area:
left = max(r1.left, r2.left)
right = min(r1.right, r2.right)
bottom = max(r1.bottom, r2.bottom)
top = min(r1.top, r2.top)
तो फिर, अगर चौराहे खाली नहीं है (left < right && bottom < top), यह दो आयतों के सामान्य क्षेत्र से घटाना।
पुनश्च:
bottom = min(r1.bottom, r2.bottom) top = max(r1.top, r2.top)
धन्यवाद लेकिन यदि आपको कोई फर्क नहीं पड़ता कि आप कोड में आयताकार का प्रतिनिधित्व कैसे कर सकते हैं क्योंकि उपयोगकर्ता आयताकार में नीचे बाएं किनारे और ऊपरी दाएं किनारे को इनपुट कर सकता है तो इसका प्रतिनिधित्व कैसे करें? –
और जटिलता ओ (एन^2) –
@al_khater से कम होनी चाहिए जब आप ओ (एन^2) कहें तो 'एन' क्या है? आपकी मूल समस्या में केवल दो आयत हैं, जिसका अर्थ केवल 8 अंक है। –
चौराहे के निर्देशांक सही अगर संदर्भ (0,0) संदर्भ प्रणाली के निचले बाएं हिस्से में रखा गया है तो सही करें।
इमेज प्रोसेसिंग, जहां मूल (0,0) आमतौर पर पर रखा गया है में ऊपर-बाएं संदर्भ प्रणाली, निर्देशांक नीचे और चौराहे के शीर्ष के होगा:
bottom = min(r1.bottom, r2.bottom)
top = max(r1.top, r2.top)
यहाँ पूर्ण समाधान है जावा का उपयोग करके इस एल्गोरिदम के लिए:
public static int solution(int K, int L, int M, int N, int P, int Q, int R,
int S) {
int left = Math.max(K, P);
int right = Math.min(M, R);
int bottom = Math.max(L, Q);
int top = Math.min(N, S);
if (left < right && bottom < top) {
int interSection = (right - left) * (top - bottom);
int unionArea = ((M - K) * (N - L)) + ((R - P) * (S - Q))
- interSection;
return unionArea;
}
return 0;
}
देर से पार्टी में आने के लिए खेद है। मुझे पता है न आप भाषा देख रहे हैं विशिष्ट: लेकिन iOS पर अपनी सुंदर आसान:
CGRectIntersection
यह आप CGrect कि दिए गए दो rects द्वारा overlappring है देना होगा। यदि वे अंतर नहीं कर रहे हैं तो CGRectIsNull वापस आ जाएगा।
उम्मीद है कि कम से कम किसी की मदद करें। हैप्पी कोडिंग
मैंने देखा कि इस प्रश्न का उत्तर नहीं दिया गया था, इसलिए मैंने समीकरण को आजमाने के लिए एक छोटा जावा कार्यक्रम लिखा था कि @ विकोजर्डन और @ निकिता रायबक ने पिछले उत्तरों में बात की है। उम्मीद है की यह मदद करेगा।
/**
* This function tries to see how much of the smallest rectangle intersects
* the with the larger one. In this case we call the rectangles a and b and we
* give them both two points x1,y1 and x2, y2.
*
* First we check for the rightmost left coordinate. Then the leftmost right
* coordinate and so on. When we have iLeft,iRight,iTop,iBottom we try to get the
* intersection points lenght's right - left and bottom - top.
* These lenght's we multiply to get the intersection area.
*
* Lastly we return the result of what we get when we add the two areas
* and remove the intersection area.
*
* @param xa1 left x coordinate A
* @param ya1 top y coordinate A
* @param xa2 right x coordinate A
* @param ya2 bottom y coordinate A
* @param xb1 left x coordinate B
* @param yb1 top y coordinate B
* @param xb2 right x coordinate B
* @param yb2 bottom y coordinate B
* @return Total area without the extra intersection area.
*/
public static float mostlyIntersects(float xa1, float ya1, float xa2, float ya2, float xb1, float yb1, float xb2, float yb2) {
float iLeft = Math.max(xa1, xb1);
float iRight = Math.min(xa2, xb2);
float iTop = Math.max(ya1, yb1);
float iBottom = Math.min(ya2, yb2);
float si = Math.max(0, iRight - iLeft) * Math.max(0, iBottom - iTop);
float sa = (xa2 - xa1) * (ya2 - ya1);
float sb = (xb2 - xb1) * (yb2 - yb1);
return sa + sb - si;
}
विश्लेषण और लीटकोड परीक्षण परिणामों के साथ एक स्विफ्ट-संस्करण समाधान।
/**
Calculate the area of intersection of two given rectilinear rectangles.
- Author:
Cong Liu <congliu0704 at gmail dot com>
- Returns:
The area of intersection of two given rectilinear rectangles.
- Parameters:
- K: The x coordinate of the lower left point of rectangle A
- L: The y coordinate of the lower left point of rectangle A
- M: The x coordinate of the upper right point of rectangle A
- N: The y coordinate of the upper right point of rectangle A
- P: The x coordinate of the lower left point of rectangle B
- Q: The y coordinate of the lower left point of rectangle B
- R: The x coordinate of the upper right point of rectangle B
- S: The y coordinate of the upper right point of rectangle B
- Assumptions:
All the eight given coordinates (K, L, M, N, P, Q, R and S) are integers
within the range [-2147483648...2147483647], that is, Int32-compatible.
K < M, L < N, P < R, Q < S
- Analysis:
The area of intersected is dyIntersected * dxIntersected.
To find out dyIntersected, consider how y coordinates of two rectangles relate
to each other, by moving rectangle A from above rectangle B down.
Case 1: when N > L >= S > Q, dyIntersected = 0
Case 2: when N >= S > L >= Q, dyIntersected = S - L
Case 3: when S > N > L >= Q, dyIntersected = N - L
Case 4: when S >= N >= Q > L, dyIntersected = N - Q
Case 5: when N > S > Q > L, dyIntersected = S - Q
Cases 2 and 3 can be merged as Case B:
when L >= Q, dyIntersected = min(N, S) - L
Cases 4 and 5 can be merged as Case C:
when Q > L, dyIntersected = min(N, S) - Q
Cases B and C can be merged as Case D:
when S > L , dyIntersected = min(N, S) - max(L, Q)
Likewise, x coordinates of two rectangles relate similarly to each other:
Case 1: when R > P >= M > K, dxIntersected = 0
Case 2: when M > P , dxIntersected = min(R, M) - max(P, K)
- Submission Date:
Sat 20 Jan 2018 CST at 23:28 pm
- Performance:
https://leetcode.com/problems/rectangle-area/description/
Status: Accepted
3081/3081 test cases passed.
Runtime: 78 ms
*/
class Solution {
public static func computeArea(_ K: Int, _ L: Int, _ M: Int, _ N: Int, _ P: Int, _ Q: Int, _ R: Int, _ S: Int) -> Int {
let areaA : Int = Int((M - K) * (N - L))
let areaB : Int = Int((R - P) * (S - Q))
var xIntersection : Int = 0
var yIntersection : Int = 0
var areaIntersection : Int = 0
if ((min(M, R) - max(K, P)) > 0) {
xIntersection = Int(min(M, R) - max(K, P))
}
if ((min(N, S) - max(L, Q)) > 0) {
yIntersection = Int(min(N, S) - max(L, Q))
}
if ((xIntersection == 0) || (yIntersection == 0)) {
areaIntersection = 0
} else {
areaIntersection = Int(xIntersection * yIntersection)
}
return (areaA + areaB - areaIntersection)
}
}
// A simple test
Solution.computeArea(-4, 1, 2, 6, 0, -1, 4, 3) // returns 42
क्या आपके पास चौराहे बिंदुओं की स्थिति है? – karatedog