腾讯云

文章/答案/技术大牛

发布

社区首页 >问答首页 >对于线段数据库，查找与矩形相交的所有线段

问对于线段数据库，查找与矩形相交的所有线段
EN

Stack Overflow用户

提问于 2013-06-16 12:13:45

回答 3查看 467关注 0票数 2

给定一大组线段，如何有效地找到与矩形相交的所有线段？典型的应用程序是GIS数据库，查找当前视野内的所有道路。对于点，这可以通过将点存储在KD树中来有效地完成，但是线段的相应数据结构是什么？

如果算法考虑了线宽，这是一个额外的好处，但是零宽度算法是完全可以的。

computational-geometry

kdtree

data-structures

geometry

回答 3

Stack Overflow用户

发布于 2013-06-16 16:22:06

您可以使用段树，就像CGAL：dD Range and Segment Trees中存在的那样。该数据结构在所有维度中都可用，包括维度2。

票数 2

Stack Overflow用户

发布于 2013-06-26 19:34:33

将矩形视为一组4条线段。现在，您就有了一组n+4线段。在线段上应用扫描线算法。仅当两条直线段来自不同的集合时才执行交点。即一段来自矩形，另一段来自数据库。此外，您可以从矩形的第一个顶点开始扫描线过程，并在所有矩形线完成处理后结束。

您还可以搜索空间散列和线栅格化(用于用线数据填充空间单元格)。这可能会更快。

票数 1

Stack Overflow用户

发布于 2013-07-11 20:43:43

另一种可能的数据结构是R-tree。特别是priority R-tree将为您的运行时间提供有保证的上限，但启发式变体在实践中可能更快。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/17133213

复制

平面中判断线段与矩形是否相交

编程算法

那么关键就在于两个子算法：判断点在矩形内和判断线段相交。判断点在矩形内非常简单，就是比较点是否在矩形的四至范围就可以了;而判断线段相交可以参考《空间或平面判断两线段相交(求交点)》这篇文章。

charlee44

2021/06/21

3.1K0

POJ 1410--Intersection(判断线段和矩形相交)

编程算法

Intersection Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 16322 Accepted: 4213 Description

Enterprise_

2019/03/01

8920

POJ 3304 Segments(直线与线段相交)

编程算法

我们考虑如果所有线段的投影有重合部分，那么我们可以在重合部分上做一条垂线经过所有点

attack

2019/03/04

4180

codeforces 1366B（线段相交）

swap

You are given an array consisting of n integers a1, a2, …, an. Initially ax=1, all other elements are equal to 0.

dejavu1zz

2020/10/23

3070

计算几何之判断线段相交

两条线段都满足“另一条线段的两个端点分别位于当前线段的顺时针方向和逆时针方向”，那么这两条线段相交。

灯珑LoGin

2022/10/31

4870

计算几何之线段相交问题（平面扫描）

编程算法

求n条线段的交点，可以用抽选配对的方式来遍历所有的情况，这样子时间复杂度为O(n2).

灯珑LoGin

2022/10/31

1K0

空间或平面判断两线段相交(求交点)

编程算法

charlee44

2021/06/21

2.4K0

POJ 1066--Treasure Hunt(判断线段相交）

line minimum point pyramid state

Treasure Hunt Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 7857 Accepted: 3247 Description

Enterprise_

2019/02/20

3210

HDU 1086 计算几何判断线段相交

java

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6456 Accepted Submission(s): 3116

csxiaoyao

2019/02/18

5660

LintCode 线段树系列问题（线段树的构造，线段树的构造||，线段树的查询，线段树的查询II,线段树的修改）线段树的构造线段树的构造 II线段树的查询线段树查询 II线段树的修改

其他

线段树是一棵二叉树，他的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start和end都是整数，并按照如下的方式赋值:

desperate633

2018/08/22

5350

LintCode 线段树系列问题（线段树的构造，线段树的构造||，线段树的查询，线段树的查询II,线段树的修改）线段树的构造线段树的构造 II线段树的查询线段树查询 II线段树的修改

POJ 2653--Pick-up sticks(判断线段相交)

case input limit output sample

Pick-up sticks Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 14568 Accepted: 5510 Description

Enterprise_

2019/02/20

4000

【HDU 1542】Atlantis（线段树+离散化，矩形面积并)

编程算法

另一种方法还是线段树，这里扫描线用的是平行y轴的直线，每次增加的面积是当前扫描的竖线所在的高度区间的最后一次的x与当前x的差值乘上区间的高度。所以每次增加的不一定是一个矩形，而是多个矩形并。

饶文津

2020/06/02

3830

几何算法：判断两条线段是否相交

point 编辑器开发前端算法

一条线段两个点，可以列出一个两点式(x - x1) / (x2 - x1) = (y - y1) / (y2 - y1)），两条线段是两个两点式，这样就是二元一次方程组了，就能求出两条直线的交点。

前端西瓜哥

2023/08/18

9650

线段树模板与练习

存储递归函数数据数组

查询也是一个递归的过程，如果查询的区间已经把当前区间完全包含了，则可以返回该区间了。

timerring

2023/03/23

6190

[奇怪但有用的数据结构]线段树

数据结构二叉树编程算法

线段树是一棵二叉树，他的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start和end都是整数，并按照如下的方式赋值:

杜逸先

2018/06/20

3.9K0

【数据结构】了解线段树与操作线段树的基本方法

编程算法存储腾讯云开发者社区 java

每次将区间的长度一分为二,区间存储的左右边界 [[start,end]/[left,right]]

冷环渊

2022/03/09

4370

线段树

简单线段树过程详解 #include<iostream> //——————————>debug 了一上午才把这个程序运行的过程在脑子里有了思路 #include<string.h> //头文件就不多说了 #include<stdlib.h> #define maxsize 10000 //这个可定义其他数----------->这个主要是控制数组的大小， using namespace std; struct node { //结构

知识浅谈

2020/03/25

3720

线段树

编程算法存储二叉树

对于给定数组nums，修改nums中某个下标的值的操作记做update（index, val）,获得nums某个区间元素和的操作记做query（start，end）。

你的益达

2020/10/09

4130

树状数组、线段树与RMQ

编程算法

binary index tree 来自OI-wiki的图，我记得刘汝佳书里也有，不过那本书不在我手边

千灵域

2022/06/17

7010

线段树（模板）

编程算法

刚学了线段树，趁现在理解比较清楚，写篇博客供以后翻阅，线段树有很多应用，如求区间总和，最大值，最小值等，总之求区间问题都可以想想线段树，这里以求和为例

Here_SDUT

2022/06/29

3220

相似问题

查找与线段相交的所有切片

如何检查线段是否与矩形相交？

查找线段与方框相交的位置。

圆与线段相交

线段与圆相交

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

社区富文本编辑器全新改版！诚邀体验～

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

问对于线段数据库，查找与矩形相交的所有线段
EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

查找与线段相交的所有切片

如何检查线段是否与矩形相交？

查找线段与方框相交的位置。

圆与线段相交

线段与圆相交

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问对于线段数据库，查找与矩形相交的所有线段EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

查找与线段相交的所有切片

如何检查线段是否与矩形相交？

查找线段与方框相交的位置。

圆与线段相交

线段与圆相交

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问对于线段数据库，查找与矩形相交的所有线段
EN