草庐IT

c++ - 减少寻找 N 线交点所花费的时间

coder 2024-02-24 原文

有 N 条线段，它们要么是水平的，要么是垂直的。现在我需要找出每条线段的交点总数和交点总数。 N 最高可达 100000。我试着检查每一对线。答案是正确的，但我需要减少它所花费的时间。

这是我的代码:

using namespace std;

typedef struct Point
{
     long long int x;
     long long int y;
} ;


bool fun(Point p0, Point p1, Point p2, Point p3)
{
    double s1_x, s1_y, s2_x, s2_y;
    s1_x = p1.x - p0.x;     s1_y = p1.y - p0.y;
    s2_x = p3.x - p2.x;     s2_y = p3.y - p2.y;

    double s, t;
    s = (-s1_y * (p0.x - p2.x) + s1_x * (p0.y - p2.y)) / (-s2_x * s1_y + s1_x * s2_y);
    t = ( s2_x * (p0.y - p2.y) - s2_y * (p0.x - p2.x)) / (-s2_x * s1_y + s1_x * s2_y);

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
    {
        return 1; // Collision detected
    }

    return 0; // No collision
}


int main()
{
     long long int n // number of line segments;

     Point p[n],q[n]; // to store end points of line segments

    for( long long int i=0;i<n;i++)
    {

// line segments is defined by 2 points P(x1,y1) and Q(x2,y2)
        p[i].x=x1;
        p[i].y=y1;
        q[i].x=x2;
        q[i].y=y2;
    }

    for( long long int i=0;i<n-1;i++)
    {
        for( long long int j=i+1;j<n;j++)
        {
            if(fun(p[i],q[i],p[j],q[j]))
               count++;
        }

    }

    return 0;
}

有人可以帮我降低这个程序的时间复杂度吗？

最佳答案

这是一个时间复杂度为 O(n log n) 的算法，它使用带有 Fenwick 树的扫掠线。

第0步:坐标重映射

对 x 坐标进行排序，并用 0..n-1 中的整数替换每个值，以保持顺序。对 y 坐标执行相同的操作。保留交集属性，同时允许下面的算法更容易实现。

第一步:平行线段

我将针对水平段描述此步骤。对垂直段重复上述操作。

按 y 坐标对水平线段进行分组。一次处理一组，为扫描线创建事件，如下所示。每个段在其较小端点处获得一个开始事件，在其较大端点处获得一个停止事件。如果您想要封闭的线段，则排序在停止之前开始。按排序顺序扫描事件，跟踪当前与扫描线相交的线段数和处理的启动事件数。一个段的平行交集数为(开始时相交的段数+停止时处理的开始事件数-开始时处理的开始事件数)。 (另请参阅 Given a set of intervals, find the interval which has the maximum number of intersections，了解我之前对此的解释。)

第二步:垂直线段

我将通过计算每个水平线段与它相交的垂直线段的数量来描述此步骤。

我们做另一种扫描线算法。这些事件是水平线段开始、垂直线段和水平线段停止，假定闭合线段按该顺序排序。我们使用 Fenwick 树来跟踪，对于每个 y 坐标，到目前为止有多少垂直线段覆盖了该 y 坐标。要处理水平起点，请从其交点计数中减去其 y 坐标的树值。要处理水平停靠点，请将其 y 坐标的树值添加到其交点计数。这意味着计数增加了差值，差值是在水平线处于事件状态时刺穿水平线的垂直线段的数量。要处理垂直线段，请使用 Fenwick 树的强大功能快速递增其较小的 y 坐标和较大的 y 坐标之间的所有值(假设闭合线段包括在内)。

如果需要，可以组合这些扫描线算法。出于说明原因，我将它们分开。

关于c++ - 减少寻找 N 线交点所花费的时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40566994/

amp43longsectionstrongc++algorithmtime-complexityline-intersection

有关c++ - 减少寻找 N 线交点所花费的时间的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby-on-rails - Ruby 检查日期时间是否为 iso8601 并保存 - 2

    我需要检查DateTime是否采用有效的ISO8601格式。喜欢:#iso8601?我检查了ruby​​是否有特定方法，但没有找到。目前我正在使用date.iso8601==date来检查这个。有什么好的方法吗？编辑解释我的环境，并改变问题的范围。因此，我的项目将使用jsapiFullCalendar，这就是我需要iso8601字符串格式的原因。我想知道更好或正确的方法是什么，以正确的格式将日期保存在数据库中，或者让ActiveRecord完成它们的工作并在我需要时间信息时对其进行操作。 最佳答案 我不太明白你的问题。我假设您想检查

  3. ruby-on-rails - 将 Ruby 中的日期/时间格式化为 YYYY-MM-DD HH :MM:SS - 2

    这个问题在这里已经有了答案:Railsformattingdate(4个答案)关闭4年前。我想格式化Time.Now函数以显示YYYY-MM-DDHH:MM:SS而不是:“2018-03-0909:47:19+0000”该函数需要放在时间中.现在功能。require‘roo’require‘roo-xls’require‘byebug’file_name=ARGV.first||“Template.xlsx”excel_file=Roo::Spreadsheet.open(“./#{file_name}“,extension::xlsx)xml=Nokogiri::XML::Build

  4. ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2

    几个月前，我读了一篇关于ruby​​gem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：

  5. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

  6. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  7. sql - 查询忽略时间戳日期的时间范围 - 2

    我正在尝试查询我的Rails数据库(Postgres)中的购买表，我想查询时间范围。例如，我想知道在所有日期的下午2点到3点之间进行了多少次购买。此表中有一个created_at列，但我不知道如何在不搜索特定日期的情况下完成此操作。我试过:Purchases.where("created_atBETWEEN?and?",Time.now-1.hour,Time.now)但这最终只会搜索今天与那些时间的日期。 最佳答案 您需要使用PostgreSQL'sdate_part/extractfunction从created_at中提取小时

  8. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  9. ruby - 在没有基准或时间的情况下用 Ruby 测量用户时间或系统时间 - 2

    因为我现在正在做一些时间测量，我想知道是否可以在不使用Benchmark类或命令行实用程序time的情况下测量用户时间或系统时间。使用Time类只显示挂钟时间，而不显示系统和用户时间，但是我正在寻找具有相同灵active的解决方案，例如time=TimeUtility.now#somecodeuser,system,real=TimeUtility.now-time原因是我有点不喜欢Benchmark，因为它不能只返回数字(编辑:我错了-它可以。请参阅下面的答案。)。当然，我可以解析输出，但感觉不对。*NIX系统的time实用程序也应该可以解决我的问题，但我想知道是否已经在Ruby中实

  10. ruby - 以毫秒为单位获取当前系统时间 - 2

    在Ruby中，以毫秒为单位获取自纪元(1970)以来的当前系统时间的正确方法是什么？我试过了Time.now.to_i，好像不是我想要的结果。我需要结果显示毫秒并且使用long类型，而不是float或double。 最佳答案 (Time.now.to_f*1000).to_iTime.now.to_f显示包含十进制数字的时间。要获得毫秒数，只需将时间乘以1000。 关于ruby-以毫秒为单位获取当前系统时间，我们在StackOverflow上找到一个类似的问题：

随机推荐