लाइन के चौराहे और पायथन में एक सर्कल खोजने का सबसे प्रभावी तरीका क्या है?

Question

मेरे पास बहुभुज है जिसमें बहुत से अंक हैं। मैं बहुभुज और एक सर्कल का चौराहे खोजना चाहता हूं। [X0, y0] और आर 0 के त्रिज्या के सर्कल केंद्र प्रदान करते हुए, मैंने सर्कल के चौकोर समीकरण को हल करने के लिए एक मोटा कार्य लिखा है और एक रेखा। लेकिन पॉलीगॉन के प्रत्येक लाइन सेगमेंट के छेड़छाड़ को एक-एक करके खोजने की दक्षता के बारे में क्या? क्या कोई और कुशल तरीका है?

मुझे पता है कि sympy पहले से ही विभिन्न ज्यामिति के चौराहे पाने के लिए सुविधा प्रदान करता है। लेकिन बाहरी लाइब्रेरी की दक्षता के बारे में क्या है, जैसे कि सिम्पी अपने स्वयं के फ़ंक्शन द्वारा गणना करने की तुलना में, यदि मैं बहुत सारे बहुभुजों से निपटना चाहता हूं?

def LineIntersectCircle(p,lsp,lep): 
# p is the circle parameter, lsp and lep is the two end of the line 
    x0,y0,r0 = p 
    x1,y1 = lsp 
    x2,y2 = esp 
    if x1 == x2: 
    if abs(r0) >= abs(x1 - x0): 
     p1 = x1, y0 - sqrt(r0**2 - (x1-x0)**2) 
     p2 = x1, y0 + sqrt(r0**2 - (x1-x0)**2) 
     inp = [p1,p2] 
     # select the points lie on the line segment 
     inp = [p for p in inp if p[1]>=min(y1,y2) and p[1]<=max(y1,y2)] 
    else: 
     inp = [] 
    else: 
    k = (y1 - y2)/(x1 - x2) 
    b0 = y1 - k*x1 
    a = k**2 + 1 
    b = 2*k*(b0 - y0) - 2*x0 
    c = (b0 - y0)**2 + x0**2 - r0**2 
    delta = b**2 - 4*a*c 
    if delta >= 0: 
     p1x = (-b - sqrt(delta))/(2*a) 
     p2x = (-b + sqrt(delta))/(2*a) 
     p1y = k*x1 + b0 
     p2y = k*x2 + b0 
     inp = [[p1x,p1y],[p2x,p2y]] 
     # select the points lie on the line segment 
     inp = [p for p in inp if p[0]>=min(x1,x2) and p[0]<=max(x1,x2)] 
    else: 
     inp = [] 
    return inp 

Answer 1

मुझे लगता है कि शायद आपका प्रश्न इस सिद्धांत के बारे में है कि सिद्धांत में इसे सबसे तेज़ तरीके से कैसे करें। लेकिन अगर आप इसे जल्दी से करना चाहते हैं, तो आपको वास्तव में कुछ ऐसा करना चाहिए जो सी/सी ++ में लिखा गया हो।

मुझे Shapely पर काफी उपयोग किया जाता है, इसलिए मैं इस पुस्तकालय के साथ ऐसा करने का उदाहरण प्रदान करूंगा। अजगर के लिए कई ज्यामिति पुस्तकालय हैं। मैं उन्हें इस उत्तर के अंत में सूचीबद्ध करूंगा।

from shapely.geometry import LineString 
from shapely.geometry import Point 

p = Point(5,5) 
c = p.buffer(3).boundary 
l = LineString([(0,0), (10, 10)]) 
i = c.intersection(l) 

print i.geoms[0].coords[0] 
(2.8786796564403576, 2.8786796564403576) 

print i.geoms[1].coords[0] 
(7.121320343559642, 7.121320343559642) 

क्या एक छोटा सा काउंटर सुडौल में सहज है कि हलकों बफर क्षेत्रों के साथ अंक के boundries हो रहा है। यही कारण है कि मुझे क्या करना p.buffer(3).boundry

इसके अलावा चौराहे i ज्यामितीय आकार की एक सूची, उन दोनों अंक इस मामले में है, इस कारण है कि मैं से i.geoms[]

उन दोनों को प्राप्त करने के लिए वहाँ another Stackoverflow question है जो चला जाता है रुचि रखने वालों के लिए इन पुस्तकालयों के बारे में विवरण में।

• SymPy
• CGAL Python bindings
• PyEuclid
• PythonOCC
• Geometry-simple

संपादित करें क्योंकि टिप्पणियाँ:

सुडौल आधारित है ओ एन जीईओएस (trac.osgeo.org/geos) जो सी ++ में बनाया गया है और जो कुछ भी आप पाइथन में मूल रूप से लिखते हैं उससे काफी तेज है। SymPy mpmath (mpmath.org) पर आधारित प्रतीत होता है जो कि पाइथन भी लगता है, लेकिन ऐसा लगता है कि इसमें काफी जटिल गणित एकीकृत है। कार्यान्वित करना कि आपको बहुत सारे काम की आवश्यकता हो सकती है, और शायद जीईओएस सी ++ कार्यान्वयन के रूप में तेज़ नहीं होगा।

Answer 2

मुझे लगता है कि सूत्र आप दो चौराहों के निर्देशांक आगे अनुकूलित नहीं किया जा सकता है खोजने के लिए इस्तेमाल करते हैं। एकमात्र सुधार (जो संख्यात्मक रूप से महत्वपूर्ण है) दो मामलों को अलग करना है: |x_2-x_1| >= |y_2-y_1| और |x_2-x1| < |y_2-y1| ताकि मात्रा k हमेशा -1 और 1 के बीच हो (आपके गणना में आपको बहुत अधिक संख्यात्मक त्रुटियां मिल सकती हैं यदि x_2-x_1 | बहुत है छोटे)। आप एक मामले को दूसरे में कम करने के लिए एक्स-एस और वाई-एस को स्वैप कर सकते हैं।

आप प्रारंभिक जांच भी कार्यान्वित कर सकते हैं: यदि दोनों अंतराल सर्कल में आंतरिक हैं तो कोई चौराहे नहीं है। अंक से सर्कल के केंद्र तक वर्ग की दूरी की गणना करके यह एक साधारण सूत्र बन जाता है जो वर्ग रूट फ़ंक्शन का उपयोग नहीं करता है। दूसरी जांच: "क्या रेखा सर्कल के बाहर है" पहले से ही आपके कोड में कार्यान्वित की गई है और डेल्टा < 0 से मेल खाती है। यदि आपके पास बहुत से छोटे सेगमेंट हैं तो इन दो चेकों को ज्यादातर मामलों में शॉर्टकट उत्तर (कोई चौराहे नहीं) देना चाहिए।

Answer 3

एक कम लागत spacial विभाजन 9 टुकड़े

में विमान विभाजित करने के लिए हो सकता है यहाँ एक भद्दा चित्र है। कल्पना कीजिए, अगर आप करेंगे, कि रेखाएं सिर्फ सर्कल को छू रही हैं।

 
    | | 
__|_|__ 
__|O|__ 
    | | 
    | | 

8 जिन क्षेत्रों में हम रुचि रखते हैं उनमें से 8 सर्कल के आसपास हैं। केंद्र में वर्ग सस्ता परीक्षण के लिए अधिक उपयोग नहीं है, लेकिन आप सर्कल के अंदर r/sqrt(2) का एक वर्ग रख सकते हैं, इसलिए यह कोनों को बस सर्कल को स्पर्श करें।

चलें लेबल क्षेत्रों

 
A |B| C 
__|_|__ 
D_|O|_E 
    | | 
F |G| H 

और केंद्र में r/sqrt(2) के वर्ग हम फोन करता हूँ J

हम केंद्र वर्ग चित्र में दिखाया गया है कि नहीं कर रहे 'में अंक के सेट कॉल करेंगे J में 0, Z

बहुभुज के प्रत्येक चरम को इसके अक्षर कोड के साथ लेबल करें।

अब हम जल्दी से देख सकते हैं

 
AA => Outside 
AB => Outside 
AC => Outside 
... 
AJ => Intersects 
BJ => Intersects 
... 
JJ => Inside 

यह एक लुकअप तालिका

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