cad制图初学入门 一个简单的多矩形碰撞算法，有快于N^2的方法吗？
一个简单的多矩形碰撞算法，有快于N^2的方法吗？
谢谢。
我无法理解解决问题时“碰撞”的含义。我把它理解为矩形覆盖部分重叠时的碰撞。
让我们首先来看一个简单的一维情况：一条线由若干具有给定端点坐标的线段分散而成。如何判断线段是否相交？
n*logn的算法是标记每个端点所在线段的左端点或右端点，然后按坐标对所有端点进行排序。如果线段a的左端点在线段B的左端点和右端点之间，并且线段a的右端点在线段B的左端点和右端点之外，则线段a和B相交。所以排序遍历可以解决。
补充说明：如果线段a及其左右端点位于线段B的左右端点之间，则线段a位于线段B内部，即包含关系。计算包含关系的复杂性与计算交叉关系的复杂性相同。
因此，在二元平面上，所有矩形都可以首先投影到x轴上，并且可以一维方式判断它们是否在x轴上相交。如果它们在x轴上相交，则可以判断相应矩形的投影线段是否在y轴上相交。如果X和Y轴相交，则可以确定两个矩形的碰撞。
还可以计算正方形的完全覆盖关系。
复杂性是排序n*logn、遍历n和合成n*logn。
在虫岛有更好的算法吗。
一个简单的多矩形碰撞算法，有快于N^2的方法吗？
一定有。一般来说，这类事情是根据具体情况来分析的。一般情况下，扫描线算法可以用来处理碰撞，即长、宽、高的固定分辨率扫描。在这种情况下，最严重的复杂性取决于图像的分辨率。如果用于数值处理（即仅判断矩形是否相交），则可以先将矩形存储为四个顶点的坐标，然后对坐标进行离散化。之后，扫描线路。该算法的复杂度远高于n^2算法。特别是在处理非特定数据时，如果不退化，算法速度会更快。
qt怎么检测碰撞？
1. qlabel的边界是一个规则矩形，所以判断两个qlabel是否碰撞实际上就是判断两个矩形是否相交？矩形qrect类有一个成员函数intersects，可以直接判断它是否与另一个矩形相交。
2. 要通过键盘控制qlabel，需要获取键盘事件，在键盘事件函数中移动qlabel，判断是否有碰撞。重写标签父窗口的keypressevent或keyreleaseevent函数。
3. 您可以使用图形视图框架来编写界面。使用这个框架来检测碰撞要容易得多。直接调用函数即可。
版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
