आयत के रूप में दो आयताकारों के बीच अंतर (एक्सओआर)?

Question

मैं दो आयताकारों के बीच अंतर की गणना करने के लिए एक आसान तरीका ढूंढ रहा हूं। मेरा मतलब है कि सभी बिंदु जो आयतों में से एक हैं, लेकिन दोनों के लिए नहीं (इसलिए यह एक्सओआर की तरह है)।

आयताकार इस मामले में धुरी-गठबंधन हैं, इसलिए केवल सही कोण होंगे। मेरा मानना ​​है कि अंतर क्षेत्र को 0-4 आयताकारों में व्यक्त किया जा सकता है (0 यदि दोनों आयताकार समान हैं, 1 यदि केवल एक किनारा अलग है, तो सामान्य मामले में 4), और मैं अंतर क्षेत्र को सूची के रूप में प्राप्त करना चाहता हूं आयताकारों का।

आप इसे स्क्रीन के उन क्षेत्रों के बारे में भी सोच सकते हैं जिन्हें एक ठोस आयताकार/आकार बदलते समय अपडेट किया जाना है।

उदाहरण: आयत की चौड़ाई को दोगुना करना "ए" - मुझे जोड़ा क्षेत्र (आर) चाहिए।

+----+----+ 
| a | R | 
| | | 
+----+----+     

पारस्परिक आयतों (ए और बी) - मैं क्षेत्र आयतों में टी, एल, आर और बी (अन्य विभाजन संभव) द्वारा दिया गया है, लेकिन छोड़कर एक्स हैं:

+------------+ a 
|  T  | 
|·····+------+-----+ b 
| L | X | R | 
|  |  |  | 
+-----+------+·····| 
     | B  | 
     +------------+ 

मैं था एक अजगर समाधान/पुस्तकालय पसंद करते हैं, लेकिन कोई भी मजबूत एल्गोरिदम सहायक होगा।

Answer 1

समस्या एक प्रति अक्ष आधार पर नीचे विभाजित। आपके आयताकारों को प्रत्येक अक्ष पर उनके स्पैन के संदर्भ में परिभाषित किया जा सकता है - प्रत्येक अक्ष पर दिलचस्प बिंदु खोजें जहां आयताकार शुरू होता है या समाप्त होता है और फिर उन परिणामों में अपने परिणामों को परिभाषित करता है। यह आपको अंतर क्षेत्रों के 6 आयत देगा, आप आसानी से उन चारों तक गठबंधन कर सकते हैं जिन्हें आपने सचित्र किया है या यदि आपको आवश्यकता हो तो अपरिवर्तनीय शून्य-क्षेत्र आयतों को खत्म कर सकते हैं।

यहाँ एक जावा कार्यान्वयन है: https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Rectangle_difference

यह "4-क्षेत्र आयत अंतर" कहा जाता है:

public class Rect 
{ 
    private float minX, maxX, minY, maxY; 

    public Rect(float minX, float maxX, float minY, float maxY) 
    { 
     this.minX = minX; 
     this.maxX = maxX; 
     this.minY = minY; 
     this.maxY = maxY; 
    } 

    /** 
    * Finds the difference between two intersecting rectangles 
    * 
    * @param r 
    * @param s 
    * @return An array of rectangle areas that are covered by either r or s, but 
    *   not both 
    */ 
    public static Rect[] diff(Rect r, Rect s) 
    { 
     float a = Math.min(r.minX, s.minX); 
     float b = Math.max(r.minX, s.minX); 
     float c = Math.min(r.maxX, s.maxX); 
     float d = Math.max(r.maxX, s.maxX); 

     float e = Math.min(r.minY, s.minY); 
     float f = Math.max(r.minY, s.minY); 
     float g = Math.min(r.maxY, s.maxY); 
     float h = Math.max(r.maxY, s.maxY); 

     // X = intersection, 0-7 = possible difference areas 
     // h +-+-+-+ 
     // . |5|6|7| 
     // g +-+-+-+ 
     // . |3|X|4| 
     // f +-+-+-+ 
     // . |0|1|2| 
     // e +-+-+-+ 
     // . a b c d 

     Rect[] result = new Rect[ 6 ]; 

     // we'll always have rectangles 1, 3, 4 and 6 
     result[ 0 ] = new Rect(b, c, e, f); 
     result[ 1 ] = new Rect(a, b, f, g); 
     result[ 2 ] = new Rect(c, d, f, g); 
     result[ 3 ] = new Rect(b, c, g, h); 

     // decide which corners 
     if(r.minX == a && r.minY == e || s.minX == a && s.minY == e) 
     { // corners 0 and 7 
      result[ 4 ] = new Rect(a, b, e, f); 
      result[ 5 ] = new Rect(c, d, g, h); 
     } 
     else 
     { // corners 2 and 5 
      result[ 4 ] = new Rect(c, d, e, f); 
      result[ 5 ] = new Rect(a, b, g, h); 
     } 

     return result; 
    } 
} 

Answer 2

मैं कल्पना करता हूं कि छेड़छाड़ आयत (जो एक्स है) का क्षेत्र ढूंढना और आयताकार के संयुक्त क्षेत्र से कटौती करना + आयताकार बी आपके समाधान को देगा।

मैं तुरंत उत्तर के लिए मेरी खोज पर इस पाया:

http://tekpool.wordpress.com/2006/10/12/rectangle-intersection-find-the-intersecting-rectangle/

Answer 3

इस कड़ी में एक एल्गोरिथ्म है।

यह मूल रूप से चार संभावित आयताकारों की गणना करता है जो दूसरे से एक आयताकार घटाने के बाद रह सकते हैं।

इस मामले में, एल्गोरिदम को दो बार दौड़ना होगा।