草庐IT

c++ - 检查两条三次贝塞尔曲线是否相交

coder 2023-05-02 原文

对于个人项目，我需要确定两条三次贝塞尔曲线是否相交。我不需要知道在哪里:我只需要知道他们是否这样做。不过，我需要尽快完成。

我一直在搜寻这个地方，并找到了一些资源。大多数情况下，有 this question here有一个有希望的答案。

所以在我弄清楚 Sylvester matrix 是什么之后, 什么是 determinant , 什么是 resultant和 why it's useful ，我想我知道解决方案是如何工作的。然而，现实有所不同，而且效果并不好。

乱七八糟

我使用图形计算器绘制了两条相交的贝塞尔样条曲线(我们将其称为 B0 和 B1)。它们的坐标如下(P0, P1, P2, P3):

(1, 1) (2, 4) (3, 4) (4, 3)
(3, 5) (3, 6) (0, 1) (3, 1)

结果如下，B0是“水平”曲线，B1是另一条:

按照上述问题最高投票答案的指示，我将 B0 减去 B1。它给我留下了两个方程(X 轴和 Y 轴)，根据我的计算器，它们是:

x = 9t^3 - 9t^2 - 3t + 2
y = 9t^3 - 9t^2 - 6t + 4

西尔维斯特矩阵

据此，我构建了以下 Sylvester 矩阵:

9  -9  -3   2   0   0
0   9  -9  -3   2   0
0   0   9  -9  -3   2
9  -9  -6   4   0   0
0   9  -9  -6   4   0
0   0   9  -9  -6   4

之后，我创建了一个 C++ 函数来使用 Laplace expansion 计算矩阵的行列式。 :

template<int size>
float determinant(float* matrix)
{
    float total = 0;
    float sign = 1;
    float temporaryMatrix[(size - 1) * (size - 1)];
    for (int i = 0; i < size; i++)
    {
        if (matrix[i] != 0)
        {
            for (int j = 1; j < size; j++)
            {
                float* targetOffset = temporaryMatrix + (j - 1) * (size - 1);
                float* sourceOffset = matrix + j * size;
                int firstCopySize = i * sizeof *matrix;
                int secondCopySize = (size - i - 1) * sizeof *matrix;
                memcpy(targetOffset, sourceOffset, firstCopySize);
                memcpy(targetOffset + i, sourceOffset + i + 1, secondCopySize);
            }
            float subdeterminant = determinant<size - 1>(temporaryMatrix);
            total += matrix[i] * subdeterminant * sign;
        }
        sign *= -1;
    }
    return total;
}

template<>
float determinant<1>(float* matrix)
{
    return matrix[0];
}

它似乎在相对较小的矩阵(2x2、3x3 和 4x4)上工作得很好，所以我希望它也能在 6x6 矩阵上工作。但是我没有进行广泛的测试，它有可能坏了。

问题

如果我正确理解另一个问题的答案，行列式应该是 0，因为曲线相交。但是，为我的程序提供我上面制作的 Sylvester 矩阵，它是 -2916。

这是我的错误还是他们的错误？找出两条三次贝塞尔曲线是否相交的正确方法是什么？

最佳答案

贝塞尔曲线的交点由(非常酷的)Asymptote 完成 vector 图形语言:寻找 intersect() here .

虽然他们没有解释他们在那里实际使用的算法，只是说它来自 p。 “The Metafont Book”的第 137 页，它的关键似乎是贝塞尔曲线的两个重要属性(尽管我现在找不到该页面，但该网站的其他地方对此进行了解释):

  • 贝塞尔曲线始终包含在由其 4 个控制点定义的边界框内
  • Bezier 曲线总是可以在任意 t 值处 segmentation 为 2 个 sub-Bezier 曲线

有了这两个属性和一个相交多边形的算法，你可以递归到任意精度:

bezInt(B1, B2):

  1. bbox(B1) 是否与 bbox(B2) 相交？
    • 否:返回 false。
    • 是:继续。
  2. area(bbox(B1)) + area(bbox(B2)) 是不是阈值？
    • 是:返回 true。
    • 否:继续。
  3. 在 t = 0.5
    4. 处将 B1 拆分为 B1a 和 B1b
  4. 在 t = 0.5
    5. 处将 B2 拆分为 B2a 和 B2b
  5. 返回 bezInt(B1a, B2a) || bezInt(B1a, B2b) || bezInt(B1b, B2a) || bezInt(B1b, B2b).

如果曲线不相交，这会很快——这是通常的情况吗？

[编辑] 看起来将贝塞尔曲线一分为二的算法称为 de Casteljau's algorithm .

关于c++ - 检查两条三次贝塞尔曲线是否相交，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4039229/

贝塞贝塞尔subc++intersectionbezier

有关c++ - 检查两条三次贝塞尔曲线是否相交的更多相关文章

  1. ruby-on-rails - 如何验证 update_all 是否实际在 Rails 中更新 - 2

    给定这段代码defcreate@upgrades=User.update_all(["role=?","upgraded"],:id=>params[:upgrade])redirect_toadmin_upgrades_path,:notice=>"Successfullyupgradeduser."end我如何在该操作中实际验证它们是否已保存或未重定向到适当的页面和消息？ 最佳答案 在Rails3中，update_all不返回任何有意义的信息，除了已更新的记录数(这可能取决于您的DBMS是否返回该信息)。http://ar.ru

  2. ruby - 检查 "command"的输出应该包含 NilClass 的意外崩溃 - 2

    为了将Cucumber用于命令行脚本，我按照提供的说明安装了arubagem。它在我的Gemfile中，我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作，我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了，但失败的原因是错误的:@announceScenario:Testingcucumber/ar

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

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

  4. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  5. ruby - 检查方法参数的类型 - 2

    我不确定传递给方法的对象的类型是否正确。我可能会将一个字符串传递给一个只能处理整数的函数。某种运行时保证怎么样？我看不到比以下更好的选择:defsomeFixNumMangler(input)raise"wrongtype:integerrequired"unlessinput.class==FixNumother_stuffend有更好的选择吗？ 最佳答案 使用Kernel#Integer在使用之前转换输入的方法。当无法以任何合理的方式将输入转换为整数时，它将引发ArgumentError。defmy_method(number)

  6. ruby - 检查字符串是否包含散列中的任何键并返回它包含的键的值 - 2

    我有一个包含多个键的散列和一个字符串，该字符串不包含散列中的任何键或包含一个键。h={"k1"=>"v1","k2"=>"v2","k3"=>"v3"}s="thisisanexamplestringthatmightoccurwithakeysomewhereinthestringk1(withspecialcharacterslike(^&*$#@!^&&*))"检查s是否包含h中的任何键的最佳方法是什么，如果包含，则返回它包含的键的值？例如，对于上面的h和s的例子，输出应该是v1。编辑:只有字符串是用户定义的。哈希将始终相同。 最佳答案

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

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

  8. ruby - 检查日期是否在过去 7 天内 - 2

    我的日期格式如下:"%d-%m-%Y"(例如，今天的日期为07-09-2015)，我想看看是不是在过去的七天内。谁能推荐一种方法？ 最佳答案 你可以这样做:require"date"Date.today-7 关于ruby-检查日期是否在过去7天内，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/32438063/

  9. ruby - 如何验证 IO.copy_stream 是否成功 - 2

    这里有一个很好的答案解释了如何在Ruby中下载文件而不将其加载到内存中:https://stackoverflow.com/a/29743394/4852737require'open-uri'download=open('http://example.com/image.png')IO.copy_stream(download,'~/image.png')我如何验证下载文件的IO.copy_stream调用是否真的成功——这意味着下载的文件与我打算下载的文件完全相同，而不是下载一半的损坏文件？documentation说IO.copy_stream返回它复制的字节数，但是当我还没有下

  10. ruby - 是否可以覆盖 gemfile 进行本地开发？ - 2

    我们的git存储库中目前有一个Gemfile。但是，有一个gem我只在我的环境中本地使用(我的团队不使用它)。为了使用它，我必须将它添加到我们的Gemfile中，但每次我checkout到我们的master/dev主分支时，由于与跟踪的gemfile冲突，我必须删除它。我想要的是类似Gemfile.local的东西，它将继承从Gemfile导入的gems，但也允许在那里导入新的gems以供使用只有我的机器。此文件将在.gitignore中被忽略。这可能吗？ 最佳答案 设置BUNDLE_GEMFILE环境变量:BUNDLE_GEMFI

随机推荐