需求是:一个点(经纬度)是否在一个多边形内部,多边形有多个点构成,每个点是一个实际的经纬度坐标,有多个点构成一个多边形，
算法数学上实现思路: 判断一个点是在一个多边形内部的集中情况
第一:目标点在多边形的某一个顶点上,我们认为目标点在多边形内部
第二:目标点在多边形的任意一天边上,我们认为目标点在多边形内部
第三:这种情况就比较复杂了,不在某天边上，也不和任何一个顶点重合.这时候就需要我们自己去算了，解决方案是将目标点的Y坐标与多边形的每一个点进行比较，我们会得到一个目标点所在的行与多边形边的交点的列表。如果目标点的两边点的个数都是奇数个则该目标点在多边形内，否则在多边形外。
这种算法适合凸多边形也适合凹多边形，所以是一种通用的算法，同时也解决了多边形的点的顺序不同导致的形状不同，比如一个五边形，可以是凸五边形，也可以是一个凹五边形，这个根据点的位置和顺序决定的。
有了数学上的实现思路，辣么我们就可以用java 或者去他语言去实现一个点(经纬度)是否在一个多边形内部了(多个点构成)。
我们先写一个 对点和线的一些公用方法，
package cn.liuzw.point;
import java.util.ArrayList;
/**
* <span style="font-family: Arial; font-size: 14px; line-height: 26px;">点和线的一些公用方法</span><br/>
*
* @author liuZhiwei
* 2016年8月6日 下午3:48:38
*/
public class Point {
/**
* 是否有 横断<br/>
* 参数为四个点的坐标
* @param px1
* @param py1
* @param px2
* @param py2
* @param px3
* @param py3
* @param px4
* @param py4
* @return
*/
public boolean isIntersect ( double px1 , double py1 , double px2 , double py2 , double px3 , double py3 , double px4 ,
double py4 )
{
boolean flag = false;
double d = (px2 - px1) * (py4 - py3) - (py2 - py1) * (px4 - px3);
if ( d != 0 )
{
double r = ((py1 - py3) * (px4 - px3) - (px1 - px3) * (py4 - py3)) / d;
double s = ((py1 - py3) * (px2 - px1) - (px1 - px3) * (py2 - py1)) / d;
if ( (r >= 0) && (r <= 1) && (s >= 0) && (s <= 1) )
{
flag = true;
}
}
return flag;
}
/**
* 目标点是否在目标边上边上<br/>
*
* @param px0 目标点的经度坐标
* @param py0 目标点的纬度坐标
* @param px1 目标线的起点(终点)经度坐标
* @param py1 目标线的起点(终点)纬度坐标
* @param px2 目标线的终点(起点)经度坐标
* @param py2 目标线的终点(起点)纬度坐标
* @return
*/
public boolean isPointOnLine ( double px0 , double py0 , double px1 , double py1 , double px2 , double py2 )
{
boolean flag = false;
double ESP = 1e-9;//无限小的正数
if ( (Math.abs(Multiply(px0, py0, px1, py1, px2, py2)) < ESP) && ((px0 - px1) * (px0 - px2) <= 0)
&& ((py0 - py1) * (py0 - py2) <= 0) )
{
flag = true;
}
return flag;
}
public double Multiply ( double px0 , double py0 , double px1 , double py1 , double px2 , double py2 )
{
return ((px1 - px0) * (py2 - py0) - (px2 - px0) * (py1 - py0));
}
/**
* 判断目标点是否在多边形内(由多个点组成)<br/>
*
* @param px 目标点的经度坐标
* @param py 目标点的纬度坐标
* @param polygonXA 多边形的经度坐标集合
* @param polygonYA 多边形的纬度坐标集合
* @return
*/
public boolean isPointInPolygon ( double px , double py , ArrayList<Double> polygonXA , ArrayList<Double> polygonYA )
{
boolean isInside = false;
double ESP = 1e-9;
int count = 0;
double linePoint1x;
double linePoint1y;
double linePoint2x = 180;
double linePoint2y;
linePoint1x = px;
linePoint1y = py;
linePoint2y = py;
for (int i = 0; i < polygonXA.size() - 1; i++)
{
double cx1 = polygonXA.get(i);
double cy1 = polygonYA.get(i);
double cx2 = polygonXA.get(i + 1);
double cy2 = polygonYA.get(i + 1);
//如果目标点在任何一条线上
if ( isPointOnLine(px, py, cx1, cy1, cx2, cy2) )
{
return true;
}
//如果线段的长度无限小(趋于零)那么这两点实际是重合的，不足以构成一条线段
if ( Math.abs(cy2 - cy1) < ESP )
{
continue;
}
//第一个点是否在以目标点为基础衍生的平行纬度线
if ( isPointOnLine(cx1, cy1, linePoint1x, linePoint1y, linePoint2x, linePoint2y) )
{
//第二个点在第一个的下方,靠近赤道纬度为零(最小纬度)
if ( cy1 > cy2 )
count++;
}
//第二个点是否在以目标点为基础衍生的平行纬度线
else if ( isPointOnLine(cx2, cy2, linePoint1x, linePoint1y, linePoint2x, linePoint2y) )
{
//第二个点在第一个的上方,靠近极点(南极或北极)纬度为90(最大纬度)
if ( cy2 > cy1 )
count++;
}
//由两点组成的线段是否和以目标点为基础衍生的平行纬度线相交
else if ( isIntersect(cx1, cy1, cx2, cy2, linePoint1x, linePoint1y, linePoint2x, linePoint2y) )
{
count++;
}
}
if ( count % 2 == 1 )
{
isInside = true;
}
return isInside;
}
}里面有三个方法，两个原子方法，一个主方法
第一个判断是否与横断 目标端和y轴 也就是东经0也叫西经180的一条经度线构成的一天平行于纬度(赤道)的一天线段和多边形的任意一天线段是否有横断。参数是四个点的坐标分别是目标点和目标点组成线段的一个点(在西经180度上) 多边形的任意连续的两个点(可以构成一条线段)
第二个是目标点是否在目标边上边上，
点三个是主方法，外接只需要调用这个方法，这个而方法的逻辑就是，第一步先判断目标点的坐标是否和多边形的任意一个顶点的坐标重合，如果重合直接放回true，说明目标点在该多边形内，如果都不重合，在判断是否在多边形的任意一条边上，如果在 返回true，如果以上两种情况都不成立在理由低三种算法，计算目标点平行于赤道的线和多边形的焦点，在判断焦点的个数。如果l两边的焦点是基数个返回true。
我可以写main方法去测试该程序。
package cn.liuzw.bean;
import java.util.Random;
/**
* 点实体类<br/>
*
* @author liuZhiwei
* 2016年8月15日 下午7:16:14
*/
public class Area {
public static Random rd=new Random();
public Double createDouble(){
return (double) rd.nextInt(1000);
}
public Area() {
this.px = createDouble();
this.py = createDouble();
}
public Area(Double px, Double py) {
super();
this.px = px;
this.py = py;
}
public Area(Double px, Double py, String name) {
super();
this.px = px;
this.py = py;
this.name = name;
}
private Double px;
private Double py;
private String name;
public Double getPx() {
return px;
}
public void setPx(Double px) {
this.px = px;
}
public Double getPy() {
return py;
}
public void setPy(Double py) {
this.py = py;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "Area [px=" + px + ", py=" + py + ", name=" + name + "]";
}
public String getPoint() {
StringBuffer buffer=new StringBuffer();
buffer.append("(").append(px).append(",").append(py).append(")");
return buffer.toString();
}
}main方法测试类
package cn.liuzw.test;
import java.util.ArrayList;
import java.util.List;
import cn.liuzw.bean.Area;
import cn.liuzw.point.Point;
public class GraphicalMain {
public static void main(String[] args) {
//(113.944421,22.528841) (113.94629,22.529208)
//isPointInPolygon(area.createDouble(),area.createDouble()); (114.082402,22.550271) 114.075323,22.543528)
isPointInPolygon(113.947871,22.52804);
}
private static Boolean isPointInPolygon( double px , double py ){
Area a1=new Area(113.941853,22.530777);
Area a3=new Area(113.94788,22.527597);
Area a2=new Area(113.940487,22.527789);
Area a4=new Area(113.947925,22.530618);
Area a5=new Area(113.941772,22.530727);
List<Area> areas=new ArrayList<Area>();
areas.add(a1);
areas.add(a2);
areas.add(a3);
areas.add(a4);
ArrayList<Double> polygonXA = new ArrayList<Double>();
ArrayList<Double> polygonYA = new ArrayList<Double>();
for(int i=0;i<areas.size();i++){
Area area=areas.get(i);
polygonXA.add(area.getPx());
polygonYA.add(area.getPy());
}
Point point=new Point();
Boolean flag= point.isPointInPolygon(px, py, polygonXA, polygonYA);
StringBuffer buffer=new StringBuffer();
buffer.append("目标点").append("(").append(px).append(",").append(py).append(")").append("\n");
buffer.append(flag?"在":"不在").append("\t").append("由\n");
for(int i=0;i<areas.size();i++){
Area area=areas.get(i);
buffer.append(area.getPoint()).append("; ");
//buffer.append("第"+i+"个点"+area.getPoint()).append("\n");
System.out.println("第"+(i+1)+"个点"+area.getPoint());
}
StringBuffer sb=new StringBuffer();
sb.append("目标点:").append("(").append(px).append(",").append(py).append(")").append("\n");
System.out.println(sb);
buffer.append(areas.size()).append("个点组成的").append(areas.size()).append("边行内");
System.out.println(buffer.toString());
return flag;
}
}需求是:一个点(经纬度)是否在一个多边形内部,多边形有多个点构成,每个点是一个实际的经纬度坐标,有多个点构成一个多边形，
需求是:一个点(经纬度)是否在一个多边形内部,多边形有多个点构成,每个点是一个实际的经纬度坐标,有多个点构成一个多边形，
算法数学上实现思路: 判断一个点是在一个多边形内部的集中情况
第一:目标点在多边形的某一个顶点上,我们认为目标点在多边形内部
第二:目标点在多边形的任意一天边上,我们认为目标点在多边形内部
第三:这种情况就比较复杂了,不在某天边上，也不和任何一个顶点重合.这时候就需要我们自己去算了，解决方案是将目标点的Y坐标与多边形的每一个点进行比较，我们会得到一个目标点所在的行与多边形边的交点的列表。如果目标点的两边点的个数都是奇数个则该目标点在多边形内，否则在多边形外。
