/**
* Copyright (c) 2009-2011, chunquedong(YangJiandong)
*
* This file is part of ChunMap project
* Licensed under the GNU LESSER GENERAL PUBLIC LICENSE(Version >=3)
*
* History:
* 2010-05-05 Jed Young Creation
*/
package chunmap.model.algorithm;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import chunmap.model.coord.CoordSeqEditor;
import chunmap.model.coord.CoordinateSeq;
import chunmap.model.coord.CPoint;
import chunmap.model.elem.LineSegment;
import chunmap.model.elem.PointLineBag;
public class LineAlgorithm {
static public boolean containLineString(CoordinateSeq points, CoordinateSeq other)
{
//打断
CoordSeqEditor tLine = new CoordSeqEditor(other);
tLine.tryInsertAll(points);
// 片段在里面
for (int i = 0, n = tLine.size() - 1; i < n; i++)
{
LineSegment lseg = tLine.getLineSegment(i);
if (!containSegment(points, lseg))
{
return false;
}
}
return true;
}
// 直接包含线段，不考虑线段跨结点情况
static private boolean containSegment(CoordinateSeq points, LineSegment lseg)
{
for (int i = 0, n = points.size() - 1; i < n; i++)
{
LineSegment lseg2 = new LineSegment(points.getCoordinate(i), points.getCoordinate(i+1));
if (lseg2.containLineSegment(lseg))
{
return true;
}
}
return false;
}
static public boolean onLineString(CoordinateSeq points, CPoint p)
{
for (int i = 0, n = points.size() - 1; i < n; i++)
{
LineSegment lseg = new LineSegment(points.getCoordinate(i), points.getCoordinate(i+1));
if (lseg.onLineSegment(p))
return true;
}
return false;
}
//------------------------------------------------------------------------交集
public static PointLineBag intersection(CoordinateSeq me, CoordinateSeq l2)
{
PointLineBag geometrys = new PointLineBag();
List<MonotonyChain> chains1 = getMonotonyChains(me);
List<MonotonyChain> chains2 = getMonotonyChains(l2);
for (MonotonyChain chain1 : chains1)
{
for (MonotonyChain chain2 : chains2)
{
geometrys.add(chain1.intersection(chain2));
}
}
return geometrys;
}
public static boolean hasIntersection(CoordinateSeq me, CoordinateSeq l2)
{
//PointLineBag geometrys = new PointLineBag();
List<MonotonyChain> chains1 = getMonotonyChains(me);
List<MonotonyChain> chains2 = getMonotonyChains(l2);
for (MonotonyChain chain1 : chains1)
{
for (MonotonyChain chain2 : chains2)
{
if (chain1.hasIntersection(chain2))
{
return true;
}
}
}
return false;
}
/**
* 分解为单调链集合
*/
public static List<MonotonyChain> getMonotonyChains(CoordinateSeq points)
{
List<MonotonyChain> chains = new ArrayList<MonotonyChain>();
boolean forward = true;// 正向
if (points.size() > 1)
{
if (points.startPoint().getX() > points.getCoordinate(1).getX())
{
forward = false;
}
}
int n = points.size();
int i = 0;
while (i < n)
{
if (forward)
{
i = extractPositiveChain(points, chains, i);
forward = false;
}
else
{
i = extractNegativeChain(points, chains, i);
forward = true;
}
}
return chains;
}
private static int extractPositiveChain(CoordinateSeq points
, List<MonotonyChain> chains, int from)
{
MonotonyChain chain = new MonotonyChain();
for (int i = from, n = points.size(); i < n; i++)
{
CPoint p = points.getCoordinate(i);
if (!chain.add(p))
{
chains.add(chain);
return i - 1;
}
}
chains.add(chain);
return points.size();
}
private static int extractNegativeChain(CoordinateSeq points
, List<MonotonyChain> chains, int from)
{
MonotonyChain chain = new MonotonyChain();
for (int i = from, n = points.size(); i < n; i++)
{
CPoint p = points.getCoordinate(i);
if (!chain.insert(p))
{
chains.add(chain);
return i - 1;
}
}
chains.add(chain);
return points.size();
}
//------------------------------------------------------------------------有效性检查
public static boolean isSimple(CoordinateSeq points)
{
if (!checkOverPoint(points))
return false;
for (int i = 0, n = points.size() - 1; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
LineSegment ls1 = new LineSegment(points.getCoordinate(i), points.getCoordinate(i+1));
LineSegment ls2 = new LineSegment(points.getCoordinate(j), points.getCoordinate(j+1));
Object g = ls1.intersection(ls2);
if (g == null)
continue;
else if (g instanceof CPoint[])
return false;
else if (g instanceof CPoint)
{
CPoint p = (CPoint)g;
if (!isNodePoint(ls1, ls2, p))
{
return false;
}
}
}
}
return true;
}
private static boolean isNodePoint(LineSegment ls1, LineSegment ls2, CPoint p)
{
boolean isBorder1 = ls1.onBorder(p);
boolean isBorder2 = ls2.onBorder(p);
if (isBorder1 && isBorder2)
{
return true;
}
return false;
}
// 重叠点检测
private static boolean checkOverPoint(CoordinateSeq points)
{
HashSet<CPoint> set = new HashSet<CPoint>();
if (points.size() < 4)
{
return !hasOverPoint(points);
}
for (int i = 1, n = points.size() - 1; i < n; i++)
{
CPoint p = points.getCoordinate(i);
if (set.contains(p))
{
return false;
}
else
{
set.add(p);
}
}
if (existPointAt(points, 1))
{
if (points.startPoint().equals(points.getCoordinate(1)))
{
return false;
}
}
if (existPointAt(points, points.size() - 2))
{
if (points.endPoint().equals(points.getCoordinate(points.size() - 2)))
{
return false;
}
}
return true;
}
// 是否有重叠点
private static boolean hasOverPoint(CoordinateSeq points)
{
HashSet<CPoint> set = new HashSet<CPoint>();
for (CPoint p : points)
{
if (set.contains(p))
{
return true;
}
else
{
set.add(p);
}
}
return false;
}
private static boolean existPointAt(CoordinateSeq points, int i)
{
if ((i < points.size()) && i >= 0)
return true;
return false;
}
}