पॉलीगॉन छेड़छाड़ विफल हो जाती है, टकराव "आकार" बहुत बड़ा

Question

ठीक है, इसलिए मैं एक साधारण क्षुद्रग्रह क्लोन बनाने की कोशिश कर रहा हूं। टकराव का पता लगाने के अलावा, सब कुछ ठीक काम करता है।

मैं दो अलग अलग संस्करण है, पहले एक java.awt.geom.Area उपयोग करता है:

// polygon is a java.awt.Polygon and p is the other one 
final Area intersect = new Area(); 
intersect.add(new Area(polygon)); 
intersect.intersect(new Area(p.polygon)); 
return !intersect.isEmpty(); 

यह एक आकर्षण की तरह काम करता है ... आप केवल 120 के लिए लगभग 40% सीपीयू परवाह नहीं है अगर क्षुद्रग्रहों :(

तो मैं प्रसिद्ध अलग अक्ष प्रमेय के लिए शुद्ध खोज की है, के बाद से मैं thaaaaaat अच्छा एक गणित मैं here से कार्यान्वयन लिया और परिवर्तित मेरी जावा फिट करने के लिए की जरूरत है नहीं कर रहा हूँ:

public double dotProduct(double x, double y, double dx, double dy) { 
     return x * dx + y * dy; 
    } 

    public double IntervalDistance(double minA, double maxA, double minB, 
      double maxB) { 
     if (minA < minB) { 
      return minB - maxA; 
     } else { 
      return minA - maxB; 
     } 
    } 

    public double[] ProjectPolygon(double ax, double ay, int p, int[] x, int[] y) { 
     double dotProduct = dotProduct(ax, ay, x[0], y[0]); 
     double min = dotProduct; 
     double max = dotProduct; 
     for (int i = 0; i < p; i++) { 
      dotProduct = dotProduct(x[i], y[i], ax, ay); 
      if (dotProduct < min) { 
       min = dotProduct; 
      } else if (dotProduct > max) { 
       max = dotProduct; 
      } 
     } 
     return new double[] { min, max }; 
    } 

    public boolean PolygonCollision(Asteroid ast) { 
     int edgeCountA = points; 
     int edgeCountB = ast.points; 
     double edgeX; 
     double edgeY; 

     for (int edgeIndex = 0; edgeIndex < edgeCountA + edgeCountB; edgeIndex++) { 
      if (edgeIndex < edgeCountA) { 
       edgeX = xp[edgeIndex] * 0.9; 
       edgeY = yp[edgeIndex] * 0.9; 
      } else { 
       edgeX = ast.xp[edgeIndex - edgeCountA] * 0.9; 
       edgeY = ast.yp[edgeIndex - edgeCountA] * 0.9; 
      } 

      final double x = -edgeY; 
      final double y = edgeX; 
      final double len = Math.sqrt(x * x + y * y); 
      final double axisX = x/len; 
      final double axisY = y/len; 

      final double[] minMaxA = ProjectPolygon(axisX, axisY, points, xp, 
        yp); 
      final double[] minMaxB = ProjectPolygon(axisX, axisY, ast.points, 
        ast.xp, ast.yp); 

      if (IntervalDistance(minMaxA[0], minMaxA[1], minMaxB[0], minMaxB[1]) > 0) { 
       return false; 
      } 
     } 
     return true; 
    } 

यह काम करता है ... थोड़े। दरअसल ऐसा लगता है कि इस कोड का उपयोग करते समय क्षुद्रग्रहों का "टक्कर हल" बहुत बड़ा है, यह क्षुद्रग्रह के आकार के 1.2 गुना की तरह है। और मेरे पास कोई सुराग नहीं है।
http://www.spielecast.de/stuff/asteroids1.png
http://www.spielecast.de/stuff/asteroids2.png

आप उम्मीद है कि देख सकते हैं, चित्र में क्षुद्रग्रहों चित्र 2 में लोगों को जहां सैट कोड का उपयोग है की तुलना में काफी सघन हैं:

यहाँ तुलना के लिए दो तस्वीरें हैं।

तो कोई विचार? या क्या कोई जावा के लिए पॉलीगॉन कार्यान्वयन जानता है जिसमें चौराहे परीक्षण शामिल हैं जिनका मैं उपयोग कर सकता हूं?

Answer 1

ऐसा लगता है कि आपका दूसरा परिणाम टकराव का पता लगा रहा है जैसे कि बहुभुज उनके त्रिज्या के साथ सर्कल थे, जो केंद्र से बहुभुज के सबसे दूर बिंदु पर सेट होते थे। मैंने देखा है कि ज्यादातर टक्कर पहचान सामग्री एक साधारण बाउंडिंग बॉक्स (या तो एक सर्कल या आयताकार) बनाता है जिसमें बहुभुज फिट हो सकता है। केवल तभी जब दो बाउंडिंग बॉक्स छेड़छाड़ करते हैं (एक बहुत ही सरल गणना) क्या आप अधिक विस्तृत पहचान जारी रखते हैं। शायद विनियमित एल्गोरिदम केवल बाध्यकारी बॉक्स कैलक्यूलेटर के रूप में लक्षित है?

संपादित करें: इसके अलावा, अगर निकायों में से एक उत्तल नहीं है विकिपीडिया

से प्रमेय लागू नहीं होता।

आपकी छवि में कई क्षुद्रग्रहों में अवतल सतहें हैं।