精华内容
下载资源
问答
  • 多边形重叠计算

    千次阅读 2018-11-29 23:00:05
    两个凸多边形重叠问题就是对两个凸多边形求相交部分的问题。约定凸多边形指它的边界和内部,凸多边形仍用顶点坐标的逆时针方向序列确定。 设给出的两个凸多边形 P 和 Q 的顶点序列分别是 P1,P2,…,PL 和 Q1,Q2,…...

    前言

    两个凸多边形的重叠问题就是对两个凸多边形求相交部分的问题。约定凸多边形指它的边界和内部,凸多边形仍用顶点坐标的逆时针方向序列确定。

    设给出的两个凸多边形 P 和 Q 的顶点序列分别是 P1,P2,…,PL 和 Q1,Q2,…,Qm。

    假设 P 的边界上不包含 Q 的顶点 ,Q 的边界也不包含 P 的顶点。有两个问题需要解决:

    1. 如何有次序地求出各边的所有交点 ,
    2. 如何排列求出的交点和原凸多边形的顶点 , 形成新的凸多边形的顶点序列。

    求交点

    为了有次序地求出交点 , 可以在两个多边形边上交替地前进,原则是在哪个多边形的边上可能有交点就等待 , 在另一个多边形的边上前进。

    前进的原则可以自己随便定义,但是得满足以下两个要求(后面会解释):

    1. 两个多边形向前走的机会相同
    2. 所有情况都要覆盖

    初始从 对边 P0P1 Q0Q1P_0P_1 与 Q_0Q_1 的求交 开始 , 注意所有求交是线段的求交。这里规定了 P0=PL,Q0=QmP_0=P_L,Q_0=Q_m

    设已经算得 Pi1Pi Qj1QjP_{i-1}P_i 和 Q_{j-1}Q_j 的交点

    1. 依可能性判定接下去计算的是 PiPi+1 Qj1QjP_iP_{i+1} 与 Q_{j-1}Q_j 的交点还是 Pi1Pi QjQj+1P_{i-1}P_i 和 Q_jQ_{j+1} 的交点
      如果是算第一个,就是 P 多边形前进。算第二个就是 Q 多边形前进。
    2. 此外还需考虑 Pi QjP_i 和 Q_j 之间的夹角是否大于 180 度

    强调:初始从对边 P0P1 Q0Q1P_0P_1 与 Q_0Q_1 的求交开始 , 注意所有求交是线段的求交。

    前进情况

    Pi1Pi Qj1QjP_{i-1}P_i 和 Q_{j-1}Q_j 的相对位置总共有 8 种,分别如下:

    在这里插入图片描述
    上图中对于第一行的四种情况可分为一类,第二行的四种情况就是将第一行的 P Q 两条线段换了下位置。

    记忆第一行的四种情况可以采取以下方式:

    1. 将 “短的” Pi1Pi Qj1QjP_{i-1}P_i 和 Q_{j-1}Q_j 看作 0,“长的” 看作 1
    2. 这样可以上述四种情况可以分别记成 00 01 10 11 形式

    对于 P Q 线段的相对位置总共就 8 种情况,对于选哪个前进我们刚才说了两个原则:

    1. 两个多边形向前走的机会相同。在这 8 种情况中我们不能定义成 5 种是 P 前进,3 种是 Q 前进。前进方案是任意定义的。图中是一种定义方案,概率均为 1/2。而我们也可以定义成第一行全部是 P 前进,第二行全部是 Q 前进。区别是在编程的实现不同。
    2. 所有情况都要覆盖。不能遗漏某种情况,这里是对编程的时候说的。

    Pi1Pi Qj1QjP_{i-1}P_i 和 Q_{j-1}Q_j 夹角

    在上图中我们不难发现,对于第一行的四种情况单纯只按 PiQi Pi1PiQi1QiP_i Q_i 与 P_{i-1}P_i Q_{i-1}Q_i 的相对位置来划分的话,是无法与第二行的四种情况区分开来的。比如 情形(1) 和 情形(8)。

    在这里插入图片描述此图中的 情形 8 和上图中的 情形 8 都是一种类型,要注意辨别。

    此时我们就要利用 Pi1Pi×Qi1QiP_{i-1}P_i×Q_{i-1}Q_i(矢量叉乘)的 z 分量(用右手定则判断方向)来判断。

    • 如果该分量大于等于 0,则是前四种情形
    • 否则是后四种情形

    伪代码

    按照第一张图约定的前进方法,我们可以写出如下伪代码。

    /* P、Q为多边形顶点数组,l、m为顶点个数*/
    void Advance(PONIT P[],int l,POINT Q[],int m){  
    	int s;
    	s = vector3(P,Q,i,j); //s 置成 PiPi-1 与 QjQj-1 的叉乘的 z 值; vector3 是 unity 的一个 API
    	if (s >= 0){
    		if((left(P,i,Q,j) && left(Q,j,P,i)) || (right(P,i,Q,j) && left(Q,j,P,i))){ 
    			if (i < l) i++; 
    			else i = 1;
    		}else {
    			if(j < m) j++; 
    			else j = 1;
    		}
    	}else{
    		if((right(P,i,Q,j) && left(Q,j,P,i)) || (right(P,i,Q,j) && right(Q,j,P,i))){ 
    			if (i<l) i++; 
    			else i = 1;
    		} else{
    			if(j < m) j++; 
    			else j = 1;
    		}
    	}
    }
    

    排列交点和顶点

    为了正确排列求出的交点并加入原两个凸多边形部分顶点以形成相交的凸多边形,可以在每求出一个交点时进行一次输出。

    求出的第一个交点可做一下记录,如果在以后交替前进求交点的过程中再次求出与第一次求得相同的交点,就知道整个求交过程已经结束了。

    求得的交点不是第一个时,为形成交得凸多边形顶点序列,要区分边 Pi1PiP_{i-1}P_i 是进入多边形 Q,还是走出 Q 两种情况。(这决定了我们选择 Pi1 PiP_{i-1} 还是 P_i)

    在这里插入图片描述

    1. Pi1PiP_{i-1}P_i 正进入多边形 Q ,此时应先输出 上次求得交点后的多边形Q上的各顶点,再输出本次交点。
    2. Pi1PiP_{i-1}P_i 是走出多边形 Q ,此时应先输出 上次求得交点后的多边形P上的各顶点,再输出本次交点。
      区分这两种情况,可通过检查 PiP_i 在直线 Qj1QjQ_{j-1}Q_j左侧还是右侧来确定。

    伪代码

    /* P、Q为多边形顶点数组,l、m为顶点个数*/
    void Output(PONIT P[],int l,POINT Q[],int m){
    	POINT r0; 
    	int t;
    	if(本过程第一次调用){
    		r0 = intersect(P,i,Q,j);//r0置成Pi-1Pi与Qj-1Qj之交点
    		if (left(P,i,Q,j)) //Pi在Qj-1Qj左
    			t = i;
    		else  
    			t = j;
    	}else {
    		 if (left(P,i,Q,j)) {//若Pi在Qj-1Qj左,输出Q中t至j-1顶点,输出Pi-1Pi与Qj-1Qj之交点
    			 out(Q,t,j-1);
    			 t = i;
    		 }else {//输出P中t至i-1顶点,输出Pi-1Pi与Qj-1Qj之交点
    			 out(P,t,i-1);
    			 t = j;
    		 }
    	}
    }
    

    交点个数

    多边形 P 和 Q 的交点个数决定了我们算法循环次数的上限。

    多边形 P 和 Q,P 中的每一条边与 P 相交最多两个交点,故 Q 最多与 P 交 2m 个交点,同理,P 最多与 Q 交 2l 个交点。因此 2(l+m) 步是足够的。

    完整伪代码

    两个凸多边形求交的完整算法:

    /* P、Q为多边形顶点数组,l、m为多边形边数 */
    void  Convex_polygon_intersection(POINT P[],int l,POINT Q[],int m)
    { 
    	int i,j,k,P0,Q0;
    	i=1;j=1;k=1;P0=P[l];Q0=Q[m];//初始化
    	while (k<=2*(l+m)&& (求得的交点不是第一个交点R0))//交替前进求交
    	{ 
    		if (Pi-1Pi与Qj-1Qj相交) Output(P,l,Q,m);//若相交,则调用Output
    		Advance(P, l, Q, m);
    		k++;
    	}
    	if(找到过交点) return ;
    	else{  
    		if(inner(Q,m,P[1])) printf("P在Q中");
    		else if (inner(P,l,Q[1])) printf("Q在P中");
    		else printf("P与Q分离");
    	}
    }
    
    展开全文
  • openlayers 多边形重叠判断平移

    千次阅读 2014-05-06 19:57:48
    1判断多边形重叠: var res = map.getResolution(); for(var i=0;i['profile'].length;i++){ var feat_be = response['profile'][i].belongsSegment; var k =i%2; var f = 0; if(k==0...

    主要目的:

    在做GIS开发时,常常需要用到空间判断的算法。比如:判断地图中的多边形与多边形是否相交。我在项目中具体的需求就是如此,在绘制多个polygon多边形后,判断多边形之间是否重叠,如果重叠,则需要将两个多边形分离。延某一个方向移动该多边形。在选择分离重叠的多边形方案时,可以确定以其中一个多边形为中心,即参考物。移动时平移其周边的多边形即可。
    1,首先要获得周边移动对象
    2,判断多边形之间是否相交,用自带函数intersect()
    3,计算移动的方向和移动距离,由于openalyers中的move(x,y)和moveto(x,y),如果直接将x,y代入数字只能移动一段特定的距离,没有方向的选择,所以我们这里还是用move(x,y)函数,但是首先获得需要一定方向和距离直线上两点的经纬度,然后利用getViewPortPxFromLonLat(lonlat, resolution) 函数将具体的经纬度坐标转换为像素点。
    调用dragfeature类中的geometry.move(res * (pixel.x - lastPixel.x),  res * (lastPixel.y - pixel.y));函数。便可移动多边形,方向和距离分别为两点经纬度的方向和距离。

    代码显示:

    1判断多边形重叠:
    var res = map.getResolution();
    		            for(var i=0;i<response['profile'].length;i++){
    		            	var feat_be = response['profile'][i].belongsSegment;				            	
    		            	var k =i%2;
    		            	var f = 0;
    						if(k==0){
    							f = i;
    						}else if(k==1){
    							f = i-1;
    						}	
    						var a = feat[f].geometry.getVertices()[1];
    		    			var b = feat[f].geometry.getVertices()[0];
    		    		    var pixel = getViewPortPxFromLonLat(a , res);
    		    	        var lastPixel = getViewPortPxFromLonLat(b , res);
    		            	intersects12 = feat[i].geometry.intersects(feat_survery.geometry);
    		            	var j =i+1;
    						/*
    						 * 判断剖面和测绘是否相交
    						 */
    						while(intersects12) { 
    							if(j<response['profile'].length){
    								feat[i].geometry.move(res * (pixel.x - lastPixel.x), 
    													res * (lastPixel.y - pixel.y));
    								feat[j].geometry.move(res * (pixel.x - lastPixel.x), 
    													res * (lastPixel.y - pixel.y)); 
    								for(var ho=0;ho<response['hole'].length;ho++){
    									var hole_be = response['hole'][ho].belongsSegment;
    									if(feat_be == hole_be){
    									hole[ho].geometry.move(res * (pixel.x - lastPixel.x), 
    														res * (lastPixel.y - pixel.y));            			
    									layer.drawFeature(hole); 
    									}
    								}
    								for(var ca=0;ca<response['cable'].length;ca++){
    									var cable_be = response['cable'][ca].belongsSegment;
    									if(feat_be == cable_be){
    									cable[ca].geometry.move(res * (pixel.x - lastPixel.x), 
    														res * (lastPixel.y - pixel.y));            			
    									layer.drawFeature(cable); 
    									}
    								}
    								layer.drawFeature(feat);
    								layer.drawFeature(hole);
    								layer.drawFeature(cable);
    							}
    							intersects12 = feat[i].geometry.intersects(feat_survery.geometry);
    						}
    					}  
    2,经纬度转换为像素点:
    /*
    					 * 函数:经纬度转换为像素点
    					 */           
    		            function getViewPortPxFromLonLat(lonlat, resolution) {
    		                var px = null; 
    		                if (lonlat != null) {               
    		                    px = new OpenLayers.Pixel(
    		                        (1/resolution * (lonlat.x - extent.left)),
    		                        (1/resolution * (extent.top - lonlat.y))
    		                    );    
    		                }
    		                return px;
    		            }



    具体代码为我实际项目中应用代码:
    <%@ page language="java" contentType="text/html; charset=UTF-8"
        pageEncoding="UTF-8"%>
    <%@ taglib prefix="s" uri="/struts-tags" %>
    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
    <html xmlns="http://www.w3.org/1999/xhtml">
    <head>
    	<meta http-equiv="Content-Type" content="text/html;charset=UTF-8" />
    	<%
        String path = request.getContextPath();
        String basePath = request.getScheme() + "://"
                + request.getServerName() + ":" + request.getServerPort()
                + path + "/";
        String id = request.getParameter("id");
    	%>
    	<base href="<%=basePath%>">
    	<link href="style/profile.css" rel="stylesheet" type="text/css" media="screen"/>
    </head>
    <body οnlοad='init(<%=id%>)'> 
    	<div id="map"></div>
    	<script>
    	function init(id){
    		var extent = new OpenLayers.Bounds(//初始化视图的边界设置,参照conf.cdi文件中的值
    				120.50490375617102, 30.588471912865483,
    				120.5859733795086,	30.685245907613851
    			);
    		var map = new OpenLayers.Map('map');
    		map.div.oncontextmenu = function () { return false;};//屏蔽浏览器的右键菜单 
    		var baseLayer = new OpenLayers.Layer.Image(
    				'Grid',
    				'img/blank.png',
    				extent,
    				new OpenLayers.Size(2000, 1500),
    				{
    					isBaseLayer: true,
    					numZoomLevels: 8
    				});
    		var layer = new OpenLayers.Layer.Vector();
    		map.addLayers([baseLayer,layer]);
    		   var mousePositionCtl = new OpenLayers.Control.MousePosition({
    		       prefix: '<a target="_blank" ' +
    		           'href="http://spatialreference.org/ref/epsg/4326/">' +
    		           'EPSG:4326</a> coordinates: ',
    		       separator: ' | ',
    		       numDigits: 2,
    		       emptyString: 'Mouse is not over map.'
    		       }
    		   );
    		   map.addControl(mousePositionCtl);
    	    OpenLayers.Request.GET({
    	    	url: "getProfileCableHoleByWell.action?WellId="+id,
    	        success: profileProperty_success
    	    });
    		function profileProperty_success(req){
    			var format = new OpenLayers.Format.JSON();
    		    var response = format.read(req.responseXML || req.responseText);
    		    var wellStyle;
    		    if(response['well'].countSquare && parseInt(response['well'].countSquare)!=0){
    		    	wellStyle = {		    			
    			    		externalGraphic : "img/icons/square.svg",
    			    		pointRadius : 8
    		    	}
    		    }else{
    		    	wellStyle = {	
    			    		externalGraphic : "img/icons/well.svg",
    			    		pointRadius : 8
    			    };
    		    } 
    		    var style;
    		    var features = [];		    
    		    var index = 0;
    		    var segment = [], feat = [], hole = [], cable = [];
    		    var feat_survery, intersects12;
    		    console.log(response)		   
    			for(key in response){
    				if(key != 'well'){
    					for(var i=0;i<response[key].length;i++,index++){												
    						switch(key){						
    						case 'ccable':
    							var cableRadius = 6;
    							switch(response[key][i].voltagegrade){
    							case 0:
    								style = {externalGraphic:"img/holes/communicate.svg",pointRadius: cableRadius};
    								break;
    							case 1:
    								style = {externalGraphic:"img/holes/hole04.svg",pointRadius: cableRadius};
    								break;
    							case 2: 
    								style = {externalGraphic:"img/holes/hole10.svg",pointRadius: cableRadius};
    								break;
    							case 3: 
    								style = {externalGraphic:"img/holes/hole35.svg",pointRadius: cableRadius};
    								break;
    							case 4: 
    								style = {externalGraphic:"img/holes/hole110.svg",pointRadius: cableRadius};
    								break;
    							case 5: 
    								style = {externalGraphic:"img/holes/hole220.svg",pointRadius: cableRadius};
    								break;
    							case 6: 
    								style = {externalGraphic:"img/holes/hole330.svg",pointRadius: cableRadius};
    								break;
    							case 7: 
    								style = {externalGraphic:"img/holes/hole500.svg",pointRadius: cableRadius};
    								break;
    							case 8: 
    								style = {externalGraphic:"img/holes/hole750.svg",pointRadius: cableRadius};
    								break;
    							}
    							break;						
    						case 'segment':
    							switch(response[key][i].objecttype){
    							case 1020211:
    								style = {
    									strokeWidth : 10,
    									strokeColor : '#3399CC'
    								};// 排管
    								break;
    							case 1020212:
    								style = {
    									strokeWidth : 10,
    									strokeColor : '#00FFFF'
    								};// 桥架
    								break;
    							case 1020213:
    								style = {
    									strokeWidth : 10,
    									strokeColor : '#996600'
    								};// 沟道
    								break;
    							case 1020214:
    								style = {
    									strokeWidth : 10,
    									strokeColor : '#00FF00'
    								};// 直埋
    								break;
    							case 1020215:
    								style = {
    									strokeWidth : 10,
    									strokeColor : '#666666'
    								};// 隧道
    								break;
    							case 1020216:
    								style = {
    									strokeWidth : 10,
    									strokeColor : '#003399'
    								};// 顶管
    								break;
    							case 1020203:
    								style = {
    									strokeOpacity: 0.5,
    									strokeWidth : 10,
    									strokeColor : '#3399CC'
    								};// 虚拟管沟
    								break;
    							}
    							break;
    						case 'pointsurvery':
    							style = {
    								strokeColor : "black",
    								strokeOpacity : 0,
    								strokeWidth : 1,
    								fillOpacity : 0,
    								fillColor : "#4FD5D6",
    								pointRadius : 6,
    								cursor : "inherit"
    							};//工井测绘
    							break;
    						case 'profile':
    							style = {
    								strokeColor : "black",
    						    	strokeOpacity : 0,
    						    	strokeWidth : 1,
    						    	fillOpacity : 0,
    						    	fillColor : "#FFCC00",
    						    	pointRadius : 6,
    						    	cursor : "inherit"
    						   	};	
    							break;
    						default:
    							style = {
    								strokeColor : "none",
    								strokeOpacity : 1,
    								strokeWidth : 1,
    								fillOpacity : 0.9,
    								fillColor : "none",
    								pointRadius : 6,
    								cursor : "inherit"
    							};
    						}						
    						features[index] = new OpenLayers.Feature.Vector(
    								new OpenLayers.Geometry.fromWKT(response[key][i].geometry),null,style
    						);
    					}
    				}			
    			}	
    			/*
    			 * 剖面弹出框设备样式
    			 */		    
    		    style_profile = {
    					strokeColor : "black",
    		    		strokeOpacity : 1,
    		    		strokeWidth : 1,
    		    		fillOpacity : 0.5,
    		    		fillColor : "#FFCC00",
    		    		pointRadius : 6,
    		    		cursor : "inherit"
    		   		};	
    		    style_pointsurvery = {
    					strokeColor : "black",				
    					strokeOpacity : 1,
    					strokeWidth : 1,
    					fillOpacity : 0.5,
    					fillColor : "#4FD5D6",
    					pointRadius : 6,
    					cursor : "inherit"
    				};
    		    style_segment = {
    					strokeColor : "red",				
    					strokeOpacity : 1,
    					strokeWidth : 4,
    					strokeDashstyle : 'dash',
    					cursor : "inherit"
    				};
    		    style_hole = {
    					strokeColor : "black",				
    					strokeOpacity : 1,
    					strokeWidth : 1,
    					fillColor : "white",
    					cursor : "inherit"
    				};
    		    features[features.length] = new OpenLayers.Feature.Vector(new OpenLayers.Geometry.fromWKT(response['well'].geometry),null,wellStyle);
    			layer.addFeatures(features);
    			if(response['profile'].length > 0 ){
    				for(var i=0;i<response['profile'].length;i++){
    					feat[i] = new OpenLayers.Feature.Vector( new OpenLayers.Geometry.fromWKT(response['profile'][i].geometry),null,style_profile);				
    				}				
    				layer.addFeatures(feat);
    			}
    			if(response['hole'].length > 0){
            		for(var ho=0;ho<response['hole'].length;ho++){
        				hole[ho] = new OpenLayers.Feature.Vector( new OpenLayers.Geometry.fromWKT(response['hole'][ho].geometry),null,style_hole);				
        			}
            		layer.addFeatures(hole);
    			}
    			if(response['cable'].length > 0){
        			var cableRadius = 6;
        			for(var ca=0;ca<response['cable'].length;ca++){            				
        				switch(response['cable'][ca].voltagegrade){            				
    					case 0:
    						style_cable = {externalGraphic:"img/holes/communicate.svg",pointRadius: cableRadius};
    						break;
    					case 1:
    						style_cable = {externalGraphic:"img/holes/hole04.svg",pointRadius: cableRadius};
    						break;
    					case 2: 
    						style_cable = {externalGraphic:"img/holes/hole10.svg",pointRadius: cableRadius};
    						break;
    					case 3: 
    						style_cable = {externalGraphic:"img/holes/hole35.svg",pointRadius: cableRadius};
    						break;
    					case 4: 
    						style_cable = {externalGraphic:"img/holes/hole110.svg",pointRadius: cableRadius};
    						break;
    					case 5: 
    						style_cable = {externalGraphic:"img/holes/hole220.svg",pointRadius: cableRadius};
    						break;
    					case 6: 
    						style_cable = {externalGraphic:"img/holes/hole330.svg",pointRadius: cableRadius};
    						break;
    					case 7: 
    						style_cable = {externalGraphic:"img/holes/hole500.svg",pointRadius: cableRadius};
    						break;
    					case 8: 
    						style_cable = {externalGraphic:"img/holes/hole750.svg",pointRadius: cableRadius};
    						break;
    					}
    					cable[ca] = new OpenLayers.Feature.Vector( new OpenLayers.Geometry.fromWKT(response['cable'][ca].geometry),null,style_cable);				
    				}
        			layer.addFeatures(cable);
    			}
    			if(response['segment'].length > 0 ){
    				for(var se=0;se<response['segment'].length;se++){      					
            			segment[se] = new OpenLayers.Feature.Vector( new OpenLayers.Geometry.fromWKT(response['segment'][se].geometry),null,style_segment);	
            		}
    				layer.addFeatures(segment);
    			}
    			if(response['pointsurvery'].length > 0 ){
    				feat_survery = new OpenLayers.Feature.Vector( new OpenLayers.Geometry.fromWKT(response['pointsurvery'][0].geometry),null,style_pointsurvery);
    				layer.addFeatures(feat_survery);
    				if(response['profile'].length>0){
    					var res = map.getResolution();
    		            for(var i=0;i<response['profile'].length;i++){
    		            	var feat_be = response['profile'][i].belongsSegment;				            	
    		            	var k =i%2;
    		            	var f = 0;
    						if(k==0){
    							f = i;
    						}else if(k==1){
    							f = i-1;
    						}	
    						var a = feat[f].geometry.getVertices()[1];
    		    			var b = feat[f].geometry.getVertices()[0];
    		    		    var pixel = getViewPortPxFromLonLat(a , res);
    		    	        var lastPixel = getViewPortPxFromLonLat(b , res);
    		            	intersects12 = feat[i].geometry.intersects(feat_survery.geometry);
    		            	var j =i+1;
    						/*
    						 * 判断剖面和测绘是否相交
    						 */
    						while(intersects12) { 
    							if(j<response['profile'].length){
    								feat[i].geometry.move(res * (pixel.x - lastPixel.x), 
    													res * (lastPixel.y - pixel.y));
    								feat[j].geometry.move(res * (pixel.x - lastPixel.x), 
    													res * (lastPixel.y - pixel.y)); 
    								for(var ho=0;ho<response['hole'].length;ho++){
    									var hole_be = response['hole'][ho].belongsSegment;
    									if(feat_be == hole_be){
    									hole[ho].geometry.move(res * (pixel.x - lastPixel.x), 
    														res * (lastPixel.y - pixel.y));            			
    									layer.drawFeature(hole); 
    									}
    								}
    								for(var ca=0;ca<response['cable'].length;ca++){
    									var cable_be = response['cable'][ca].belongsSegment;
    									if(feat_be == cable_be){
    									cable[ca].geometry.move(res * (pixel.x - lastPixel.x), 
    														res * (lastPixel.y - pixel.y));            			
    									layer.drawFeature(cable); 
    									}
    								}
    								layer.drawFeature(feat);
    								layer.drawFeature(hole);
    								layer.drawFeature(cable);
    							}
    							intersects12 = feat[i].geometry.intersects(feat_survery.geometry);
    						}
    					}  
    					/*
    					 * 函数:经纬度转换为像素点
    					 */           
    		            function getViewPortPxFromLonLat(lonlat, resolution) {
    		                var px = null; 
    		                if (lonlat != null) {               
    		                    px = new OpenLayers.Pixel(
    		                        (1/resolution * (lonlat.x - extent.left)),
    		                        (1/resolution * (extent.top - lonlat.y))
    		                    );    
    		                }
    		                return px;
    		            }
    				}
    			}
    		    map.zoomToExtent(extent, true);
    		    var center = new OpenLayers.LonLat(features[features.length-1].geometry.x, features[features.length-1].geometry.y).transform(
    					new OpenLayers.Projection("EPSG:4326"),
    					map.getProjectionObject());
    		    map.setCenter(center,5);
    		    console.log(map)
    		}
    	}
    	
    	</script>
    	<script src="lib/OpenLayers.js"></script>
    </body>
    </html>
    


    展开全文
  • 计算两个不规则多边形重叠的面积

    千次阅读 2020-05-20 09:27:33
    } //计算多边形面积 double PolygonArea(Point p[], int n) { if(n ) return 0.0; double s = p[0].y * (p[n - 1].x - p[1].x); for(int i = 1; i ; ++ i) { s += p[i].y * (p[i - 1].x - p[i + 1].x); // cout [i-...
    #include <iostream>
    #include <cmath>
    #include <cstring>
    
    using namespace std;
    
    const int maxn = 300;
    const double eps = 1e-6;
    int dcmp(double x)
    {
        if(x > eps) return 1;
        return x < -eps ? -1 : 0;
    }
    struct Point
    {
        double x, y;
    };
    double cross(Point a,Point b,Point c) ///叉积
    {
        return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
    }
    Point intersection(Point a,Point b,Point c,Point d)
    {
        Point p = a;
        double t =((a.x-c.x)*(c.y-d.y)-(a.y-c.y)*(c.x-d.x))/((a.x-b.x)*(c.y-d.y)-(a.y-b.y)*(c.x-d.x));
        p.x +=(b.x-a.x)*t;
        p.y +=(b.y-a.y)*t;
        cout << "intersection p.x=" << p.x << ", p.y=" << p.y << endl;
        return p;
    }
    //计算多边形面积
    double PolygonArea(Point p[], int n)
    {
        if(n < 3) return 0.0;
        double s = p[0].y * (p[n - 1].x - p[1].x);
        for(int i = 1; i < n - 1; ++ i) {
            s += p[i].y * (p[i - 1].x - p[i + 1].x);
            // cout << "p[i-1].x =" << p[i-1].x << ", p[i-1].y=" << p[i-1].y << endl;
            // cout << "p[i].x =" << p[i].x << ", p[i].y=" << p[i].y << endl;
            // cout << "p[i+1].x =" << p[i+1].x << ", p[i+1].y=" << p[i+1].y << endl;
        }
        s += p[n - 1].y * (p[n - 2].x - p[0].x);
        cout << "s =" << s << endl;
        return fabs(s * 0.5);
    }
    double CPIA(Point a[], Point b[], int na, int nb)//ConvexPolygonIntersectArea
    {
        Point p[20], tmp[20];
        int tn, sflag, eflag;
        memcpy(p,b,sizeof(Point)*(nb));
        for(int i = 0; i < na && nb > 2; i++)
        {
        	if (i == na - 1) {
        		sflag = dcmp(cross(a[0], p[0],a[i]));
        	} else {
        		sflag = dcmp(cross(a[i + 1], p[0],a[i]));
        	}
            for(int j = tn = 0; j < nb; j++, sflag = eflag)
            {
                if(sflag>=0) {
                	tmp[tn++] = p[j];
                }
                if (i == na - 1) {
                	if (j == nb -1) {
                		eflag = dcmp(cross(a[0], p[0], a[i]));
    				} else {
    					eflag = dcmp(cross(a[0], p[j + 1], a[i]));
    				}
    			} else {
    				if (j == nb -1) {
    					eflag = dcmp(cross(a[i + 1], p[0], a[i]));
    				} else {
    					eflag = dcmp(cross(a[i + 1], p[j + 1], a[i]));
    				}
    			}
                if((sflag ^ eflag) == -2){
                	if (i == na - 1) {
                		if (j == nb -1) {
                			tmp[tn++] = intersection(a[i], a[0], p[j], p[0]); //求交点
                		} else {
                			tmp[tn++] = intersection(a[i], a[0], p[j], p[j + 1]);
                		}
    				} else {
    					if (j == nb -1) {
    						tmp[tn++] = intersection(a[i], a[i + 1], p[j], p[0]);
    					} else {
    						tmp[tn++] = intersection(a[i], a[i + 1], p[j], p[j + 1]);
    					}
    				}
                }
            }
            memcpy(p, tmp, sizeof(Point) * tn);
            nb = tn, p[nb] = p[0];
        }
        if(nb < 3) return 0.0;
        return PolygonArea(p, nb);
    }
    double SPIA(Point a[], Point b[], int na, int nb)///SimplePolygonIntersectArea 调用此函数
    {
        int i, j;
        Point t1[na], t2[nb];
        double res = 0, num1, num2;
        t1[0] = a[0], t2[0] = b[0];
        for(i = 2; i < na; i++)
        {
            t1[1] = a[i-1], t1[2] = a[i];
            num1 = dcmp(cross(t1[1], t1[2],t1[0]));
            if(num1 < 0) swap(t1[1], t1[2]);
            for(j = 2; j < nb; j++)
            {
                t2[1] = b[j - 1], t2[2] = b[j];
                num2 = dcmp(cross(t2[1], t2[2],t2[0]));
                if(num2 < 0) swap(t2[1], t2[2]);
                res += CPIA(t1, t2, 3, 3) * num1 * num2;
            }
        }
        cout << "Sum::res=" <<res << endl;
        return res;
    }
    Point p1[maxn], p2[maxn];
    int n1, n2;
    int main()
    {
    
        while(cin>>n1>>n2)
        {
            for(int i = 0; i < n1; i++) scanf("%lf%lf", &p1[i].x, &p1[i].y);
            for(int i = 0; i < n2; i++) scanf("%lf%lf", &p2[i].x, &p2[i].y);
            double Area = SPIA(p1, p2, n1, n2);
            cout << "Area=" << Area << endl;
            double A1 = PolygonArea(p1, n1);
            double A2 = PolygonArea(p2, n2);
            cout << "A1 =" << A1 << ", A2=" << A2 << endl;
        }
        return 0;
    }
    
    

    测试结果1:

    输入的参数为:
    4 4
    0 0 0 3 5 3 5 0
    3 1 3 4 6 4 6 1
    
    产生的过程的log和结果:
    intersection p.x=5, p.y=3
    intersection p.x=3, p.y=1.8
    intersection p.x=3, p.y=3
    s =2.4
    intersection p.x=6, p.y=3.6
    intersection p.x=5, p.y=3
    intersection p.x=5, p.y=3
    intersection p.x=5, p.y=4
    intersection p.x=3, p.y=1.8
    s =1.6
    intersection p.x=5, p.y=1
    intersection p.x=5, p.y=3
    s =4
    Sum::res=4
    Area=4
    s =-30
    s =-18
    A1 =15, A2=9
    

    测试结果2:

    输入的参数为:
    4 5
    3 1 6 1 6 4 3 4
    3 0 5 1 5 3 3 1 0 2
    
    产生的过程的log和结果:
    intersection p.x=3.66667, p.y=1
    s =2.66667
    intersection p.x=3.66667, p.y=1
    s =1.33333
    intersection p.x=1.5, p.y=1
    intersection p.x=2.4, p.y=0.4
    Sum::res=2
    Area=2
    s =18
    s =9
    A1 =9, A2=4.5
    
    展开全文
  • 多边形是否重叠

    千次阅读 2006-11-08 10:52:00
     判断点P是否在多边形中是计算几何中一个非常基本但是十分重要的算法。以点P为端点,向左方作射线L,由于多边形是有界的,所以射线L的左端一定在多边形外,考虑沿着L从无穷远处开始自左向右移动,遇到

        题目:多边形是否重叠(有可能是凹多边形,有点重叠了就算。pku acm 3082题目)。 可以分为几种情况: 点点是否重叠  点是否在线上  点是否在在多边形内部,最后一个是关键。        

    判断点P是否在多边形中是计算几何中一个非常基本但是十分重要的算法。以点P为端点,向左方作射线L,由于多边形是有界的,所以射线L的左端一定在多边形外,考虑沿着L从无穷远处开始自左向右移动,遇到和多边形的第一个交点的时候,进入到了多边形的内部,遇到第二个交点的时候,离开了多边形,……所以很容易看出当L和多边形的交点数目C是奇数的时候,P在多边形内,是偶数的话P在多边形外。
    为了统一起见,在计算射线L和多边形的交点的时候,1。对于多边形的水平边不作考虑;2。对于多边形的顶点和L相交的情况,如果该顶点是其所属的边上纵坐标较大的顶点,则计数,否则忽略;3。对于P在多边形边上的情形,直接可判断P属于多边行。

    题目:

    'Roid Rage
    Time Limit:1000MS  Memory Limit:65536K
    Total Submit:177 Accepted:52

    Description
    When writing game programs, it is often useful to determine when two polygons intersect one another. This is especially useful in arcade games like Asteroids where one polygon could represent a spaceship while another represents a huge, unyielding chunk of space rock.

    Write a program that can determine which polygons of a given set intersect one another.

    Input
    Input to this problem will begin with a line containing a single integer n indicating the number of datasets. Each data set consists of the following components:

     

    Output
    For each dataset in the input, output the heading "Data Set #z", where z is 1 for the first dataset, 2 for the second, etc. If this data set contained no intersecting polygons, output the message "no collisions" on its own line. Otherwise, output the list of all pairs of intersecting polygons, one pair per line, each pair formatted with the lowest-numbered polygon first. Output the polygon pairs in ascending order, sorting first by the lowest-numbered polygon in the set and then the second.

    Note: The definition of "intersecting" for the purpose of this problem means that two polygons either share an interior region (i.e., they overlap), or they share boundary points (i.e., they touch at a point or along an edge).

    Sample Input

     

    Sample Output

     

    Source
    2006 South Central USA Regional Programming Contest

    Source

    Problem Id:3082  User Id:bmexue
    Memory:72K  Time:0MS
    Language:C++  Result:Accepted

    • Source

       

       

      #include <iostream>
      using namespace std;
      int m;
      struct Point
      {
      	int x,y;
      };
      Point d[10][21];
      bool one_two(int a, int b , int t) //ok
      {
      	if(t>=a && t<=b)
      		return true;
      	if(t<=a && t>=b)
      		return true;
      	return false;
      }
      bool one_two(double a, double b , double t)  //ok
      {
      	if(t>=a && t<=b)
      		return true;
      	if(t<=a && t>=b)
      		return true;
      	return false;
      }
      bool p_line(Point a, Point b, Point t)
      {
      	if(b.x == a.x){   //水平线
      		if( t.x == a.x && one_two(a.y,b.y,t.y))
      			return true;
      		return false;
      	}
      	else if(b.y == a.y){   //垂直边
      		if( t.y == a.y && one_two(a.x,b.x,t.x))
      			return true;
      		return false;
      	}
      	else{    //斜边
      		if( (b.x-t.x == 0) || (a.x-t.x ==0) )
      			return false;
      		if(  (double)(b.y-t.y)/(double)(b.x-t.x) ==  (double)(a.y-t.y)/(double)(a.x-t.x) && one_two(a.y,b.y,t.y))
      			return true;
      	}
      	return false;
      }
      bool p_p(Point a, Point b)  //点点
      {
      	if(a.x==b.x && a.y==b.y)
      		return true;
      	return false;
      }
      int min(int a, int b)
      {
      	if(a<b) return a;
      	return b;
      }
      int max(int a, int b)
      {
      	if(a>b)
      		return a;
      	return b;
      }
      bool dline_line(int y0, int x0, Point a, Point b)
      {   
      	if(a.y == b.y)   //水平边  不考虑
      		return false;
      	if(y0 <= min(a.y,b.y)) // 相交在纵坐标低的不算
      		return false;
      	if( y0 > max(a.y,b.y))  //不在带状区域
      		return false;
      	if(x0>=max(a.x,b.x)) //射线源在边的右边,可以不考虑
      		return false;
      	if(a.x == b.x){  // 垂直边
              if( one_two(a.y,b.y,y0) && a.x > x0){  //向右边发射现可以相交 
      			return true;
      		}
      	    return false;
      	}
          //斜边:
      	double tmp_x = (double)(y0-a.y)*(double)(b.x-a.x)/(double)(b.y-a.y) + (double)a.x;
      	if(tmp_x < (double)x0) //相交在x0的左边了
      		return false;
      	if(one_two( (double)a.x,(double)b.x,tmp_x))
      		return true;
      	return false;
      }
      bool polygon_polygon(int i, int j)
      {
      	int v1 = d[i][0].x;
      	int v2 = d[j][0].x;
      	int a,b;
          for(a=1; a<=v1;a++){   //p_p
      		for(b=1;b<=v2;b++){
      			if(p_p( d[i][a], d[j][b]))
      				return true;
      		}
      	}
          for(a=1; a<=v1;a++){  //p_line
      		for(b=1;b<v2;b++){
      			if(p_line(d[j][b],d[j][b+1], d[i][a]) )
      				return true;
      		}
      		if( p_line(d[j][1],d[j][v2], d[i][a]) )
      			return true;
      	}
      	for(b=1; b<=v2;b++){   // p_line   b=1 a=2
      		for(a=1;a<v1;a++){
      			if(p_line(d[i][a],d[i][a+1], d[j][b]) )
      				return true;
      		}
      	    if( p_line(d[i][1],d[i][v1], d[j][b]) )//b==3 a==3  xxxxxxxxxx
      			return true;
      	}
          //i 的点在j内?
          int num;
      	for(a=1;a<=v1;a++){
      		num=0;
      		for(b=1;b<v2;b++){
      		   if(dline_line(d[i][a].y,d[i][a].x ,   d[j][b],d[j][b+1]) )
      			   num++;
      		}
              if(dline_line(  d[i][a].y,d[i][a].x ,   d[j][1],d[j][v2]))
      			   num++;
      		if(num%2 !=0)   //奇数个交点就在内部
      			return true;
      	}
      	//j的点在i内
          for(b=1;b<=v2;b++){
      		num=0;
      		for(a=1;a<v1;a++){
      		   if(dline_line(d[j][b].y, d[j][b].x,    d[i][a],d[i][a+1]) )
      			   num++;
      		}
        	    if(dline_line(d[j][b].y,d[j][b].x,d[i][1],d[i][v1]) )
      			   num++;
      		if(num%2 !=0)
      			return true;
      	}
      
      	return false;
      	
      }
      void work(int ii)
      {
      	printf("Data Set #%d/n",ii);
      	int fir =0;
      	for(int i=0; i<m;i++){
      		for(int j=i+1; j<m;j++){
      		     if	(polygon_polygon(i,j) ){
      				 printf("%d %d/n",i+1,j+1);fir++;
      			 }
      		}
      	}
      	if(fir==0)
      		printf("no collisions/n");
      }
      int main()
      {
      	int n,p,v,i;
      	char c='d';
      	scanf("%d",&n);
      	int ii=1;
      	while(ii<=n){
      		scanf("%d",&m);   //num
      		i=0;  
      		while(i<m){   //m line
      			scanf("%d",&v);  d[i][0].x =v; p=1;
      		    while(p<=v){
      			   scanf("%d%c%d",&d[i][p].x,&c,&d[i][p].y); 
      			   p++;
      			} 
      			i++;
      		}
      		work(ii);
              ii++;
      	}
      	return 0;
      }
      

     

     

    Data Set #1
    no collisions
    Data Set #2
    1 2
    1 4
    2 4
    3 4

     

    2
    2
    4 0,0 1,0 1,1 0,1
    4 2,2 3,2 3,3 2,3
    4
    3 2,1 1,2 2,3
    3 2,1 3,2 2,3
    5 2,0 4,2 2,4 5,4 5,0
    4 3,3 1,3 1,5 3,5

     

    1. A line containing a single positive integer m (1 <= m <= 10) indicating the number of polygons to analyze.
    2. m lines, each representing a single polygon, with the first line describing polygon 1, the second line describing polygon 2, and so on. Each line begins with a single positive integer v (3 <= v <= 20) indicating the number of vertices describing this polygon. This is followed by v (x,y) coordinate pairs (0 <= x, y <= 100), each of which is a vertex of this polygon. The vertices are connected by edges in the order listed with the last vertex connected back to the first by a final edge. All polygons are "simple"; they do not self-intersect.
    展开全文
  • 生成多边形 随机生成若干个点,就可以生成多边形。 严格来说,是要判断产生的点是否共线的,但是这样概率太低,所以我就没有判断。生成的点不能直接连起来,因为点的顺序有可能是错乱的,所以首先要进行顺序判断,...
  • select st_astext( ST_Intersection( ST_Multi(st_geomfromEWKT('SRID=32649;POLYGON((x1 y1, x2 y2, x3 y3...执行sql后返回重叠区域的polygon字符串,如果没有重叠区域则返回"GEOMETRYCOLLECTION EMPTY"字符串
  • 在网上看了很多的文章都没有找到解决方案,功夫不负有心人,在网上找到个可以判断是否重复的,但是在包含的情况下就不能判断,后来自己加入根据点判断点是否在多边形内来判断重复,问题已解决,在此把代码贴出来,供...
  • 扫描线算法判断多边形是否合法

    千次阅读 2013-05-04 01:59:29
    题目大意:就是求多边形面积,可能是凹多边形,还有就是判断不能形成多边形的情况 解题思路:使用扫描线算法判断是否存在不相邻的两条边是否有交点,以及相邻的边是否重叠;  使用的一些小trick  线段相交...
  • Python | 任意多边形间的重叠面积计算

    千次阅读 热门讨论 2019-10-19 23:49:03
    简介 跟某人讨论一个排样问题。 他说,算法搜索速度很慢,每两个物体间的重叠面积计算时间若按1s来算,300个物体需要...给定的数据为多边形的各个顶点,为N*2的矩阵,N 为多边形的顶点个数,计算任意两个多边形重叠...
  • 在地图中绘制多边形时如何判断两图形有重叠部分
  • python 判断多边形,点是否重合 首先代码并未使用 cv2.pointPolygonTest 这一opencv函数,因为自己在使用时,一直报错,很难自己构造出适用于 pointPolygonTest ()的 tuple参数,然后在网上找到了如下这边博客写的...
  • 如何计算两个多边形重叠·区域

    千次阅读 2015-12-01 16:36:11
    查看PDF手册有方法如下: 8.10.13 ST_Intersection ST_Intersection — (T) Returns a geometry that represents the shared portion of geomA and geomB.... does a transform to geometry to do...
  • 判断点在多边形内部

    2014-08-12 12:20:36
    判断点在多边形内部 作者:hyp 微博:http://weibo.com/hhyypp 0.前言 最近不断遇到类似的几何位置问题,一直没有花时间去总结,本文总结了我常用点跟多边形的位置判断方法以及代码。希望能够对大家...
  • ArcGIS案例学习笔记-查找重叠多边形 联系方式:向日葵,135-4855-4328,xiexiaokui@qq.com 目的:对于多边形图层,查找具有重叠(相互覆盖)的面 数据: 方法: 1. 生成重叠部分的多边形 2. 空间...
  • 所以我们在绘制的时候需要判断当前绘制的图形是否是多边形: 1:下载百度地图开源库里面的鼠标绘制工具条库:DrawingManager.js 2:找到DrawingManager.prototype._bindPolylineOrPolygon方法里面的startAction方法,...
  • js 判断平面几何图形是否重叠

    千次阅读 热门讨论 2018-09-05 10:20:08
    1. 点线面数据格式 点: { x: xxx, y: xxx } 线: [{ x: xxx, y: xxx }, { x: xxx, y: xxx }] 面: [{ x: xxx, y: xxx }, { x: xxx, y: xxx }, { x: xxx, y: xxx }...] ...//判断多边形线段是否相交 fu...
  • 1.射线判别法   根据对多边形的了解,我们可以得出如下结论: 如果一个点在多边形内部,任意角度做...利用上面的结论,我们只要判断这个点与多边形的交点个数,就可以判断出点与多边形的位置关系了。 首先罗列下注意事
  • 原文地址 http://www.cnblogs.com/topcss/p/3575248.html ,基于该作者的代码基础上进行简单修改,使其在openlayers3上可用,有兴趣可以去看一下
  • 碰撞检测:判断2个多边形相交

    千次阅读 2019-03-02 14:41:09
    演示demo: 需要判断2个条件 ...《碰撞检测:判断点是否在多边形内部》 https://blog.csdn.net/StevenKyleLee/article/details/88044589 《碰撞检测:判断线段相交》 https://blog.csdn.net/StevenKy...
  • 判断一个坐标点是否在多边形区域范围内。可直接使用。 用来做地图经纬度 判断一个点是否在一个多边形范围内很合适 代码简洁 不到100行代码
  • 新页面(new page)介绍了将样条曲线添加到...我们要判断红色点是否在多边形内。 解决方案是将测试点的Y坐标与多边形的每一个点进行比较,我们会得到一个测试点所在的行与多边形边的交点的列表。在这个例子中有8条边

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,407
精华内容 1,362
关键字:

判断多边形重叠