精华内容
下载资源
问答
  • 1、 使用truf库的booleanContains函数,这个函数可以检测两个几何是否为包容关系 使用:引入相关函数,因为truf识别的geometry不是openlayers中的geometry,所以需要使用其提供的函数,转换成对应的geometry import ...

    1、 使用openlayers自带的geom. containsXY方法

    该方法是监测坐标点是否在多边形内,所以Geom的类型只能是Polygon、MultiPolygon、GeometryCollection、Circle中的一个,且该方法的参数是点

    使用:polygon.containsXY(coors[0], coors[1])

    那我们如何使用这个检测点与面关系的函数,去检测面与面之间的关系?我们可以这样做:

    比如有A、B两个多边形
    1、遍历A多边形上的点,判断是否有坐标点在B多边形内 — 返回结果 a
    2、遍历B多边形上的点,判断是否有坐标点在A多边形内 — 返回结果 b

    如果a、b都为true,则两个多边形相交
    如果a为true,b为false,则多边形B包含多边形A
    如果a为false,b为true,则多边形A包含多边形B
    如果a、b都为false,则两个多边形远离

    代码如下:

    function judge(coorsA, coorsB){
      //booleanContains
      let geomA = new ol.geom.Polygon([coorsA])
      let geomB = new ol.geom.Polygon([coorsB])
    
      let boola = coorsA.some(item => {
        return geomB.containsXY(item[0], item[1])
      })
      let boolb = coorsB.some(item => {
        return geomA.containsXY(item[0], item[1])
      })
    
      return [
        ['相离', 'A包含B'],
        ['B包含A', '相交']
      ][+boola][+boolb]
    }
    

    2、 使用truf库的booleanContains函数,这个函数可以检测两个几何是否为包容关系

    使用:引入相关函数,因为truf识别的geometry不是openlayers中的geometry,所以需要使用其提供的函数,转换成对应的geometry

    import booleanContains from '@turf/boolean-contains'
    import {geometry, polygon, lineString} from '@turf/helpers'
    
    let contains = booleanContains( polygon(parent.coors), polygon(child.coors) )
    

    函数可以监测的类型如下
    booleanContains

    如果父元素的类型是LineString,那么子元素的类型可以是Point、LineString、MultiPoint,此外都会抛出错误,以此类推。

    其他相似方法:
    booleanCrosses:检测两个几何是否相交
    booleanDisjoint:检测两个几何是否不相交

    经过测试,使用openlayers自带的方法性能上可能比truf要好,而且不需要在引入额外库,所以推荐使用openlayers自带的函数进行封装。

    展开全文
  • 比如两个多边形位置关系是相交 ,内含,还是多边形外等。有没有什么算法?
  • 判断两个多边形是否相交 ,当前认为一个点相交也是相交,可针对凹多边形和凸边型等多复杂的多边形进行相交判断,采用java实现,因为网上java实现的比较少,所以这里写下如何实现,适用于碰撞检测,地图等等应用场景

    判断两个多边形是否相交 ,当前认为一个点相交也是相交,可针对凹多边形和凸边型等多复杂的多边形进行相交判断,采用java实现,因为网上java实现的比较少,所以这里写下如何实现,适用于碰撞检测,地图等等应用场景

    入口方法:intersectionJudgment

    package org.dxl;
    
    import lombok.AllArgsConstructor;
    import lombok.Data;
    import lombok.NoArgsConstructor;
    import lombok.experimental.Accessors;
    import lombok.extern.slf4j.Slf4j;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collection;
    import java.util.List;
    
    /**
     * * @projectName launcher2
     * * @title Test
     * * @package org.dxl
     * * @description  判断两个多边形是否相交
     * * @author IT_CREAT     
     * * @date  2020 2020/11/5/005 22:06  
     * * @version
     */
    @Slf4j
    public class Test {
        /*
        第一步:快速排除,以某一个多边形参照物,沿着此多边形画矩形,用矩形将多边形包起来,
        在判断另一个多边形是否在这个矩形框中存在顶点,没有就说明另一个矩形一定在参照矩形框的外围。
        第二步:利用的是向量叉乘求两线段是否相交,这种求法是求的绝对相交(交叉相交),只要存在多边形任意两线段相交,就一定相交,
        同时还有一种情况,就是平行或者在延长线及线段上,这时候需要排除平行和在延长线上的情况
        第三步:用点射法求某一个顶点是否在某个多边形内部,这里需要同时同时判断多变形1上的所有点都在多边形2的内部或者边线段上,
        或者是反向多边形2的所有点在多边形1的内部或边线上,二者满足其一即可;
        */
        public static void main(String[] args) {
            Point point = new Point(0, 0.5);
            Polygon polygon = new Polygon().setPoints(Arrays.asList(
                    new Point(0, 0),
                    new Point(0, 0.5),
                    new Point(0.5, 0.5),
                    new Point(0.5, 0)
            ));
            // 点是否在内部
            boolean b = pointInPolygon(point, getLineSegment(polygon));
            System.out.println(b);
    
            Polygon polygon1 = new Polygon().setPoints(Arrays.asList(
                    new Point(-1, -1),
                    new Point(-1, 1),
                    new Point(1, 1),
                    new Point(1, -1)
            ));
            // 两个多边形相交
            System.out.println(intersectionJudgment(polygon, polygon1));
        }
    
        /**
         * 多边形相交判断(有一个点相交也认为相交)
         *
         * @param polygon1 多边形1
         * @param polygon2 多边形2
         * @return boolean
         */
        public static boolean intersectionJudgment(Polygon polygon1, Polygon polygon2) {
            if (isExistNull(polygon1, polygon2)) {
                return false;
            }
            if (isExistNullOrEmpty(polygon1.getPoints(), polygon2.getPoints())) {
                return false;
            }
            // 1、快速判断,如果不想交,则返回不相交
            if (!fastExclude(polygon1, polygon2)) {
                return false;
            }
            // 获取多边形线段集合
            List<LineSegment> lineSegment1 = getLineSegment(polygon1);
            List<LineSegment> lineSegment2 = getLineSegment(polygon2);
            // 存在线段集合任意一方为空,则不想交
            if (isExistNullOrEmpty(lineSegment1, lineSegment2)) {
                return false;
            }
            // 2、向量叉乘判断多边形是否存在线段相交,存在相交则返回相交
            if (crossJudgment(lineSegment1, lineSegment2)) {
                return true;
            }
            // 3、包含关系判断,分别两次判断,判断polygon1是否在polygon2内部和polygon2是否在polygon1内部,满足其一即可
            boolean isInclude = includeRelation(polygon1, lineSegment2);
            if (isInclude) {
                return true;
            }
            return includeRelation(polygon2, lineSegment1);
        }
    
        /**
         * 1、快速判断多边形是否相交
         *
         * @param polygon1 多边形1
         * @param polygon2 多边形2
         * @return boolean
         */
        private static boolean fastExclude(Polygon polygon1, Polygon polygon2) {
            // 多边形1
            double polygon1MaxX = polygon1.getPoints().get(0).getX();
            double polygon1MinX = polygon1.getPoints().get(0).getX();
            double polygon1MaxY = polygon1.getPoints().get(0).getY();
            double polygon1MinY = polygon1.getPoints().get(0).getY();
            for (Point point : polygon1.getPoints()) {
                polygon1MaxX = Math.max(polygon1MaxX, point.getX());
                polygon1MinX = Math.min(polygon1MinX, point.getX());
                polygon1MaxY = Math.max(polygon1MaxY, point.getY());
                polygon1MinY = Math.min(polygon1MinY, point.getY());
            }
    
            // 多边形2
            double polygon2MaxX = polygon2.getPoints().get(0).getX();
            double polygon2MinX = polygon2.getPoints().get(0).getX();
            double polygon2MaxY = polygon2.getPoints().get(0).getY();
            double polygon2MinY = polygon2.getPoints().get(0).getY();
            for (Point point : polygon2.getPoints()) {
                polygon2MaxX = Math.max(polygon2MaxX, point.getX());
                polygon2MinX = Math.min(polygon2MinX, point.getX());
                polygon2MaxY = Math.max(polygon2MaxY, point.getY());
                polygon2MinY = Math.min(polygon2MinY, point.getY());
            }
    
            // 我这里是人为临界点的点-点,点-线也是属于相交,(如过你认为不是,加上等于条件,也就是最大和最小出现任意相等也是不想交)
            // 1、多边形1的最大x比多边形2最小x还小,说明多边形1在多边形2左边,不可能相交
            // 2、多边形1的最小x比多边形2最大x还大,说明多边形1在多边形2右边,不可能相交
            // 3、多边形1的最大y比多边形2最小y还小,说明多边形1在多边形2下边,不可能相交
            // 4、多边形1的最小y比多边形2最大y还小,说明多边形1在多边形2上边,不可能相交
            return !(polygon1MaxX < polygon2MinX)
                    && !(polygon1MinX > polygon2MaxX)
                    && !(polygon1MaxY < polygon2MinY)
                    && !(polygon1MinY > polygon2MaxY);
        }
    
        /**
         * 获取线段集合
         *
         * @param polygon 多边形
         * @return 线段集合
         */
        private static List<LineSegment> getLineSegment(Polygon polygon) {
            List<LineSegment> lineSegments = new ArrayList<>();
            List<Point> points = polygon.getPoints();
            // 依次链接,形成线段
            for (int i = 0; i < points.size() - 1; i++) {
                Point previousElement = points.get(i);
                Point lastElement = points.get(i + 1);
                lineSegments.add(new LineSegment(previousElement, lastElement));
            }
            // 最后一组线段(最后一个点和初始点形成最后一条线段,形成闭环)
            if (lineSegments.size() > 0) {
                Point previousElement = points.get(points.size() - 1);
                Point lastElement = points.get(0);
                lineSegments.add(new LineSegment(previousElement, lastElement));
            }
            return lineSegments;
        }
    
        /**
         * 2、线段集合之间是否存在相交关系
         *
         * @param lineSegments1 线段集合1(其中一个多边形的线段集合)
         * @param lineSegments2 线段集合2(另一个多边形的线段集合)
         * @return boolean
         */
        private static boolean crossJudgment(List<LineSegment> lineSegments1, List<LineSegment> lineSegments2) {
            for (LineSegment lineSegment1 : lineSegments1) {
                for (LineSegment lineSegment2 : lineSegments2) {
                    // 任意一组线段相交及多边形相交,返回相交
                    if (calculationLineSegmentCrossing(lineSegment1, lineSegment2)) {
                        return true;
                    }
                }
            }
            return false;
        }
    
        /**
         * 线段是否相交(向量叉乘判断)
         *
         * @param lineSegment1 线段1
         * @param lineSegment2 线段2
         * @return boolean
         */
        private static boolean calculationLineSegmentCrossing(LineSegment lineSegment1, LineSegment lineSegment2) {
            // 如果存在任意一点在对方线段上,则相交
            if (isPointOnline(lineSegment1, lineSegment2)) {
                return true;
            }
            // 当不存端点在线段上,则进行交叉相交判断
            // A点
            Point aPoint = lineSegment1.getPrePoint();
            // B点
            Point bPoint = lineSegment1.getLastPoint();
            // C点
            Point cPoint = lineSegment2.getPrePoint();
            // D点
            Point dPoint = lineSegment2.getLastPoint();
            // AB向量叉乘AC向量
            double bc = crossProduct(aPoint, bPoint, aPoint, cPoint);
            // AB向量叉乘AD向量
            double bd = crossProduct(aPoint, bPoint, aPoint, dPoint);
            // CD向量叉乘CA向量
            double da = crossProduct(cPoint, dPoint, cPoint, aPoint);
            // CD向量叉乘CB向量
            double db = crossProduct(cPoint, dPoint, cPoint, bPoint);
            return bc * bd < 0 && da * db < 0;
        }
    
        /**
         * 两线段是否存在点在对方线段上
         *
         * @param lineSegment1 线段1
         * @param lineSegment2 线段2
         * @return boolean
         */
        private static boolean isPointOnline(LineSegment lineSegment1, LineSegment lineSegment2) {
            return isExistTrue(new boolean[]{
                    isCollinearIntersection(lineSegment1.getPrePoint(), lineSegment2),
                    isCollinearIntersection(lineSegment1.getLastPoint(), lineSegment2),
                    isCollinearIntersection(lineSegment2.getPrePoint(), lineSegment1),
                    isCollinearIntersection(lineSegment2.getLastPoint(), lineSegment1)});
        }
    
        /**
         * 点是否在线段上
         *
         * @param point            点
         * @param lineSegmentStart 线段起始点
         * @param lineSegmentEnd   线段尾点
         * @return boolean
         */
        private static boolean isCollinearIntersection(Point point, Point lineSegmentStart, Point lineSegmentEnd) {
            // 排除在延长线上的情况
            if (point.getX() >= Math.min(lineSegmentStart.getX(), lineSegmentEnd.getX())
                    && point.getX() <= Math.max(lineSegmentStart.getX(), lineSegmentEnd.getX())
                    && point.getY() >= Math.min(lineSegmentStart.getY(), lineSegmentEnd.getY())
                    && point.getY() <= Math.max(lineSegmentStart.getY(), lineSegmentEnd.getY())) {
                // 任意两点之间形成的向量叉乘等于0,表示在线段上或延长线上(三点共线)
                return crossProduct(point, lineSegmentStart, point, lineSegmentEnd) == 0;
            }
            return false;
        }
    
        /**
         * 点是否在线段上
         *
         * @param point       点
         * @param lineSegment 线段
         * @return boolean
         */
        private static boolean isCollinearIntersection(Point point, LineSegment lineSegment) {
            return isCollinearIntersection(point, lineSegment.getPrePoint(), lineSegment.getLastPoint());
        }
    
        /**
         * 3、多边形polygon的所有点是都在另一个多边形内部(包含关系)
         *
         * @param polygon      被包含(内部)多边形
         * @param lineSegments 包含(外部)多边形所有线段集合
         * @return boolean
         */
        private static boolean includeRelation(Polygon polygon, List<LineSegment> lineSegments) {
            List<Point> points = polygon.getPoints();
            // 所有点在内部或者线段上才算包含,返回包含关系,只要一个不满足,则返回不包含关系
            for (Point point : points) {
                if (!pointInPolygon(point, lineSegments)) {
                    return false;
                }
            }
            return true;
        }
    
        /**
         * 判断某个点是否在多边形内部
         *
         * @param point        点
         * @param lineSegments 多边形线段集合
         * @return boolean
         */
        private static boolean pointInPolygon(Point point, List<LineSegment> lineSegments) {
            // 点坐标
            double x = point.getX();
            double y = point.getY();
            // 交点个数
            int intersectionNum = 0;
            // 判断射线与多边形的交点个数
            for (LineSegment seg : lineSegments) {
                // 如果点在多边形边线上,则算在多边形内部
                if (isCollinearIntersection(point, seg.getPrePoint(), seg.getLastPoint())) {
                    return true;
                }
                double maxY = Math.max(seg.getPrePoint().getY(), seg.getLastPoint().getY());
                double minY = Math.min(seg.getPrePoint().getY(), seg.getLastPoint().getY());
                if (y >= minY && y < maxY) {
                    // 计算交点X坐标
                    double intersectionPointX = (y - seg.getPrePoint().getY()) * (seg.getLastPoint().getX() - seg.getPrePoint().getX())
                            / (seg.getLastPoint().getY() - seg.getPrePoint().getY()) + seg.getPrePoint().getX();
                    if (x > intersectionPointX) {
                        intersectionNum++;
                    }
                }
            }
            return intersectionNum % 2 != 0;
        }
    
        /**
         * 向量叉乘
         *
         * @param point1Start 向量1起点
         * @param point1End   向量1尾点
         * @param point2Start 向量2起点
         * @param point2End   向量2尾点
         * @return 向量叉乘结果
         */
        private static double crossProduct(Point point1Start, Point point1End, Point point2Start, Point point2End) {
            // 向量a
            double aVectorX = point1End.getX() - point1Start.getX();
            double aVectorY = point1End.getY() - point1Start.getY();
            // 向量b
            double bVectorX = point2End.getX() - point2Start.getX();
            double bVectorY = point2End.getY() - point2Start.getY();
            // 向量a叉乘向量b
            return aVectorX * bVectorY - bVectorX * aVectorY;
        }
    
        /**
         * 是否存在空对象
         *
         * @param objects 对象集合
         * @return boolean
         */
        private static boolean isExistNull(Object... objects) {
            for (Object object : objects) {
                if (object == null) {
                    return true;
                }
            }
            return false;
        }
    
        /**
         * 是否存在空集合
         *
         * @param collections 集合对象
         * @return boolean
         */
        private static boolean isExistNullOrEmpty(Collection<?>... collections) {
            for (Collection<?> collection : collections) {
                if (collection == null || collection.isEmpty()) {
                    return true;
                }
            }
            return false;
        }
    
        /**
         * 是否存在true
         *
         * @param booleans 布尔集合
         * @return boolean
         */
        private static boolean isExistTrue(boolean[] booleans) {
            for (boolean bool : booleans) {
                if (bool) {
                    return true;
                }
            }
            return false;
        }
    
        /**
         * 点
         */
        @Data
        @AllArgsConstructor
        @NoArgsConstructor
        private static class Point {
            private double x;
            private double y;
        }
    
        /**
         * 线段
         */
        @Data
        @AllArgsConstructor
        @NoArgsConstructor
        private static class LineSegment {
            private Point prePoint;
            private Point lastPoint;
        }
    
        /**
         * 多边形
         */
        @Data
        @AllArgsConstructor
        @NoArgsConstructor
        @Accessors(chain = true)
        private static class Polygon {
            private List<Point> points;
        }
    }
    

     

    展开全文
  • * 用于点与多边形位置关系判断 * * @author liuwei * @date 2015年4月9日13:29:21 */ public class GraphUtils { /** * 判断点是否在圆形内 (俩点距离小于半径) */ public static boolean ...

    废话不多说,直接看代码

    资料来源:http://paulbourke.net/geometry/polygonmesh/index.html#insidepoly

    package com.xxx.utils.map;
    
    import java.util.Arrays;
    
    import com.xxx.bo.Point;
    
    
    /**
     * 用于点与多边形位置关系的判断
     * 
     * @author liuwei
     * @date 2015年4月9日13:29:21
     */
    public class GraphUtils {
    
    	/**
    	 * 判断点是否在圆形内 (俩点距离小于半径)
    	 */
    	public static boolean isPointInCircle(Point point, Point boundary, Double radius) {
    
    		if (boundary != null && point != null && radius != null && radius >= 0) {
    			double number = PointMath.distanceOfTwoPositionNew(point, boundary);
    
    			return radius >= number;
    		} else {
    			return false;
    		}
    
    	}
    
    	/**
    	 * 判断点是否在多边形内(基本思路是用交点法)
    	 * 
    	 * @param point
    	 * @param boundaryPoints
    	 * @return
    	 */
    	public static boolean isPointInPolygon(Point point, Point[] boundaryPoints) {
    		// 防止第一个点与最后一个点相同
    		if (boundaryPoints != null && boundaryPoints.length > 0
    				&& boundaryPoints[boundaryPoints.length - 1].equals(boundaryPoints[0])) {
    			boundaryPoints = Arrays.copyOf(boundaryPoints, boundaryPoints.length - 1);
    		}
    		int pointCount = boundaryPoints.length;
    
    		// 首先判断点是否在多边形的外包矩形内,如果在,则进一步判断,否则返回false
    		if (!isPointInRectangle(point, boundaryPoints)) {
    			return false;
    		}
    
    		// 如果点与多边形的其中一个顶点重合,那么直接返回true
    		for (int i = 0; i < pointCount; i++) {
    			if (point.equals(boundaryPoints[i])) {
    				return true;
    			}
    		}
    
    		/**
    		 * 基本思想是利用X轴射线法,计算射线与多边形各边的交点,如果是偶数,则点在多边形外,否则在多边形内。还会考虑一些特殊情况,如点在多边形顶点上
    		 * , 点在多边形边上等特殊情况。
    		 * http://paulbourke.net/geometry/polygonmesh/index.html#insidepoly
    		 */
    		// X轴射线与多边形的交点数
    		int intersectPointCount = 0;
    		// X轴射线与多边形的交点权值
    		float intersectPointWeights = 0;
    		// 浮点类型计算时候与0比较时候的容差
    		double precision = 2e-10;
    		// 边P1P2的两个端点
    		Point point1 = boundaryPoints[0], point2;
    		// 循环判断所有的边
    		for (int i = 1; i <= pointCount; i++) {
    			point2 = boundaryPoints[i % pointCount];
    
    			/**
    			 * 如果点的y坐标在边P1P2的y坐标开区间范围之外,那么不相交。
    			 */
    			if (point.getLat() < Math.min(point1.getLat(), point2.getLat())
    					|| point.getLat() > Math.max(point1.getLat(), point2.getLat())) {
    				point1 = point2;
    				continue;
    			}
    
    			/**
    			 * 此处判断射线与边相交
    			 */
    			if (point.getLat() > Math.min(point1.getLat(), point2.getLat())
    					&& point.getLat() < Math.max(point1.getLat(), point2.getLat())) {// 如果点的y坐标在边P1P2的y坐标开区间内
    				if (point1.getLng() == point2.getLng()) {// 若边P1P2是垂直的
    					if (point.getLng() == point1.getLng()) {
    						// 若点在垂直的边P1P2上,则点在多边形内
    						return true;
    					} else if (point.getLng() < point1.getLng()) {
    						// 若点在在垂直的边P1P2左边,则点与该边必然有交点
    						++intersectPointCount;
    					}
    				} else {// 若边P1P2是斜线
    					if (point.getLng() <= Math.min(point1.getLng(), point2.getLng())) {// 点point的x坐标在点P1和P2的左侧
    						++intersectPointCount;
    					} else if (point.getLng() > Math.min(point1.getLng(), point2.getLng())
    							&& point.getLng() < Math.max(point1.getLng(), point2.getLng())) {// 点point的x坐标在点P1和P2的x坐标中间
    						double slopeDiff = 0.0d;
    						if (point1.getLat() > point2.getLat()) {
    							slopeDiff = (point.getLat() - point2.getLat()) / (point.getLng() - point2.getLng())
    									- (point1.getLat() - point2.getLat()) / (point1.getLng() - point2.getLng());
    						} else {
    							slopeDiff = (point.getLat() - point1.getLat()) / (point.getLng() - point1.getLng())
    									- (point2.getLat() - point1.getLat()) / (point2.getLng() - point1.getLng());
    						}
    						if (slopeDiff > 0) {
    							if (slopeDiff < precision) {// 由于double精度在计算时会有损失,故匹配一定的容差。经试验,坐标经度可以达到0.0001
    								// 点在斜线P1P2上
    								return true;
    							} else {
    								// 点与斜线P1P2有交点
    								intersectPointCount++;
    							}
    						}
    					}
    				}
    			} else {
    				// 边P1P2水平
    				if (point1.getLat() == point2.getLat()) {
    					if (point.getLng() <= Math.max(point1.getLng(), point2.getLng())
    							&& point.getLng() >= Math.min(point1.getLng(), point2.getLng())) {
    						// 若点在水平的边P1P2上,则点在多边形内
    						return true;
    					}
    				}
    				/**
    				 * 判断点通过多边形顶点
    				 */
    				if (((point.getLat() == point1.getLat() && point.getLng() < point1.getLng()))
    						|| (point.getLat() == point2.getLat() && point.getLng() < point2.getLng())) {
    					if (point2.getLat() < point1.getLat()) {
    						intersectPointWeights += -0.5;
    					} else if (point2.getLat() > point1.getLat()) {
    						intersectPointWeights += 0.5;
    					}
    				}
    			}
    			point1 = point2;
    		}
    
    		if ((intersectPointCount + Math.abs(intersectPointWeights)) % 2 == 0) {// 偶数在多边形外
    			return false;
    		} else { // 奇数在多边形内
    			return true;
    		}
    	}
    
    	/**
    	 * 判断点是否在矩形内在矩形边界上,也算在矩形内(根据这些点,构造一个外包矩形)
    	 * 
    	 * @param point
    	 *            点对象
    	 * @param boundaryPoints
    	 *            矩形边界点
    	 * @return
    	 */
    	public static boolean isPointInRectangle(Point point, Point[] boundaryPoints) {
    		Point southWestPoint = getSouthWestPoint(boundaryPoints); // 西南角点
    		Point northEastPoint = getNorthEastPoint(boundaryPoints); // 东北角点
    		return (point.getLng() >= southWestPoint.getLng() && point.getLng() <= northEastPoint.getLng()
    				&& point.getLat() >= southWestPoint.getLat() && point.getLat() <= northEastPoint.getLat());
    
    	}
    
    	/**
    	 * 根据这组坐标,画一个矩形,然后得到这个矩形西南角的顶点坐标
    	 * 
    	 * @param vertexs
    	 * @return
    	 */
    	private static Point getSouthWestPoint(Point[] vertexs) {
    		double minLng = vertexs[0].getLng(), minLat = vertexs[0].getLat();
    		for (Point bmapPoint : vertexs) {
    			double lng = bmapPoint.getLng();
    			double lat = bmapPoint.getLat();
    			if (lng < minLng) {
    				minLng = lng;
    			}
    			if (lat < minLat) {
    				minLat = lat;
    			}
    		}
    		return new Point(minLng, minLat);
    	}
    
    	/**
    	 * 根据这组坐标,画一个矩形,然后得到这个矩形东北角的顶点坐标
    	 * 
    	 * @param vertexs
    	 * @return
    	 */
    	private static Point getNorthEastPoint(Point[] vertexs) {
    		double maxLng = 0.0d, maxLat = 0.0d;
    		for (Point bmapPoint : vertexs) {
    			double lng = bmapPoint.getLng();
    			double lat = bmapPoint.getLat();
    			if (lng > maxLng) {
    				maxLng = lng;
    			}
    			if (lat > maxLat) {
    				maxLat = lat;
    			}
    		}
    		return new Point(maxLng, maxLat);
    	}
    
    }
    

    这是基本代码,大楷思路也都在这里面了。不太清楚的可以Q我851668663

    转载于:https://my.oschina.net/Thinkeryjgfn/blog/875245

    展开全文
  • 多边形多边形 位置关系判断

    千次阅读 2016-04-24 14:11:48
    C#判断点的位置方法一 public int isLeft(Point P0, Point P1,Point P2) { int abc= ((P1.X - P0.X) * (P2.Y - P0.Y) - (P2.X - P0.X) * (P1.Y - P0.Y)); return abc; } private bool ...

    C#判断点的位置方法一

    
    
    1. public int isLeft(Point P0, Point P1,Point P2)
    2. {
    3. int abc= ((P1.X - P0.X) * (P2.Y - P0.Y) - (P2.X - P0.X) * (P1.Y - P0.Y));
    4. return abc;
    5. }
    6. private bool PointInFences(Point pnt1, Point[] fencePnts)
    7. {
    8. int wn = 0,j=0; //wn 计数器 j第二个点指针
    9. for (int i = 0; i < fencePnts.Length; i++)
    10. {//开始循环
    11. if (i == fencePnts.Length - 1)
    12. j = 0;//如果 循环到最后一点第二个指针指向第一点
    13. else
    14. j = j + 1; //如果不是,则找下一点
    15. if (fencePnts[i].Y < = pnt1.Y) // 如果多边形的点 小于等于 选定点的 Y 坐标
    16. {
    17. if (fencePnts[j].Y > pnt1.Y) // 如果多边形的下一点 大于于 选定点的 Y 坐标
    18. {
    19. if (isLeft(fencePnts[i], fencePnts[j], pnt1) > 0)
    20. {
    21. wn++;
    22. }
    23. }
    24. }
    25. else
    26. {
    27. if (fencePnts[j].Y < = pnt1.Y)
    28. {
    29. if (isLeft(fencePnts[i], fencePnts[j], pnt1) < 0)
    30. {
    31. wn--;
    32. }
    33. }
    34. }
    35. }
    36. if (wn == 0)
    37. return false;
    38. else
    39. return true;
    40. }

    C#判断点的位置方法二——c#内置函数:

    
    
    1. GraphicsPath myGraphicsPath = new GraphicsPath();
    2. Region myRegion=new Region();
    3. myGraphicsPath.Reset();
    4. Point inputponint = new Point(inputx, inputy);
    5. myGraphicsPath.AddPolygon(points);//points);
    6. myRegion.MakeEmpty();
    7. myRegion.Union(myGraphicsPath);
    8. //返回判断点是否在多边形里
    9. bool myPoint= myRegion.IsVisible(inputponint);
    10. this.lblx.Text = myPoint.ToString();

    图形算法:

    1,面积法。就是看所有边和目标点组成的三角形面积和是否等于总的多边形面积,如果相等,则在内部。反之在外部。这种方法计算量较大,用到的主要计算是查乘。

    2,夹角和法。参见三楼,判断所有边和目标点的夹角和是否为360度。计算量比上面这种方法稍微小点,用到主要是点乘和求模计算。

    3,引射线法。就是从该点出发引一条射线,看这条射线和所有边的交点数目。如果有奇数个交点,则说明在内部,如果有偶数个交点,则说明在外部。这是所有方法中计算量最小的方法,在光线追踪算法中有大量的应用。

    在C#中的话,有一个Region类,可以直接调用IsVisible判断是否在这个区域内部,我估计内部的实现应该是上面说的第三种方法。主要看你的需求是哪种输入了,如果在C#中,你完全可以用Region类来隐藏内部实现。

    C#判断点的位置的另外一种解决方法:

    1.已知点point(x,y)和多边形Polygon(x1,y1;x2,y2;….xn,yn;);

    2.以point为起点,以无穷远为终点作平行于X轴的直线line(x,y; -∞,y);

    3.循环取得(for(i=0;i< n;i++))多边形的每一条边side(xi,yi;xi+1,yi+1),且判断是否平行于X轴,如果平行continue,否则,i++;

    4. 同时判断point(x,y)是否在side上,如果是,则返回1(点在多边形上),否则继续下面的判断;

    5.判断线side与line是否有交点,如果有则count++,否则,i++。

    6.判断交点的总数,如果为奇数则返回0(点在多边形内),偶数则返回2(点在多边形外)。

    代码:

    
    
    1. const double INFINITY = 1e10;
    2. const double ESP = 1e-5;
    3. const int MAX_N = 1000;
    4. struct Point {
    5. double x, y;
    6. };
    7. struct LineSegment {
    8. Point pt1, pt2;
    9. };
    10. typedef vector< Point> Polygon;
    11. // 计算叉乘 |P0P1| × |P0P2|
    12. double Multiply(Point p1, Point p2, Point p0)
    13. {
    14. return ( (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y) );
    15. }
    16. // 判断线段是否包含点point
    17. bool IsOnline(Point point, LineSegment line)
    18. {
    19. return( ( fabs(Multiply(line.pt1, line.pt2, point)) < ESP ) &&
    20. ( ( point.x - line.pt1.x ) * ( point.x - line.pt2.x ) < = 0 ) &&
    21. ( ( point.y - line.pt1.y ) * ( point.y - line.pt2.y ) < = 0 ) );
    22. }
    23. // 判断线段相交
    24. bool Intersect(LineSegment L1, LineSegment L2)
    25. {
    26. return( (max(L1.pt1.x, L1.pt2.x) >= min(L2.pt1.x, L2.pt2.x)) &&
    27. (max(L2.pt1.x, L2.pt2.x) >= min(L1.pt1.x, L1.pt2.x)) &&
    28. (max(L1.pt1.y, L1.pt2.y) >= min(L2.pt1.y, L2.pt2.y)) &&
    29. (max(L2.pt1.y, L2.pt2.y) >= min(L1.pt1.y, L1.pt2.y)) &&
    30. (Multiply(L2.pt1, L1.pt2, L1.pt1) * Multiply(L1.pt2, L2.pt2, L1.pt1) >= 0) &&
    31. (Multiply(L1.pt1, L2.pt2, L2.pt1) * Multiply(L2.pt2, L1.pt2, L2.pt1) >= 0)
    32. );
    33. }
    34. // 判断点在多边形内
    35. bool InPolygon(const Polygon& polygon, Point point)
    36. {
    37. int n = polygon.size();
    38. int count = 0;
    39. LineSegment line;
    40. line.pt1 = point;
    41. line.pt2.y = point.y;
    42. line.pt2.x = - INFINITY;
    43. forint i = 0; i < n; i++ ) {
    44. // 得到多边形的一条边
    45. LineSegment side;
    46. side.pt1 = polygon[i];
    47. side.pt2 = polygon[(i + 1) % n];
    48. if( IsOnline(point, side) ) {
    49. return1 ;
    50. }
    51. // 如果side平行x轴则不作考虑
    52. if( fabs(side.pt1.y - side.pt2.y) < ESP ) {
    53. continue;
    54. }
    55. if( IsOnline(side.pt1, line) ) {
    56. if( side.pt1.y > side.pt2.y ) count++;
    57. else if( IsOnline(side.pt2, line) ) {
    58. if( side.pt2.y > side.pt1.y ) count++;
    59. else if( Intersect(line, side) ) {
    60. count++;
    61. }
    62. }
    63. if ( count % 2 == 1 ) {return 0;}
    64. else { return 2;}
    65. }
    66. }


    protected override void OnPaint(PaintEventArgs e)

            {

                base.OnPaint(e);

                Graphics g = e.Graphics;

                GraphicsPath gp1 = new GraphicsPath();

                GraphicsPath gp2 = new GraphicsPath();

                gp1.AddPolygon(new Point[] { new Point(100, 0), new Point(150, 100), new Point(200, 0),

                                             new Point(100, 300), new Point(150, 200), new Point(200, 300)});

                gp2.AddRectangle(new Rectangle(new Point(0,50),new Size(300,200)));

                g.FillPath(Brushes.Green, gp2);

                g.FillPath(Brushes.GreenYellow, gp1);

                Region region = new Region(gp1);

                region.Intersect(gp2);  //求长方形和多边形的交集

                g.FillRegion(Brushes.Red, region);//用红色填充

            }



    最近项目需要判断两个图形要素是否相交的问题:
       一个图形元素是GraphicsPath 构造的闭合多边形,另一个图形元素是矩形,然后用region.interSect(矩形)来获取两者的交集元素,但明明是有交集的,返回的交集却为空。
       可能的原因是构建图形要素的值太小造成的返回结果不准确,创建图形要素的坐标限定在:{x:(-180,180)} {y:(-90,90)}
        请问有什么办法可以使下面的交集能够正确返回?
       注:下面的两图形元素肯定是有交集的。

            public void intersectTestx(PaintEventArgs e)
            {
                PointF[] pts = new PointF[4];
                pts[0] = new PointF(115.116066f, 40.48523f);
                pts[1] = new PointF(115.879951f, 40.5706635f);
                pts[2] = new PointF(116.040909f, 39.998024f);
                pts[3] = new PointF(115.283585f, 39.9120445f);
           //构建GraphicsPath对象
                GraphicsPath gpTmp1 = new GraphicsPath(System.Drawing.Drawing2D.FillMode.Alternate);
                gpTmp1.AddPolygon(pts);
           //构建region对象
                Region rgnTmp = new Region(gpTmp1);

                SolidBrush myBrush1 = new SolidBrush(Color.Black);
                e.Graphics.FillRegion(myBrush1, rgnTmp);
           //构建矩形对象 
                RectangleF recOri = new RectangleF(115.67f, 40.27f, 0.29f, 0.36f);

                e.Graphics.DrawRectangle(Pens.Red, Rectangle.Round(recOri));
           //获取矩形对象和region对象的交集            
                rgnTmp.Intersect(recOri);

                // Fill the intersection area of 

    展开全文
  • 判断两个多边形是否相交相交

    千次阅读 2020-04-22 15:49:00
    //判断两多边形线段是否相交 function isSegmentsIntersectant(segA, segB) {//线线 const abc = (segA[0][0] - segB[0][0]) * (segA[1][1] - segB[0][1]) - (segA[0][1] - segB[0][1]) * (segA[1][0]...
  • 判断点与多边形位置关系

    千次阅读 2014-10-30 11:37:48
    遇到一个需求,给定一个点的坐标以及一个多边形的所有顶点坐标。要求能够判断这个点是在多边形内,还是在多边形外? 【参考文献】: 1、条直线的关系 ...2、点与多边形的关系 ...
  • 1.判断两点之间的距离 2.判断点与多边形关系
  • emm,我用过两个库,可以解决这个问题: 第一个: opencv: 这是一个图像处理库 import cv2 cv2.pointPolygonTest(InputArray contour, Point2f pt, bool measureDist) #根据最后一个参数: #如果最后一个参数为真: ...
  • 给出一n边形的n顶点坐标 然后给出一点的坐标,判断点与多边形位置关系 题目分析: 对于在边上的情况很好搞,直接遍历n条边,然后依次用叉积判断即可 对于此点在多边形内部还是外部的问题 可以利用...
  • 0 题目: 询问给出的多边形是凸多边形还是凹多边形(两者区别: if there exist any two interior points in the hole that, if... cross one or more edges of the hole,如果存在有任意两个顶点的连线会经过边的情
  • 判断点与多边形关系,是计算几何的经典问题,点与多边形关系可以分为:点在多边形内(inside)、点在多边形外(outside)以及点在多边形的边上(onside)三种。 本文介绍解决该问题的向量积方法。
  • 判断点与多边形关系

    2019-09-21 23:41:57
    引射线法:从被判断的点发射一条射线,与多边形有奇数交点则在多边形内 面积和法:从多边形一顶点出发,计算被判断的点和相邻点组成的三角形的面积和(可用 1/2 * 向量叉乘求),面积和与多边形面积相等则在...
  • 判断两个线段的相对位置关系

    千次阅读 2018-08-23 09:16:09
    抛出3问题,先自己理解理解,我们用叉积的办法来判断条线段的位置关系 就是向量p0p1与p0p2的叉积如果 &gt;0则向量p0p1在向量p0p2的顺时针方向 &lt;0则向量p0p1在向量p0p2的逆时针方向 =0的话...
  • 判断2个多边形相交

    千次阅读 2020-03-06 15:21:32
    2个多边形的顶点是否在另一个多边形的内部。 关于这2个条件的判断: 《碰撞检测:判断点是否在多边形内部》 https://blog.csdn.net/StevenKyleLee/article/details/88044589 《碰撞检测:判断线段相交》 ...
  • C++ ARX二次开发点和闭合多段线的位置关系 二、本节要讲解的知识点 结合自己的业务场景,想想自己开发中可能碰到的点和闭合多段线相对关系的需求:统计多段线内部的所有图块;还可以拓展判断任意曲线跟多段线的...
  • 判断个多边形是凸多边形还是凹多边形 输入: 输入包含多组测试数据,每组数据占2行,首先一行是一个整数n,表示多边形顶点的个数,然后一行是2×n个整数,表示逆时针顺序的n个顶点的坐标(xi,yi),n为0的...
  • 终极大招来了,射线法是解决这一问题的最优方法,其他方法仅具有理论意义,如果工程应用的话,知道这方法就够了。 射线法的思想是:以目标点为端点引一...如果交点数为奇数,则点在多边形部,反之则在多边形外部。
  • 最近在做一些简单的图像对比工作,总结了一些GDI+...判断Rectangl与多边形关系 /// <summary> /// 是否包含输入范围 /// </summary> /// <param name="rectangle">要对比的范围<...
  • 铅垂线内点法实现判断点与多边形区域之间的位置关系。 铅垂线内点法的基本思想是从待判别点向外引铅垂线,计算其与多边形交点的个数。若交点数为奇数,则点在多边形内;若交点数为偶数,则该点在多边形外...
  • “角度和法”的思路是:多边形内的点,与所有顶点顺次连接形成向量的夹角之和为2π。
  • 抛出3问题,先自己理解理解,我们用叉积的办法来判断条线段的位置关系   就是向量p0p1与p0p2的叉积如果 &gt;0则向量p0p1在向量p0p2的顺时针方向 &lt;0则向量p0p1在向量p0p2的逆时针方向 =0的...
  • 判断个多边形的凸凹性

    千次阅读 2020-04-20 09:42:42
    如果把一个多边形的所有边中,有一条边向方无限延长成为一直线时,其他各边都在此直线的同旁,那么这个多边形就叫做凸多边形。 凸多边形是一个内部为凸集的简单多边形。   简单多边形的下列性质与其凸...
  • 碰撞检测:判断2个多边形相交

    千次阅读 2019-03-02 14:41:09
    2个多边形的顶点是否在另一个多边形的内部。 关于这2个条件的判断: 《碰撞检测:判断点是否在多边形内部》 https://blog.csdn.net/StevenKyleLee/article/details/88044589 《碰撞检测:判断线段相交》 ...
  • 1.声明 此处的简单多边形,是只常见的凸多边形,比如三角形、长方形、五边形、6边形。...每个vector变量,就存两个坐标:横和纵 bool isOnside(vector<int>& A, vector<int>& B, vector<in
  • 判断两条直线的位置关系

    千次阅读 2019-03-07 09:53:31
    最近在看任意两个多边形的交并比,
  • 射线法判断点与多边形关系原理如下: 从待判断点引出一条射线,射线与多边形相交,如果交点为偶数,则点不在多边形内,如果交点为奇数,则点在多边形内。 原理虽是这样,有些细节还是要注意一下,比如射线过多边形...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,781
精华内容 3,912
关键字:

判断两个多边形的位置关系