/**
* 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.List;
import chunmap.model.coord.CPoint;
import chunmap.model.elem.Envelope;
import chunmap.model.elem.LineSegment;
import chunmap.model.elem.PointLineBag;
import chunmap.model.geom.GeoPoint;
import chunmap.model.geom.Geometry;
import chunmap.model.geom.LineString;
import chunmap.util.CMAssert;
/**
* 单调链
*
* @author chunquedong
*
*/
public class MonotonyChain {
private final List<CPoint> points = new ArrayList<CPoint>();
private int cursor;
public CPoint getFirst() {
return points.get(0);
}
public CPoint getLast() {
return points.get(points.size() - 1);
}
public int size() {
return points.size();
}
public CPoint get(int i) {
return points.get(i);
}
protected int getCursor() {
return cursor;
}
protected void resetCursor() {
cursor = 0;
}
protected CPoint getCursorPoint() {
return points.get(cursor);
}
protected void increaseCursor() {
cursor++;
}
protected void reduceCursor() {
cursor--;
}
protected boolean hasPre() {
return cursor > 0;
}
protected CPoint getPrePoint() {
return this.get(cursor - 1);
}
protected LineSegment getPreLineSegment() {
return new LineSegment(get(cursor - 1), get(cursor));
}
protected boolean hasNext() {
return cursor < this.size() - 1;
}
protected CPoint getNextPoint() {
return this.get(cursor + 1);
}
protected LineSegment getNextLineSegment() {
return new LineSegment(get(cursor), get(cursor + 1));
}
/**
* 追加到最大的位置
*
* @param p
* @return
*/
public boolean add(CPoint p) {
if (size() == 0) {
points.add(p);
return true;
} else if (p.getX() >= getLast().getX()) {
points.add(p);
return true;
}
return false;
}
/**
* 插入到最小的位置
*
* @param p
* @return
*/
public boolean insert(CPoint p) {
if (size() == 0) {
points.add(p);
return true;
} else if (p.getX() <= getFirst().getX()) {
points.add(0, p);
return true;
}
return false;
}
public boolean join(MonotonyChain other) {
CPoint p1 = this.getLast();
CPoint p2 = other.getFirst();
if (p1.getX() >= p2.getX()) {
points.addAll(other.points);
return true;
}
return false;
}
public LineString toLineString() {
return new LineString(points);
}
public Envelope getEnvelop() {
double minY;
double maxY;
minY = maxY = getFirst().getY();
for (CPoint p : points) {
double y = p.getY();
if (y < minY) {
minY = y;
} else if (y > maxY) {
maxY = y;
}
}
return new Envelope(getFirst().getX(), minY, getLast().getX(), maxY);
}
private void setStartCursor(MonotonyChain other) {
resetCursor();
if (this.getCursorPoint().getX() >= other.getCursorPoint().getX()) {
return;
}
double minX = other.getCursorPoint().getX();
while (getCursorPoint().getX() < minX && this.hasNext()) {
this.increaseCursor();
}
if (this.hasPre())
this.reduceCursor();
}
private int compareY(MonotonyChain other) {
return Double.compare(this.getCursorPoint().getY(), other
.getCursorPoint().getY());
}
public PointLineBag intersection(MonotonyChain other)
{
PointLineBag geometrys=new PointLineBag();
intersectionSub(other, geometrys, true);
return geometrys;
}
public boolean hasIntersection(MonotonyChain other)
{
PointLineBag geometrys=new PointLineBag();
return intersectionSub(other, geometrys, false);
}
private boolean intersectionSub(MonotonyChain other, PointLineBag geometrys, boolean myContinue)
{
//geometrys = new PointLineBag();
// 空的
if (this.size() == 0 || other.size() == 0)
return false;
// 没有交集
if (!this.getEnvelop().hasIntersect(other.getEnvelop()))
{
return false;
}
// 初始化
this.setStartCursor(other);
other.setStartCursor(this);
// 纵坐标大小比较
int compare = compareY(other);
boolean mustHasIntersection = false;
// 交集运算
while (true)
{
int nowCompare = compareY(other);
if (mustHasIntersection || (nowCompare == 0 || nowCompare != compare))
{// 位置改变时必有交点
Geometry g = getIntersection(other);
if (g != null)
{
geometrys.add(g);
if (!myContinue)
{
return true;
}
compare = nowCompare;
mustHasIntersection = false;
}
else
{
mustHasIntersection = true;
}
}
// 增长
if (!increase(other))
break;
}
return geometrys.size()>0;
}
// 向前增长
private boolean increase(MonotonyChain other) {
if (this.getCursorPoint().getX() < other.getCursorPoint().getX()) {
if (this.hasNext())
this.increaseCursor();
else
return false;
} else if (this.getCursorPoint().getX() > other.getCursorPoint().getX()) {
if (other.hasNext())
other.increaseCursor();
else
return false;
} else {
if (this.hasNext())
this.increaseCursor();
else if (other.hasNext())
other.increaseCursor();
else
return false;
}
return true;
}
// 从游标位置前的交集
private Geometry getIntersection(MonotonyChain other) {
if (hasPre()) {
return other.getIntersection(getPreLineSegment());
} else {
return other.getIntersection(this.getCursorPoint());
}
}
// 游标位置前和线段的交集
private Geometry getIntersection(LineSegment ls) {
if (hasPre()) {
Object r = getPreLineSegment().intersection(ls);
if (r == null) return null;
if (r instanceof CPoint)
{
return new GeoPoint((CPoint)r);
}
else if (r instanceof CPoint[])
{
return new LineString((CPoint[])r);
}
else
{
throw new CMAssert.AssertionEexception("unreachable code");
}
} else {
return getIntersection(ls, this.getCursorPoint());
}
}
// 游标位置前和点 的交集
private Geometry getIntersection(CPoint p) {
if (hasPre()) {
return getIntersection(getPreLineSegment(), p);
} else {
if (p.equals(this.getCursorPoint()))
return new GeoPoint(p);
else
return null;
}
}
private Geometry getIntersection(LineSegment ls, CPoint p) {
if (ls.onLineSegment(p))
return new GeoPoint(p);
else
return null;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((points == null) ? 0 : points.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
MonotonyChain other = (MonotonyChain) obj;
if (points == null) {
if (other.points != null)
return false;
} else if (!points.equals(other.points))
return false;
return true;
}
@Override
public String toString() {
return "MonotonyChain [" + points + "]";
}
}