मौजूदा बेंटले-ओटमैन एल्गोरिदम कार्यान्वयन

Question

बेंटले-ओटोमैन एल्गोरिदम एक रेखा खंडों के एक सेट में सभी क्रॉसिंग पाता है। एक प्रसिद्ध और महत्वपूर्ण एल्गोरिदम के लिए, यह बहुत अजीब लगता है कि बेंटले-ओटमैन एल्गोरिदम का एक सी ++ (या नेट) कार्यान्वयन - कार्यान्वयन जो सभी अपरिवर्तित मामलों को संभाल सकता है (यानी, व्यापक रेखा और संख्या पर विशेष धारणा नहीं चौराहे बिंदु और इतने पर) - बस उपलब्ध नहीं है। एकमात्र कोड जो मुझे मिल सकता है वह here है, लेकिन ऐसा लगता है कि यह the generalized case को संभालने में प्रतीत नहीं होता है।

बेंटले-Ottmann एल्गोरिथ्म पहले से ही इस तरह के बूस्ट या LEDA रूप में किसी भी अच्छी तरह से परीक्षण किया पुस्तकालय में लागू किया, है? यदि हां, तो क्या इसका संदर्भ हो सकता है?

Answer 1

CGAL बेंटले-Ottmann, O((n + k)*log(n)) रूप में एक ही जटिलता के साथ वहाँ में कुछ जहां n खंडों और k की संख्या है है चौराहों की संख्या (यकीन नहीं जो एल्गोरिथ्म वे प्रयोग किया जाता):

//! \file examples/Arrangement_on_surface_2/sweep_line.cpp 
// Computing intersection points among curves using the sweep line. 

#include <CGAL/Cartesian.h> 
#include <CGAL/MP_Float.h> 
#include <CGAL/Quotient.h> 
#include <CGAL/Arr_segment_traits_2.h> 
#include <CGAL/Sweep_line_2_algorithms.h> 
#include <list> 

typedef CGAL::Quotient<CGAL::MP_Float>     NT; 
typedef CGAL::Cartesian<NT>        Kernel; 
typedef Kernel::Point_2         Point_2; 
typedef CGAL::Arr_segment_traits_2<Kernel>    Traits_2; 
typedef Traits_2::Curve_2        Segment_2; 

int main() 
{ 
    // Construct the input segments. 
    Segment_2 segments[] = {Segment_2 (Point_2 (1, 5), Point_2 (8, 5)), 
          Segment_2 (Point_2 (1, 1), Point_2 (8, 8)), 
          Segment_2 (Point_2 (3, 1), Point_2 (3, 8)), 
          Segment_2 (Point_2 (8, 5), Point_2 (8, 8))}; 

    // Compute all intersection points. 
    std::list<Point_2>  pts; 

    CGAL::compute_intersection_points (segments, segments + 4, 
            std::back_inserter (pts)); 

    // Print the result. 
    std::cout << "Found " << pts.size() << " intersection points: " << std::endl; 
    std::copy (pts.begin(), pts.end(), 
      std::ostream_iterator<Point_2>(std::cout, "\n")); 

    // Compute the non-intersecting sub-segments induced by the input segments. 
    std::list<Segment_2> sub_segs; 

    CGAL::compute_subcurves(segments, segments + 4, std::back_inserter(sub_segs)); 

    std::cout << "Found " << sub_segs.size() 
      << " interior-disjoint sub-segments." << std::endl; 

    CGAL_assertion (CGAL::do_curves_intersect (segments, segments + 4)); 

    return 0; 
} 

- - http://doc.cgal.org/latest/Sweep_line_2/index.html

क्षमा करें, एक/(थोड़ा) तेज एल्गोरिदम का संदर्भ नहीं मिल रहा है।

Answer 2

अपनी टिप्पणी में सुझाव के रूप में, यहाँ एक जवाब है:

CGAL Bently-Ottmann एल्गोरिथ्म के लिए एक कार्यान्वयन है, तो आप के मैनुअल में Sweep line 2 खंड में इसके बारे में अधिक जानकारी प्राप्त कर सकते हैं।

@Bart पहले से ही कार्यान्वयन उजागर की अतिरिक्त प्रयास किया था।

Answer 3

http://geomalgorithms.com/a09-_intersect-3.html में बेंटले-ओटमैन और शामोस-होई एल्गोरिदम और उनके रिश्ते की चर्चा है। यह बाइनरी पेड़ों के आधार पर एक सी ++ कार्यान्वयन के साथ समाप्त होता है। दिलचस्प संदर्भ सामग्री यदि आप कागल या बूस्ट से लिंक नहीं करना चाहते हैं।

Answer 4

अपने आप को इस के लिए चारों ओर देख रही है और कुछ भी मैं लेने के लिए और अपने खुद के परियोजना के लिए इस्तेमाल कर सकते हैं नहीं मिल के बाद - , (CGAL के संभावित अपवाद के साथ, लेकिन यह इस एक समारोह के लिए शामिल करने के लिए काफी बड़ा पुस्तकालय है) मैंने Python3 में अपना खुद का संदर्भ कार्यान्वयन लिखने का निर्णय लिया।

यह http://github.com/bkiers/CompGeom, पर आधारित है लेकिन इसे अन्य भाषाओं में पोर्ट करने के लिए अपेक्षाकृत आसान बनाने के लिए लिखा गया है (bug with the library भी हल करता है)।

इसकी एक फ़ाइल और जटिल आकार के साथ काम करने के लिए परीक्षण किया गया।

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

---

स्रोत फ़ाइल देखें:

https://github.com/ideasman42/isect_segments-bentley_ottmann

---

उदाहरण परिणाम: (14,880 क्षेत्रों से 73002 चौराहों)।