遇到一个需求，给定一个点的坐标以及一个多边形的所有顶点坐标。要求能够判断这个点是在多边形内，还是在多边形外？
【参考文献】：
1、两条直线的关系
http://www.cnblogs.com/devymex/archive/2010/08/19/1803885.html
2、点与多边形的关系
http://wenku.baidu.com/view/5e3913a2b0717fd5360cdccf.html?qq-pf-to=pcqq.c2c
经过在网上的一番搜索，发现目前比较通用的就是射线法，而我采用的就是X轴射线法。主要理论来源于西安交大的一篇论文（即参考文献的第二条）
代码讲解：
主要的类有两个：一个是坐标点的抽象类，另一个是位置关系判断工具类。
1、是坐标点的抽象类
package com.niux.crm.core.common.bmap;
/**
* 用于构造百度地图中的经纬度点
*
* @author zhengtian
* @date 2013-8-5 下午02:54:41
*/
public class BmapPoint {
private double lng;// 经度
private double lat;// 纬度
public BmapPoint() {
}
public BmapPoint(double lng, double lat) {
this.lng = lng;
this.lat = lat;
}
@Override
public boolean equals(Object obj) {
if (obj instanceof BmapPoint) {
BmapPoint bmapPoint = (BmapPoint) obj;
return (bmapPoint.getLng() == lng && bmapPoint.getLat() == lat) ? true : false;
} else {
return false;
}
}
public double getLng() {
return lng;
}
public void setLng(double lng) {
this.lng = lng;
}
public double getLat() {
return lat;
}
public void setLat(double lat) {
this.lat = lat;
}
}
2、位置关系判断工具类
点与多边形的位置关系的判定规则：1、，根据多边形的坐标，虚拟出一个外包矩形，主要是为了提前过滤不相关的点，减少运算量。2、然后判断是否有重合的点。3、判断点与斜线的交点。4、判断点过顶点的情况。5、判断点与边重合的情况。6、判断点在边上的情况。
其中点过顶点，以及点与边重合的情况，主要采用了加权边的思想，论文与代码中有注释。
package com.niux.crm.core.common.bmap;
import java.util.Arrays;
/**
* 用于点与多边形位置关系的判断
*
* @author zhengtian
* @date 2013-8-5 上午11:59:35
*/
public class GraphUtils {
/**
* 判断点是否在多边形内(基本思路是用交点法)
*
* @param point
* @param boundaryPoints
* @return
*/
public static boolean isPointInPolygon(BmapPoint point, BmapPoint[] 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轴射线法，计算射线与多边形各边的交点，如果是偶数，则点在多边形外，否则在多边形内。还会考虑一些特殊情况，如点在多边形顶点上
* ， 点在多边形边上等特殊情况。
*/
// X轴射线与多边形的交点数
int intersectPointCount = 0;
// X轴射线与多边形的交点权值
float intersectPointWeights = 0;
// 浮点类型计算时候与0比较时候的容差
double precision = 2e-10;
// 边P1P2的两个端点
BmapPoint 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(BmapPoint point, BmapPoint[] boundaryPoints) {
BmapPoint southWestPoint = getSouthWestPoint(boundaryPoints); // 西南角点
BmapPoint 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 BmapPoint getSouthWestPoint(BmapPoint[] vertexs) {
double minLng = vertexs[0].getLng(), minLat = vertexs[0].getLat();
for (BmapPoint bmapPoint : vertexs) {
double lng = bmapPoint.getLng();
double lat = bmapPoint.getLat();
if (lng < minLng) {
minLng = lng;
}
if (lat < minLat) {
minLat = lat;
}
}
return new BmapPoint(minLng, minLat);
}
/**
* 根据这组坐标，画一个矩形，然后得到这个矩形东北角的顶点坐标
*
* @param vertexs
* @return
*/
private static BmapPoint getNorthEastPoint(BmapPoint[] vertexs) {
double maxLng = 0.0d, maxLat = 0.0d;
for (BmapPoint bmapPoint : vertexs) {
double lng = bmapPoint.getLng();
double lat = bmapPoint.getLat();
if (lng > maxLng) {
maxLng = lng;
}
if (lat > maxLat) {
maxLat = lat;
}
}
return new BmapPoint(maxLng, maxLat);
}
}
分享到：
相关推荐
本文将深入探讨“点与多边形的位置关系”这一主题，尤其是如何判断一个点是否位于不规则多边形的内部或外部。 ### 基本概念 #### 点与多边形 - **点**：在二维空间中，一个点可以由其坐标(x, y)来定义。 - **...
可以支持所有的多边形情况
判断点P(x, y)与多边形的关系，主要有以下几种情况： 1. 点在多边形内部：一种常用的方法是射线法（Ray-Casting Algorithm），也称为Winding Number Test。从点P向任意方向画一条射线，统计这条射线与多边形边的交点...
判断点与多边形的关系，使用扫描线算法实现。图形界面演示测试结果。 实现语言：Python + wxPython
在VB（Visual Basic）编程环境中，点与多边形的关系判断是计算机图形学中的一个基本问题，尤其在游戏开发、地图应用或者可视化软件中尤为重要。这个话题涉及到如何确定一个二维平面上的点是否位于一个多边形内部。在...
在VB中，我们可以利用数学方法来解决这个问题，这通常是通过检测点与多边形边的关系来完成的。 首先，理解“点在多边形内”的定义：如果从点出发的射线与多边形的边相交的次数为奇数，那么点被判断为在多边形内部；...
（1）是否为凸多边形：前三个点计算三角形（封闭线的面积，用积分方式计算），以后每加一个点面积均应增加或至少相等。 （2）最后一个点是否在凸多边形内：同上方式计算加上这个点的多边形的面积，相等或减少表示...
总结来说，这段代码实现了判断一个点是否在由给定点集定义的凸多边形内的功能，利用了射线法通过计算多边形边与测试点的夹角总和来判断。如果夹角总和为 360 度，则点在多边形内部，否则在外部。
接下来，我们将讨论几种常见的点与多边形关系的判断方法： 1. **射线交叉法（Ray Casting Algorithm）**：这是最常用的判断点是否在多边形内的方法。从点出发，画一条水平射线（或任意非平行于多边形边界的射线）。...
高效计算点与多边形关系算法，可用于坐标点与区域的关系计算
在计算机图形学中，判断一个点是否位于一个多边形内部是一项基本任务，尤其在MFC（Microsoft Foundation Classes）框架下开发图形用户界面时。本文将详细介绍如何使用射线法（也称为穿越法或Winding Number Test）来...
### 知识点一：点与多边形的关系判断 #### 定义与背景 在计算机图形学、地理信息系统（GIS）以及许多其他领域中，经常需要确定一个点是否位于一个多边形内部、边界上还是外部。这种问题的解决方法对于路径规划、...
2. **APolygon.cs**：这可能是一个C#类，用于表示多边形，并可能包含一个或多个方法来处理点与多边形的关系，如`ContainsPoint(Point p)`，它会返回一个布尔值，指示点是否在多边形内。 3. **判断点在多边形内的...
包含：1....判断点是否在一个多边形区域内， 如果点位于多边形的顶点或边上，不算做点在多边形内，返回false8.判断点是否在多边形内，如果点位于多边形的顶点或边上，也算做点在多边形内，直接返回true
邻接边算法主要针对凸多边形，它检查点与多边形的每对邻接边之间的关系。如果点位于一对邻接边形成的夹角内，且与这两边不共线，那么点就在多边形内部。 在实际应用中，通常会根据多边形的类型和性能需求选择合适的...
8. **交互式应用**：如果是在Web环境下，可能需要将这个功能整合到前端JavaScript中，通过API与后端Java服务进行交互，实现用户在地图上点击时实时判断点是否在多边形内。 通过理解以上知识点，并参考`Demo`文件中...