浅谈多边形与多边形关系的判断

《浅谈多边形与多边形关系的判断》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浅谈多边形与多边形关系的判断一、区域与多边形我们这里所说的区域是指由边界形成的一个封闭的区域（闭域），区域内的点是连贯的，即内部任意两点都可以通过一条折线连接在一起。我们所说的多边形由线段依次首尾相连，组成一个封闭的区域，且线段之间除首尾相连外与其他线段没有任何连接。沿着组成多边形的线段一个方向行走，多边形所组成的封闭区域内部的点都在线段的一侧。线段两侧分别是区域内点和区域外点。二、几何分析（一）区域与区域我们比对区域，区域主要有相同、相离、相切（内切、外切）、相交、包含几种关系。表一区域与区域的关系序号类型特点备注1相

2、同组成两个区域的点是同序或反序相连的2相离区域之间没有交点，且任何一个区域的任何一个顶点都不在另外区域的边上和内部点都在对方区域外部，且边不相交。3外切两个区域的边有共同点，但是任何一个区域的顶点都不在另一个区域内部（顶点在线端上我们认为也是相切）。两个区域的边有共同点，且任何一个区域的点都不在另外一个区域内部，同时没有边相交。4相交两个区域有共有部分，且有非共有部分。两个区域的线段之间有交点；或者一个区域的顶点在另一个区域内外都有5内切两个区域的边有共同点，但是其中一个区域的顶点在另一个区域内部（顶点在线端上我们认为也

3、是相切）。6包含一个区域的所有顶点都在另外一个区域内部，且边没有相交。为了便于分析，我们设定区域都是按照顺时针方向排列顶点，即所有区域的内部都在当前边的右侧。我们首先判断区域相交的情况，区域相交必定是两个区域存在同时包含和互补包含的部分，又因为区域内部点是有边界（即线段）来分割的，在区域的相交必定是边界的相交，即是在一个区域的边界的左右两边同时出现另一个区域的边界。通过分析，我们可以发现只有以下几种情况，表二区域相交情况序号类型特点例图1普通相交组成两个区域的线段相交2顶点与边相交组成一个区域的其中一个线段的端点在组成另

4、一个区域的线段上。3顶点相交两个区域的线有共同顶点，且顶点处组成两个区域的线段是依次在交点交错分布的。4共同边相交组成两个区域的线段有共同部分，且一个区域的边界左右分布了另一个区域的边界。从表二我们可以看出，区域相交就是多边形相交，可以转换为线段与线段的关系。区域相切，我们分为内切、外切。当区域内切时，内部区域被外部区域包裹，并且内部区域与外部区域有共同点或边。当外切时，两个区域都不包含对方区域内容，但是两个区域有共同的边或点。当区域内切或外切的同时又有相交部分时，我们认为两个区域是相交的。表三区域内、外切序号类型条件一

5、条件二条件三例图1内切当A、B区域没有相交部分时，如果A区域和B区域有共同的顶点或共同边或一个区域的顶点在另一个区域边上A区域另一部分顶点在B区域内部B区域另一部顶点在A区域外部，2如A区域所有顶点都在B区域边上或顶点，B区域另一部顶点在A区域外部当A区域存在内部点也在B区域内部时，两区域内切3外切当A区域存在内部点不在B区域内部时4A区域另一部端点在B区域外部B区域另一部端点在A区域外部当一个区域的所有顶点在另一个区域边（端点）上时，我们无法利用区域具有线段和顶点之间的关系来判断两个区域是内切或外切。因为一个区域所有端

6、点在另一个区域上，所以一个区域必是被另一个区域包围（外切）或包裹（内切），如果被包围（被包裹）的区域的任何一点在外部区域内，说明两个区域有共同内部点，则两个区域必是内切，否则两个区域必是外切。我们需要从被包围（被包裹）的区域内找到一点。我们可以利用一条通过该区域最大横轴值和最小横轴值中间点的直线与该区域所有边（线段）的交点，按照交点的纵轴值从大（小）到小（大）依次排序，然后依序选择点与点之间的中间值，则该中间值集与横轴中间点组成的点集必存在一个该区域内部的点（即使该过中间点直线经过了该区域的一条是垂直横轴的边，该结论也是

7、成立的），找到这个点就可以与外部区域进行判断，以确定是外切还是内切。通过以上分析，我们可以知道区域与区域的关系，我们可以利用线段与线段、点与区域的关系来判断。（二）线段与线段我们将线段与线段的关系分为五种，相同、相交、相连、和相切、相离。相同即两条线段有共同的端点。相交即两个线段之间有交点，但交点不在两个线段的共同端点。相连即两条线段通过端点首尾相连。相切，我们认为一个线段的端点在另外一个线段的上，且在端点之间。相离即两条线段之间没有任何共同的部分。我们利用线段之间的关系来判断区域之间的关系时，只是利用线段是否相交这一特

8、性，区域相切我们是利用点与区域之间的关系来判断的，所以，这里我们只讨论线段与线段相交如何判断。判断线段是否相交，有许多方法，在程序设计中，我们一般不采用除法算法，避免溢出，在这里我们选取容易理解并且执行效率相等较高的向量叉积判断法。我们认为两条线段是有向的线段即向量。向量的叉积是以两条向量为邻边的平行四边形的面积。由