Implementación del algoritmo Bentley-Ottmann existente

Question

El algoritmo Bentley-Otomano encuentra todos los cruces en un conjunto de segmentos de línea. Para un algoritmo bien conocido e importante, parece bastante extraño que una implementación en C++ (o .Net) del algoritmo Bentley-Ottmann - la implementación que puede manejar todos los casos degenerados (es decir, no suposición especial en la línea de barrido y el número del punto de intersección, etc.) - simplemente no está disponible. El único código que puedo encontrar es here, pero no parece manejar the generalized case.

¿Algún algoritmo de Bentley-Ottmann ya se ha implementado en cualquier biblioteca probada, como Boost o LEDA? En caso afirmativo, ¿puedo tener la referencia?

Answer 1

CGAL tiene algo allí con la misma complejidad que Bentley-Ottmann, O((n + k)*log(n)) donde n es el número de segmentos y k es el número de intersecciones (no sé qué algoritmo que utilizan):

//! \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

Disculpe, no se puede encontrar la referencia a un algoritmo (ligeramente) más rápido.

Answer 2

Como se sugiere en su comentario, aquí está la respuesta:

CGAL tiene una aplicación para el algoritmo Bently-Ottmann, se puede encontrar más sobre esto en la sección Sweep line 2 en el manual.

@Bart ya se hizo el esfuerzo extra de la exposición de la aplicación.

Answer 3

http://geomalgorithms.com/a09-_intersect-3.html tiene una discusión de los algoritmos de Bentley-Ottmann y Shamos-Hoey y su relación. Termina con una implementación de C++ basada en árboles binarios. Material de referencia interesante si no desea vincular a Cgal o impulsar.

Answer 4

Después de mirar por esto mismo y no encontrar nada que pudiera tomar y utilizar para mi propio proyecto - (con la posible excepción de CGAL, sin embargo, esto es una gran biblioteca bastante para incluir a ésta función), Decidí escribir mi propia implementación referencia en Python3.

Se basa en http://github.com/bkiers/CompGeom, pero está escrito para que sea relativamente fácil portarlo a otros idiomas (también resuelve un bug with the library).

Es un archivo único y probado para trabajar con formas complejas.

En algún momento tengo la intención de llevar esto a un lenguaje compilado, pero por ahora estoy usando esto como un caso de prueba para asegurar que funciona como se esperaba. resultado

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

---

Ejemplo::

---

Para el archivo fuente See (73002 intersecciones de 14880 segmentos).