algorithm - मैं कुशलतापूर्वक कैसे निर्धारित करूं कि बहुभुज उत्तल, गैर-उत्तल या जटिल है या नहीं?




geometry polygon (7)

नोट: बिंदुओं के एक सेट के उत्तल ढक्कन की गणना पूरी तरह अनावश्यक है यदि आप केवल यह निर्धारित करना चाहते हैं कि बहुभुज का प्रतिनिधित्व करने वाले बिंदुओं की एक सूची उत्तल बहुभुज का प्रतिनिधित्व करती है या नहीं।

गिफ्ट रैपिंग एल्गोरिदम देखें:

मान लें कि आपके सभी बहुभुज विपरीत दिशा में हैं, जिस क्षण आपका गैर-प्रारंभिक ध्रुवीय कोण बाएं मोड़ बनाता है, आपको पता है कि यह उत्तल नहीं है।

यदि आप बहुभुज जटिल हैं (लेकिन मुझे यकीन नहीं है कि यह सबसे तेज़ तरीका है) तो आप देख सकते हैं कि रेखा खंड एक दूसरे के साथ छेड़छाड़ करते हैं या नहीं।

XFillPolygon लिए मैन पेज से:

  • यदि shape जटिल है , तो पथ स्वयं-अंतर कर सकता है। ध्यान दें कि पथ में संगत संयोग बिंदुओं को आत्म-चौराहे के रूप में नहीं माना जाता है।

  • यदि shape उत्तल है , बहुभुज के अंदर बिंदुओं की प्रत्येक जोड़ी के लिए, उन्हें जोड़ने वाले रेखा खंड पथ को छेड़छाड़ नहीं करते हैं। यदि ग्राहक द्वारा ज्ञात है, तो Convex निर्दिष्ट प्रदर्शन प्रदर्शन में सुधार कर सकते हैं। यदि आप उत्तल नहीं होने वाले पथ के लिए उत्तल निर्दिष्ट करते हैं, तो ग्राफिक्स परिणाम अपरिभाषित होते हैं।

  • यदि shape Nonconvex है , तो पथ आत्म-अंतर नहीं करता है, लेकिन आकार पूरी तरह से उत्तल नहीं है। यदि ग्राहक द्वारा ज्ञात है, तो कॉम्प्लेक्स के बजाय Nonconvex निर्दिष्ट करना प्रदर्शन में सुधार कर सकता है। यदि आप स्वयं- अंतरण पथ के लिए Nonconvex निर्दिष्ट करते हैं, तो ग्राफिक्स परिणाम अपरिभाषित हैं।

मुझे XFillPolygon भरने के साथ प्रदर्शन समस्याएं आ रही हैं और, जैसा कि मैन पेज सुझाता है, पहला कदम जो मैं लेना चाहता हूं वह बहुभुज के सही आकार को निर्दिष्ट करना है। मैं वर्तमान में सुरक्षित पक्ष पर होने के लिए कॉम्प्लेक्स का उपयोग कर रहा हूं।

क्या यह निर्धारित करने के लिए एक कुशल एल्गोरिदम है कि बहुभुज (निर्देशांक की एक श्रृंखला द्वारा परिभाषित) उत्तल, गैर-उत्तल या जटिल है?


आप गिफ्ट-रैपिंग एल्गोरिदम की तुलना में चीजों को बहुत आसान बना सकते हैं ... यह एक अच्छा जवाब है जब आपके पास किसी विशेष सीमा के बिंदुओं का एक सेट होता है और उत्तल हल ढूंढने की आवश्यकता होती है।

इसके विपरीत, उस मामले पर विचार करें जहां बहुभुज स्वयं को छेड़छाड़ नहीं कर रहा है, और इसमें एक सूची में बिंदुओं का एक सेट होता है जहां लगातार अंक सीमा बनाते हैं। इस मामले में यह पता लगाना बहुत आसान है कि बहुभुज उत्तल है या नहीं (और आपको किसी भी कोण की गणना करने की आवश्यकता नहीं है):

बहुभुज के प्रत्येक किनारों की प्रत्येक जोड़ी (अंक के प्रत्येक तिगुना) के लिए, बढ़ते क्रम में बिंदुओं की ओर इशारा करते हुए किनारों द्वारा परिभाषित वेक्टरों के क्रॉस उत्पाद के जेड-घटक की गणना करें। इन वैक्टरों का क्रॉस उत्पाद लें:

 given p[k], p[k+1], p[k+2] each with coordinates x, y:
 dx1 = x[k+1]-x[k]
 dy1 = y[k+1]-y[k]
 dx2 = x[k+2]-x[k+1]
 dy2 = y[k+2]-y[k+1]
 zcrossproduct = dx1*dy2 - dy1*dx2

बहुभुज उत्तल है यदि क्रॉस उत्पादों के जेड-घटक या तो सभी सकारात्मक या सभी नकारात्मक हैं। अन्यथा बहुभुज nonconvex है।

यदि एन अंक हैं, तो सुनिश्चित करें कि आप एन क्रॉस उत्पादों की गणना करते हैं, उदाहरण के लिए ट्रिपलेट्स (पी [एन -2], पी [एन -1], पी [0]) और (पी [एन -1] का उपयोग करना सुनिश्चित करें, पी [0], पी [1])।

यदि बहुभुज स्वयं को छेड़छाड़ कर रहा है, तो यह उत्परिवर्तन की तकनीकी परिभाषा में विफल रहता है भले ही उसके निर्देशित कोण एक ही दिशा में हों, इस स्थिति में उपर्युक्त दृष्टिकोण सही परिणाम नहीं देगा।


निम्नलिखित जावा फ़ंक्शन / विधि इस उत्तर में वर्णित एल्गोरिदम का कार्यान्वयन है।

public boolean isConvex()
{
    if (_vertices.size() < 4)
        return true;

    boolean sign = false;
    int n = _vertices.size();

    for(int i = 0; i < n; i++)
    {
        double dx1 = _vertices.get((i + 2) % n).X - _vertices.get((i + 1) % n).X;
        double dy1 = _vertices.get((i + 2) % n).Y - _vertices.get((i + 1) % n).Y;
        double dx2 = _vertices.get(i).X - _vertices.get((i + 1) % n).X;
        double dy2 = _vertices.get(i).Y - _vertices.get((i + 1) % n).Y;
        double zcrossproduct = dx1 * dy2 - dy1 * dx2;

        if (i == 0)
            sign = zcrossproduct > 0;
        else if (sign != (zcrossproduct > 0))
            return false;
    }

    return true;
}

एल्गोरिदम को तब तक काम करने की गारंटी दी जाती है जब तक कि शिखर का आदेश दिया जाता है (या तो घड़ी की दिशा में या विपरीत दिशा में), और आपके पास स्वयं-अंतरण वाले किनारों (यानी यह केवल साधारण बहुभुज के लिए काम करता है) नहीं है।


मैंने दोनों एल्गोरिदम लागू किए: एक यूरीगोरेन द्वारा पोस्ट किया गया (एक छोटा सुधार - केवल पूर्णांक गणित के साथ) और जावा में @RoryDaulton से एक। मुझे कुछ समस्याएं थीं क्योंकि मेरा बहुभुज बंद है, इसलिए दोनों एल्गोरिदम अवतल के रूप में दूसरे पर विचार कर रहे थे, जब यह उत्तल था। तो मैंने इस तरह की स्थिति को रोकने के लिए इसे बदल दिया। मेरी विधियां आधार सूचकांक का भी उपयोग करती हैं (जो 0 हो सकती है या नहीं)।

ये मेरे परीक्षण शिखर हैं:

// concave
int []x = {0,100,200,200,100,0,0};
int []y = {50,0,50,200,50,200,50};

// convex
int []x = {0,100,200,100,0,0};
int []y = {50,0,50,200,200,50};

और अब एल्गोरिदम:

private boolean isConvex1(int[] x, int[] y, int base, int n) // Rory Daulton
{
  final double TWO_PI = 2 * Math.PI;

  // points is 'strictly convex': points are valid, side lengths non-zero, interior angles are strictly between zero and a straight
  // angle, and the polygon does not intersect itself.
  // NOTES:  1.  Algorithm: the signed changes of the direction angles from one side to the next side must be all positive or
  // all negative, and their sum must equal plus-or-minus one full turn (2 pi radians). Also check for too few,
  // invalid, or repeated points.
  //      2.  No check is explicitly done for zero internal angles(180 degree direction-change angle) as this is covered
  // in other ways, including the `n < 3` check.

  // needed for any bad points or direction changes
  // Check for too few points
  if (n <= 3) return true;
  if (x[base] == x[n-1] && y[base] == y[n-1]) // if its a closed polygon, ignore last vertex
     n--;
  // Get starting information
  int old_x = x[n-2], old_y = y[n-2];
  int new_x = x[n-1], new_y = y[n-1];
  double new_direction = Math.atan2(new_y - old_y, new_x - old_x), old_direction;
  double angle_sum = 0.0, orientation=0;
  // Check each point (the side ending there, its angle) and accum. angles for ndx, newpoint in enumerate(polygon):
  for (int i = 0; i < n; i++)
  {
     // Update point coordinates and side directions, check side length
     old_x = new_x; old_y = new_y; old_direction = new_direction;
     int p = base++;
     new_x = x[p]; new_y = y[p];
     new_direction = Math.atan2(new_y - old_y, new_x - old_x);
     if (old_x == new_x && old_y == new_y)
        return false; // repeated consecutive points
     // Calculate & check the normalized direction-change angle
     double angle = new_direction - old_direction;
     if (angle <= -Math.PI)
        angle += TWO_PI;  // make it in half-open interval (-Pi, Pi]
     else if (angle > Math.PI)
        angle -= TWO_PI;
     if (i == 0)  // if first time through loop, initialize orientation
     {
        if (angle == 0.0) return false;
        orientation = angle > 0 ? 1 : -1;
     }
     else  // if other time through loop, check orientation is stable
     if (orientation * angle <= 0)  // not both pos. or both neg.
        return false;
     // Accumulate the direction-change angle
     angle_sum += angle;
     // Check that the total number of full turns is plus-or-minus 1
  }
  return Math.abs(Math.round(angle_sum / TWO_PI)) == 1;
}

और अब उरी गोरेन से

private boolean isConvex2(int[] x, int[] y, int base, int n)
{
  if (n < 4)
     return true;
  boolean sign = false;
  if (x[base] == x[n-1] && y[base] == y[n-1]) // if its a closed polygon, ignore last vertex
     n--;
  for(int p=0; p < n; p++)
  {
     int i = base++;
     int i1 = i+1; if (i1 >= n) i1 = base + i1-n;
     int i2 = i+2; if (i2 >= n) i2 = base + i2-n;
     int dx1 = x[i1] - x[i];
     int dy1 = y[i1] - y[i];
     int dx2 = x[i2] - x[i1];
     int dy2 = y[i2] - y[i1];
     int crossproduct = dx1*dy2 - dy1*dx2;
     if (i == base)
        sign = crossproduct > 0;
     else
     if (sign != (crossproduct > 0))
        return false;
  }
  return true;
}

यह जांचने के लिए एक परीक्षण है कि बहुभुज उत्तल है या नहीं

बहुभुज के साथ तीन बिंदुओं के प्रत्येक सेट पर विचार करें। यदि प्रत्येक कोण 180 डिग्री या उससे कम है तो आपके पास उत्तल बहुभुज है। जब आप प्रत्येक कोण को समझते हैं, तो कुल मिलाकर 180 (कोण) रखें। एक उत्तल बहुभुज के लिए, यह कुल 360 होगा।

यह परीक्षण ओ (एन) समय में चलता है।

ध्यान दें, कि ज्यादातर मामलों में यह गणना कुछ ऐसा है जो आप एक बार कर सकते हैं और सहेज सकते हैं - अधिकांश समय आपके पास काम करने के लिए बहुभुज का एक सेट होता है जो हर समय बदल नहीं जाता है।


यह जांचने के लिए कि क्या बहुभुज उत्तल है, बहुभुज के प्रत्येक बिंदु प्रत्येक पंक्ति के साथ या पीछे स्तर होना चाहिए।

यहां एक उदाहरण चित्र है:


@RoryDaulton का जवाब मेरे लिए सबसे अच्छा लगता है, लेकिन अगर कोणों में से एक बिल्कुल 0 है तो क्या होगा? कुछ लोग इस तरह के एज केस को वापस लौटने के लिए चाहते हैं, इस मामले में, लाइन में "<=" से "<" बदलें:

if orientation * angle < 0.0:  # not both pos. or both neg.

यहां मेरे परीक्षण मामले हैं जो इस मुद्दे को हाइलाइट करते हैं:

# A square    
assert is_convex_polygon( ((0,0), (1,0), (1,1), (0,1)) )

# This LOOKS like a square, but it has an extra point on one of the edges.
assert is_convex_polygon( ((0,0), (0.5,0), (1,0), (1,1), (0,1)) )

दूसरा जवाब मूल उत्तर में विफल रहता है। इसे होना चाहिए? मेरे उपयोग के मामले में, मैं इसे पसंद करूंगा।





xlib