algorithm - मैं 2 डी बहुभुज के क्षेत्र की गणना कैसे करूं?




geometry 2d (11)

2 डी स्पेस में बिंदुओं की एक श्रृंखला मानते हुए जो आत्म-अंतर नहीं करते हैं, परिणामी बहुभुज के क्षेत्र को निर्धारित करने का एक प्रभावी तरीका क्या है?

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


मैं 2 डी बहुभुज के क्षेत्र की गणना के लिए कुछ सरल कार्य करने जा रहा हूं। यह उत्तल और अवतल बहुभुज दोनों के लिए काम करता है। हम बहुभुज को कई उप-त्रिकोणों में विभाजित करते हैं।

//don't forget to include cmath for abs function
struct Point{
  double x;
  double y;
}
// cross_product
double cp(Point a, Point b){ //returns cross product
  return a.x*b.y-a.y*b.x;
}

double area(Point * vertices, int n){  //n is number of sides
  double sum=0.0;
  for(i=0; i<n; i++){
    sum+=cp(vertices[i], vertices[(i+1)%n]); //%n is for last triangle
  }
  return abs(sum)/2.0;
}

पायथन कोड

जैसा कि यहां वर्णित है: http://www.wikihow.com/Calculate-the-Area-of-a-Polygon

पांडा के साथ

import pandas as pd

df = pd.DataFrame({'x': [10, 20, 20, 30, 20, 10, 0], 'y': [-10, -10, -10, 0, 10, 30, 20]})
df = df.append(df.loc[0])

first_product = (df['x'].shift(1) * df['y']).fillna(0).sum()
second_product = (df['y'].shift(1) * df['x']).fillna(0).sum()

(first_product - second_product) / 2
600


ऐसा करने का सी तरीका:

float areaForPoly(const int numVerts, const Point *verts)
{
    Point v2;
    float area = 0.0f;

    for (int i = 0; i<numVerts; i++){
        v2 = verts[(i + 1) % numVerts];
        area += verts[i].x*v2.y - verts[i].y*v2.x;
    }

    return area / 2.0f;
}

त्रिकोणों से बेहतर कार्टेसियन अंतरिक्ष में trapezoids का मिश्रण है:

area = 0;
for (i = 0; i < n; i++) {
  i1 = (i + 1) % n;
  area += (vertex[i].y + vertex[i1].y) * (vertex[i1].x - vertex[i].x) / 2.0;
}

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

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

मान लें कि आपके पास पॉइंट्स की एक सूची है जो पॉलीगॉन को क्रम में परिभाषित करती है (पॉइंट I और i + 1 पॉलीगॉन की एक पंक्ति बनाते हैं):

योग (क्रॉस उत्पाद ((बिंदु 0, बिंदु i), (बिंदु 0, बिंदु i + 1)) i = 1 से n-1 के लिए।

उस क्रॉस उत्पाद की परिमाण लें और आपके पास सतह क्षेत्र है।

यह एक अच्छा संदर्भ बिंदु लेने के बारे में चिंता किए बिना अवतल बहुभुज को संभालेगा; पॉलीगॉन के अंदर नहीं होने वाले त्रिकोण को उत्पन्न करने वाले किसी भी तीन बिंदु में एक क्रॉस उत्पाद होगा जो बहुभुज के अंदर मौजूद किसी त्रिकोण की विपरीत दिशा में इंगित करता है, इसलिए क्षेत्रों को सही तरीके से सम्मिलित किया जाता है।



बिना किसी अन्य बाधाओं के अंक का एक सेट अनिवार्य रूप से बहुभुज को परिभाषित नहीं करता है।

तो, सबसे पहले आपको यह तय करना होगा कि पॉलीगॉन इन बिंदुओं से कैसे निर्माण करे - शायद उत्तल होल? http://en.wikipedia.org/wiki/Convex_hull

फिर त्रिभुज और क्षेत्र की गणना करें। http://www.mathopenref.com/polygonirregulararea.html


मेरी झुकाव बस त्रिभुजों से टुकड़ा शुरू करना होगा। मैं नहीं देखता कि कैसे और कुछ भी बालों वाले होने से बच सकता है।

पॉलीगॉन समेत तीन अनुक्रमिक बिंदुएं लें। सुनिश्चित करें कि कोण 180 से कम है। अब आपके पास एक नया त्रिकोण है जो गणना करने में कोई समस्या नहीं होनी चाहिए, पॉलीगॉन की पॉइंट्स की सूची से मध्य बिंदु को हटाएं। तब तक दोहराएं जब तक आपके पास केवल तीन अंक शेष न हों।


यहां मानक विधि है , AFAIK। मूल रूप से प्रत्येक चरम के चारों ओर क्रॉस उत्पादों को जोड़ते हैं। त्रिभुज से बहुत आसान है।

पाइथन कोड, एक बहुभुज को (x, y) vertex निर्देशांक की सूची के रूप में दर्शाया गया है, जो अंतिम चरम से पहले तक लपेटता है:

def area(p):
    return 0.5 * abs(sum(x0*y1 - x1*y0
                         for ((x0, y0), (x1, y1)) in segments(p)))

def segments(p):
    return zip(p, p[1:] + [p[0]])

डेविड लेहवी टिप्पणी करते हैं: यह उल्लेखनीय है कि यह एल्गोरिदम क्यों काम करता है: यह कार्यों के लिए ग्रीन के प्रमेय का एक अनुप्रयोग है - और एक्स; वास्तव में एक planimeter काम करता है। अधिक विशेष रूप से:

उपरोक्त फॉर्मूला =
integral_over_perimeter(-y dx + x dy) =
integral_over_area((-(-dy)/dy+dx/dx) dy dx) =
2 Area


यह पृष्ठ सूत्र दिखाता है

इसे सरल बनाया जा सकता है:

यदि आप कुछ शर्तों को लिखते हैं और उन्हें xi सामान्य कारकों के अनुसार समूहित करते हैं, तो समानता को देखना मुश्किल नहीं होता है।

अंतिम सारांश अधिक कुशल है क्योंकि इसे 2n बजाय केवल n गुणा की आवश्यकता होती है।

def area(x, y):
    return abs(sum(x[i] * (y[i + 1] - y[i - 1]) for i in xrange(-1, len(x) - 1))) / 2.0

मैंने जो किंगटन से here इस सरलीकरण को सीखा।

यदि आपके पास NumPy है, तो यह संस्करण तेज़ है (सभी के लिए बहुत छोटे सरणी):

def area_np(x, y):        
    x = np.asanyarray(x)
    y = np.asanyarray(y)
    n = len(x)
    shift_up = np.arange(-n+1, 1)
    shift_down = np.arange(-1, n-1)    
    return (x * (y.take(shift_up) - y.take(shift_down))).sum() / 2.0






2d