您可以为此使用Bentley–Ottmann 算法。给定一组个交叉点条线段时间和空间中的所有交叉点。在的情况下（即具有适当上限的情况）算法相比，这可以节省时间比较所有段。$n$$k$$O((n+k)\log n)$$O(n)$$k=o(\frac{n^2}{\log n})$$k$$O(n^2)$

更一般地，可以使用多种扫描线算法中的任何一种来解决这个问题。

因此，诀窍是每次涉及交叉路口时，在评分哈希表中增加分段的值。

用 CGAL 摆弄几个小时并没有发现明显的方法来做到这一点，并且由于线路端点处的浮点问题，其他实现产生了不正确的答案。尽管如此，这是解决该问题的计算效率最高的方法。

我已经复制了我在下面构建 CGAL 实现的尝试，并在适当的位置编辑了注释的代码：

//Compile with: g++ -g 23222-line-with-most-intersections.cpp -lCGAL -lgmp -lmpfr

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Surface_sweep_2.h>
#include <CGAL/Surface_sweep_2_algorithms.h>
//#include <CGAL/Sweep_line_2.h>
#include <CGAL/Surface_sweep_2/Default_visitor.h>
#include <CGAL/Surface_sweep_2/Surface_sweep_2_utils.h>
#include <list>
#include <vector>

typedef CGAL::Exact_predicates_exact_constructions_kernel       Kernel;
typedef Kernel::Point_2                                         Point_2;
typedef CGAL::Arr_segment_traits_2<Kernel>                      Traits_2;
typedef Traits_2::Curve_2                                       Segment_2;


namespace CGAL {
namespace Surface_sweep_2 {

template <typename GeometryTraits_2, typename OutputIterator,
          typename Allocator_ = CGAL_ALLOCATOR(int)>
class IntersectionCounter :
  public Default_visitor<IntersectionCounter<GeometryTraits_2,
                                                      OutputIterator,
                                                     Allocator_>,
                         GeometryTraits_2, Allocator_>
{
public:
  typedef GeometryTraits_2                              Geometry_traits_2;
  typedef OutputIterator                                Output_iterator;
  typedef Allocator_                                    Allocator;

private:
  typedef Geometry_traits_2                             Gt2;
  typedef IntersectionCounter<Gt2, Output_iterator, Allocator>
                                                        Self;
  typedef Default_visitor<Self, Gt2, Allocator>         Base;

public:
  typedef typename Base::Event                          Event;
  typedef typename Base::Subcurve                       Subcurve;

  typedef typename Subcurve::Status_line_iterator       Status_line_iterator;

  typedef typename Gt2::X_monotone_curve_2              X_monotone_curve_2;
  typedef typename Gt2::Point_2                         Point_2;

  typedef typename Base::Surface_sweep_2                Surface_sweep_2;

protected:
  Output_iterator m_out;                 // The output points.

public:
  IntersectionCounter(Output_iterator out) :
    m_out(out)
  {}

  template <typename CurveIterator>
  void sweep(CurveIterator begin, CurveIterator end)
  {
    std::vector<X_monotone_curve_2> curves_vec;
    std::vector<Point_2> points_vec;

    curves_vec.reserve(std::distance(begin,end));
    make_x_monotone(begin, end,
                    std::back_inserter(curves_vec),
                    std::back_inserter(points_vec),
                    this->traits());

    //Original curves get converted into x-monotone curves here, but, since they
    //are segments, their ordering and data appears to be unaltered
    std::cout<<"x-monotone curves\n";
    for(auto &x: curves_vec)
      std::cout<<x<<" "<<(&x)<<std::endl;
    std::cout<<"x-monotone points\n";
    for(auto &x: points_vec)
      std::cout<<x<<std::endl;

    //Perform the sweep
    Surface_sweep_2* sl = this->surface_sweep();
    sl->sweep(curves_vec.begin(), curves_vec.end(),
              points_vec.begin(), points_vec.end());
  }

  bool after_handle_event(Event* event,
                          Status_line_iterator /* iter */,
                          bool /* flag */)
  {
    //TODO: Magic should happen here
    if ((
         event->is_intersection() ||
         event->is_weak_intersection()) && event->is_closed())
    {
      *m_out = event->point();
      ++m_out;
    }
    return true;
  }

  Output_iterator output_iterator() { return m_out; }
};

} // namespace Surface_sweep_2

namespace Ss2 = Surface_sweep_2;



template <typename CurveInputIterator, typename OutputIterator, typename Traits>
OutputIterator CountIntersections(
  CurveInputIterator curves_begin,
  CurveInputIterator curves_end,
  OutputIterator points,
  Traits &tr
){
  // Define the surface-sweep types:
  typedef Ss2::IntersectionCounter<Traits, OutputIterator> Visitor;
  typedef Ss2::Surface_sweep_2<Visitor>                    Surface_sweep;

  // Perform the sweep and obtain the intersection points.
  Visitor visitor(points);
  Surface_sweep surface_sweep(&tr, &visitor);
  visitor.sweep(curves_begin, curves_end);

  return visitor.output_iterator();
}



template <typename CurveInputIterator, typename OutputIterator>
OutputIterator CountIntersections(
  CurveInputIterator curves_begin,
  CurveInputIterator curves_end,
  OutputIterator points
){
  typedef typename std::iterator_traits<CurveInputIterator>::value_type  Curve;
  typename Default_arr_traits<Curve>::Traits   traits;
  return CountIntersections(curves_begin, curves_end, points, traits);
}


} // namespace CGAL



int main(){
  //Points as extracted from https://scicomp.stackexchange.com/q/23222/17088
  const std::vector<Point_2> pts = {
    Point_2( 57,931),
    Point_2(447,699),
    Point_2(899,748),
    Point_2(863,137),
    Point_2(530, 67),
    Point_2(142,282)
  };

  //Points are fully connected
  std::vector<Segment_2> segments;
  for(int i=0;  i<pts.size();i++)
  for(int j=i+1;j<pts.size();j++){
    segments.emplace_back(pts[i],pts[j]);
    std::cout<<pts[i]<<"\n"<<pts[j]<<"\n\n";
  }

  // Compute all intersection points.
  std::list<Point_2> ipts;
  CGAL::CountIntersections(segments.begin(), segments.end(), std::back_inserter(ipts));

  for(const auto &x: segments)
    std::cout<<(&x)<<std::endl;

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

这个问题的答案取决于你考虑的假设。如果一个或多个点是共线的，或者如果两个以上的线段在一个点相交，那么事情可能会变得更加复杂。

因此，我将假设没有三点共线且没有三段相交的简单配置。那么一个线段相交的点数是其中表示给定线段上的点数。由于应该给出点的总数，它是固定的，所以当和尽可能接近的最大值。顶点上的双循环应该会给你正确的答案。$L \times R$$L$$R$$R+L+2$$L\times R$$R$$L$

（我确信可能存在其他更优化的算法）

我的启发式方法是，交叉点最多的线将是凸包上连接点的线。您可以使用旋转卡尺算法的变体并测试船体上对映点之间的线。交叉点的数量取决于对映对“之间”的点。确切的数字取决于连接对映线对的线的每一侧有多少点。一侧的点数乘以另一侧的点数决定了可能的最大交叉点数。确切的数字可能会更少，因为多条线可能会在同一个地方相交。因此，将需要实际评估，但这种基本启发式方法可以缩小要检查的行数。

在给定的示例中，线 AD 基本上是对映点。由于点 B 和 C 在一侧，而点 E 和 F 在另一侧，因此它们之间有 2 x 2 = 4 条线，因此最多有 4 个交点（与图表一致）。如果 B 在 AD 的另一边，那么两边各有 3 个和 1 个点，BF 和 BE 不会与 AD 相交，但 BC 会留下 3 个相交。交点 Q 和 R 彼此靠近，即使点不共线 Q 和 R 也可能重合，导致交点少于此启发式给出的最大值。如果 3 个或更多点共线，则交叉点也将少于最大值。

您只需获取每个线段，然后查看其他线段是否相交。这是针对每个单独的线段计算的。相交最多的线段就是您的线段。$n\choose 2$

^ 上面的部分很简单......这就像这是某人的笑话。无论如何...

现在，查看是否发生交叉点的方法是更具技术性的部分。我不精通计算机图形学，所以我不会立即确切地知道最好的方法。