全 文 ：林业 科学研 究 ,
中目标选取算法的研究
乔彦友
摘要 本文分别对点 、线及多边形的选取算法进行了研究 。 在点状图元选取中 , 以绝对距离代
替通用的平方根距离 ,提高了选取效率 。 对于线状图元的选取 , 定义 了一种运算量较小的点到曲线
的距离 ,同样提高了选取效率 。 为了提高多边形的选取效率 , 对常用的判定一个点是否为多边形内
点的 “半直线 ”方法进行了改进 , 得到 了一种运算量较小的算法 。
关键词 地理信息系统 、 目标选取 、 多边形
在基于矢量存储的地理信息系统中 , 现实世界中的实体被抽象为点 、线和多边形三种最基
本的图形要素 , 通过为三种图形要素建立数据模型并进行存储就实现了空间数据库的建立 。在
建立空间数据库的过程中 , 除了要对底图进行数字化外 ,还必须对通过数字化所得到的数字化
原图进行大量的编辑工作 , 以便空间数据库中各实体之间的空间关系满足相合性 一
的要求 。 而在对空间数据库的交互编辑过程中 , 首先要用 鼠标在屏幕上选择一个 目标实体
或图元 、图素 , 然后才能对被选定的图元进行编辑 。用光标指定一个图元后 , 如何快速地从空
间数据库中找出其对应的数据描述是一个值得重视的算法问题 。 本文将结合作者从事 开
发工作的经验分别论述点 、线和多边形三种基本图形要素选取的算法问题 。
点状 图素的选取算法
在矢量存储的 中 , 点状图素的存储形式如图 所示 。
用鼠标在屏幕上选取一个点状图素的过程是将鼠
标对准屏幕上的某个点状图素按特定的 鼠标键 , 然后
根据这点的坐标从空间数据库中找出该图元 。 设 鼠标
指 定的点 。 的坐标为 , 。 , 且 已经转换为实际存
储的坐标系下的值 。
从点状图素的存储可 以看出 , 它的选取算法 比较
图 点状 图素的存储方式 简单 , 只须找出离 。最近的点状图素即可 。 设空间数
据库 中共有 , , 个点状图素 , 其对应 的点分别为 ⋯
。 , 任意两点选取流程可由图 表示 。
上述流程结束后 , 变量 的值就是所选取的点状图素的序号值 , 在程序实现过程中 , 可采
用绝对值距离函数
, 一 , 一 。 , 一 ,
一 一 收稿 。
乔彦友助理研究员 中润林业科学研究院资源信息研究所 北京
林 业 科 学 研 究 卷
而不用平方根距离函数
’ , , 一 , , 一 。〕’ ,
, 相对于 ‘ , 的优越之处在于它不用进行乘法和开平方运算 , 能缩短运算时间 。
结束
图 点状图素选取流程图
倪 ,
‘ , 。
爪二
竺翌』
图 线状图素选取流程图
,
, ‘
阴 ‘ 二
十
结束
线状图素的选取算法
线状图素 弧段 的选取过程是用 鼠标对准弧段上的任一位置按特定的 鼠标键 , 然后根据
一定的算法在空间数据库中找出该弧段所对应的数据 。 设鼠标指定的点 。 的坐标为 。 , 。 ,
线状图素的选择原则应当是找出离点 。 最近的弧段 。
设空间数据库 中共有 。 条弧段 ,记为 , 一 , ⋯ , , 。 点 。到任一弧段 的距离函数为 汤
。 , , 用变量 记录最终所选到的弧段 的序号 , 那么线状 图元的选择流程可由上述图 所
不 。
在程序的实现过程中 , 点到弧段的距离函数分 , 算法的好坏决定了线状图素选择算法
的总体效率 。 下面简单论述它的定义及计算 。
设任意两点之 间的距离采用平方根距离
, 〔 , 一 。 , 一 。 〕”
设任一条直线段万兀所在的直线 的方程为
了 一
期 乔彦友 中目标选取算法的研究
过点 尸 。做 的垂线 , 并求得其与 的交点‘。 , 。 , 那么点 。 到线段万玉了百的距离为
。 。
了 “ 如
妥。 , 。 在兀户万上
。 , , 。 , 妥。 , 夕。 不在了牙百上
、
一、产一尸 一尸、
由于任一弧段 由一系列线段组成 , 记为不了不万, 一 , ⋯ , 一 , 因而点 。 到弧段的距离可
定为
。 , 二二二
毛苦 阴 一
。 , , ,
上述 汾尸 , 的定义比较严格 , 在编制程序时如采用它 , 每次选取弧段都要计算点 。 到所
有弧段上的所有线段的距离 , 运算效率非常低 。 在实际编制程序时可用下面的岔来代替
“ 尸。 ,丽 , 一 , 。 , 当 , , 一 占毛 。毛 , 占, 少 , 夕 一 占簇 少。镇 夕, , 夕 占其它
其中 , , , 为 点的坐标 , , 为 点的坐标 , 占为一个 比较小的正数值 , 可以取
为系统的容差值 或者它的倍数值 。 采用上式后 , 只有当点 。 离线段户丁户百比较近
时 , 才计算它们之间的距离 ,这就大大地减少了求点到线段的距离的次数 ,提高了运算效率 。
多边形的选取 算法
多边形的选取过程是用 鼠标对准多边形内任一点按某一特定 鼠标键 , 然后根据一定算法
从空间数据库中找出这一多边形 。
设 。 , 。为鼠标指定的多边形 内的任一点 , 函数 。 , 用于判定 。 是否
为多边形 的内点 , 空间数据库 中共有 , 个多边形 , 记为 一 , ⋯ , 。 那么多边形的
选取流程就是依次对各个 多边形调 用函数 , 判断 尸 。是否为其内点 , 直至找到某个
多边形 , 使 。是其内点时为止 。
可以看出 , 上述流程的核心就是 判断点 。 是否为一个多边形的内点的函数
的效率 的问题 。 现在普遍采用的算法是铅锤线法 , 它的基本原理是如果要判断 。是否为一个
多边形 的内点 , 可先在多边形外找一点 , 求线段牙涵与多边形的交点 的个数 , 如果交点数为
奇数则 。 是多边形的内点 , 如果交点数为偶数 , 则 。 不是多边形的内点 。 特别地 , 可取 的
纵坐标与 。的相同 , 的横坐标为正无穷大 , 那么问题就化为求由 。 向右延伸的射线 。 与
多边形的交点数 目的问题 。
由于多边形是 由一系列线段组成 , 因而求 。 与多边形的交点数等价于求 。 与各线段的交
点数的总和 。 又 由于一个多边形一般 由一个外围多边形和其内的若干岛多边形组成 , 求 。 与
这个多边形的交点数等价于分别求 。 与外围多边形及求 。 与各个岛多边形的交点数 , 然后求
和 , 因而在以后的论述中 , 我们可以假定多边形内不存在岛。
在实现上述算法时 , 有几种极端情况需要考虑 。
第一种情况是点 。 在多边形的边界上 , 例如 尸。与多边形的一个顶点重合 , 。在多边形
的一条水平线段上或者 尸。 在多边形的一条非水平线段上 。 当这些情况出现时 , 。 不是多边形
林 业 科 学 研 究 卷
的内点 , 运算不必继续进行 。
第二种情况是 。 与多边形 的一个顶
点相交 , 如图 所示 。 该两 图中 , , ,
都为多边形的顶点 , 而 。与多边形交于顶
点 尸 。 它们的处理方法是 图 中的
点算为一个交点 , 因为过这点的两条线段
尸 及尸 在 。 的两侧 图 中的 点
算为两个交点 也可算为零个交点 , 因为
, 及P ZP 在 l。 的一侧 。 这种处理方法必
图 4 1。与多边形顶点相交的情况
须判断瓦了及户诬子是否在 l。的同一侧 , 增加了机时开销 。
第三种极端情况是 l。与多边形上的一段或数段水平线重合 , 如图 5 所示 。 它们的一种处
理算法是将水平线段户丁户百的两个端点合并为一个点 , 这时分别得到图 6(a)及 6(b ) , 这时就化
为 l。与多边形的某个顶点相交的情况了 。 这种处理算法不但要判断水平线 , 而且要重新整理
多边形的点的坐标 , 增加了额外的机时开销 。
丘一 l。
图 5 1。与 多边形 中一段水平线重合的情况 图 6 1。与多边形 中一段水平线重合时的一种解决方案
通过对铅锤线法的描述和上述几种极端情况处理方法的分析 , 我们可以设想能否设计一
种通用的算法 , 使它既能处理上述几种极端情况 , 又能克服前面处理方法所带来的缺陷 , 为此 ,
本文提出了一种统一的算法流程 。 下面就详细叙述这种流程 。
设多边形的顶点 {p , } i 一 1 , ⋯ , , , l 。 与万子苦+ 1的交点数为 m , , 那么 l。 与多边形的交点数为
艺m , 。为了描述求 m , 的流程时方便 , 我们用 “i 步结束”表示求 l。 与万子亩十 , 交点的过程的结束 , 用
“ 总结束 ”表示判断 P 。 是否为多边形内点的总过程的结束 , 那 么求 m , 的过程可以如下所述 :
( I )若 x , < x o , x 、+ 1 < x 。 , 则 m , = o , i 步结束;
( l )若 二 , - 一 x 。 , 则 尸 。 不是 内点 , 总结束;
(. )若 y , - 一y , 十 , - ~ y 。 , 且 m in( x , , x , + l ) 镇x 。镇m ax (x , , x , 十 , ) , 则 p 。 不是内点 , 总结束;
(IV )如果条件 m in (y , , y ‘+ , ) 镇y 。 和 m ax (y , , y 、+ , ) > y 。不全满足 , 那么 m ‘= o , i 步结束;
( v )如果条件 m in 勺、 , 夕, + , ) 镇夕。和 m ax勿 , , 夕‘二 , ) > 夕。 都满足 , 则求 z。与瓦万i+ , 的交点的
横坐标妥
(a)如果妄- 一x 。 , 则 p 。 不为内点 , 总结束;
(b )如果妥共x 。 , 则 m , 一 1 , i 步结束 。
上述流程是 自上而下依次进行的 , 其中(I )保证了多边形 只与 z。求交 ;( I )及 ( 皿 )很容易
地处理了 P 。是多边形 的一个顶点和在多边形的一条水平线上的情况 , ( 刊 ) 使得参与与 l。求
期 乔彦友:G IS 中目标选取算法的研究
交的线段尽可能地少;( v )中的(a) 处理 了 P 。 在多边形的一条非水平边上的情况 , ( v ) 中的
(b)则是当 l。 与线段有交点 , 且交点不与 P 。重合的情况 。
这里需特别指出的是上述流程解决了 l。与多边形交于某个顶点和 l。 与多边形的水平线
段部分重合的情况 , 消除了以前处理这两种情况的缺陷 。 例如按本算法 , 在图 4(a)中 , l 。与万瓦
交点数为 。, 与万万百的交点数为 1 , 因而 p 算为一个交点 。 在图 4(b) 中 l。与万沪的交点数为 1 , 10
与耳沪的交点数为 1 , 因而 p 算为两个交点 。 还有一种 l。 与多边形交于顶点的情况就是过这点
的两条线段在 l。下方 , 如图 7 所示 。
图 7 1。与多边形交于顶点的 另一种情 况
在图 7 中 l。 与万万,及户沪的交点数都为 0( 按上述流
程 ) , 因而 P 算为 。个 交点 , 是偶数这不会影响 P 。 内点
属性的判别 。
在 l。 与多边形 的水平线 部分重 合的情况 , 按本 流
程 , 在 图 5(a )中 , p 3 p ,与 l。的交点数为 1 ,瓦瓦与 l。 的交
点数为 。 ,万沪百与 l。 的交点数为 1 , 因而 l。与万石万万,万;子百,
兀兀的交点总数为 2 。 同样可算出图 5(b) 中 l。与了兀万;,
万1子百J 不丁二的交点总数为 1。 由于第( l )步 已经排除了 p 。 在水平线户万户万上的可能 , 因而这种算
法不影响 P 。是否在多边形内的判断 。
本算法在笔者参与开发的微机地理信息系统 PC G IS 中得到应用 , 运算效率比较高 。
参 考 文 献1 乔彦友 , 唐 守正 , 刘继 宏 , 等.微机地理信息系统 P C G Is 及其在林业资源 经营管理方面的应用.林业科学研究 , 1 9 9 1 ,
4
( 增 ):32 ~ 37.
2 田永林 , 高显连 , 李应国 .W IN G IS 的 多边形内点判别算法.林业资源管理 , 19 94 , (6 ) : 79 ~ 81 .
A l
g
o r
i t h
m
s
f
o r
O
b
j
e e
t
S
e
l
e e
t i
o n
i
n
G
I
S
Q
i
a o
Y
a
,理o u
A b s tra e t A lg o rith m s fo r th e s ele e tio n o f p o in t , l i n e a n d p o l y g o n a r e s t u d i e d r e s p e e t i v e -
l
y i
n t
h i
s
P
a
P
e r
.
I
n t
h
e s e
l
e e t i
o n o
f
a
P
o
i
n t
,
a
b
s o
l
u t e
d i
s t a n e e
b
e t w
e e n t w
o
P
o
i
n t s a r e u s e
d i
n
-
s t e a
d
o
f
t
h
e e o
m m
o n
l y
u s e
d
s
q
u a r e r o o t
d i
s t a n e e
,
a n
d h i g h
e r e
f f i
e
i
e n e
y 1
5 a e
h i
e v e
d
.
F
o r t
h
e
s e
l
e e t i
o n o
f
a
l i
n e
,
a n e
w d i
s r a n e e
b
e t w
e e n a
p
o
i
n t a n
d
a e u r v e
1
5
d
e
f i
n e
d
,
a n
d h i g h
e r e
f f i
e
i
e n e y
1
5 a
l
s o a e
h i
e v e
d
.
I
n o r
d
e r t o r a i
s e t
h
e e
f f i
e
i
e n e
y
o
f p
o
l
y g
o n s e
l
e e t i
o n
,
s o
m
e
i m p
r o v e
m
e n r s
h
a v e
b
e e n
m
a
d
e t o t
h
e “ s e m i l i n e ” m e t h o d w h ie h 1 5 u s e d t o j u d g e w h e t h e r a p o i n t 1 5 i n s id e a
p o l y g o n
,
a n
d
a n e
w
a
l g
o r
i
t
h m w h i
e
h
n e e
d
s
l
e s s e o
m p
u t a t i
o n
.
K
e
y w
o r
d
s
G I S
,
o
b j
e e t s e
l
e e t i
o n
,
p
o
l y g
o n
Q i
a o
Y
a n y o u
,
A
s s
i
s t a r : t
p
r o
f
e s s o r
( T h
e
R
e s e a r e
h I
n s t
i
t u t e o
f
Fo
r e s r
R
e s o u r e e
I
n
f
o r
m
a t
i
o n
T
e c
h
n
i q
u e s .
C ^ F 氏ijing
100091).