text: /**********************************************************************
   *
   * GEOS - Geometry Engine Open Source
   * http://geos.osgeo.org
   *
   * Copyright (C) 2011 Sandro Santilli <strk@keybit.net>
   * Copyright (C) 2005-2006 Refractions Research Inc.
   * Copyright (C) 2001-2002 Vivid Solutions Inc.
   *
   * This is free software; you can redistribute and/or modify it under
   * the terms of the GNU Lesser General Public Licence as published
   * by the Free Software Foundation. 
   * See the COPYING file for more information.
   *
   **********************************************************************
   *
   * Last port: geomgraph/EdgeEndStar.java r428 (JTS-1.12+)
   *
   **********************************************************************/
  
  #include <geos/util/TopologyException.h>
  #include <geos/geomgraph/EdgeEndStar.h>
  #include <geos/algorithm/locate/SimplePointInAreaLocator.h>
  #include <geos/geom/Location.h>
  #include <geos/geomgraph/Label.h>
  #include <geos/geomgraph/Position.h>
  #include <geos/geomgraph/GeometryGraph.h>
  
  #include <cassert>
  #include <string>
  #include <vector>
  
  #ifndef GEOS_DEBUG
  #define GEOS_DEBUG 0
  #endif
  
  //using namespace std;
  //using namespace geos::algorithm;
  using namespace geos::geom;
  
  namespace geos {
  namespace geomgraph { // geos.geomgraph
  
  /*public*/
  EdgeEndStar::EdgeEndStar()
  	:
  	edgeMap()
  {
  	ptInAreaLocation[0]=Location::UNDEF;
  	ptInAreaLocation[1]=Location::UNDEF;
  }
  
  /*public*/
  Coordinate&
  EdgeEndStar::getCoordinate()
  {
  	static Coordinate nullCoord(DoubleNotANumber, DoubleNotANumber, DoubleNotANumber);
  	if (edgeMap.size()==0) return nullCoord;
  
  	EdgeEndStar::iterator it=begin();
  	EdgeEnd *e=*it;
  	assert(e);
  	return e->getCoordinate();
  }
  
  /*public*/
  EdgeEnd*
  EdgeEndStar::getNextCW(EdgeEnd *ee)
  {
  	EdgeEndStar::iterator it=find(ee);
  	if ( it==end() ) return NULL;
  	if ( it==begin() ) { it=end(); --it; }
  	else --it;
  	return *it;
  }
  
  /*public*/
  void
  EdgeEndStar::computeLabelling(std::vector<GeometryGraph*> *geomGraph)
  	//throw(TopologyException *)
  {
  	computeEdgeEndLabels((*geomGraph)[0]->getBoundaryNodeRule());
  
  	// Propagate side labels  around the edges in the star
  	// for each parent Geometry
  	//
  	// these calls can throw a TopologyException
  	propagateSideLabels(0);
  	propagateSideLabels(1);
  
  	/**
  	 * If there are edges that still have null labels for a geometry
  	 * this must be because there are no area edges for that geometry
  	 * incident on this node.
  	 * In this case, to label the edge for that geometry we must test
  	 * whether the edge is in the interior of the geometry.
  	 * To do this it suffices to determine whether the node for the
  	 * edge is in the interior of an area.
  	 * If so, the edge has location INTERIOR for the geometry.
  	 * In all other cases (e.g. the node is on a line, on a point, or
  	 * not on the geometry at all) the edge
  	 * has the location EXTERIOR for the geometry.
  	 * 
  	 * Note that the edge cannot be on the BOUNDARY of the geometry,
  	 * since then there would have been a parallel edge from the
  	 * Geometry at this node also labelled BOUNDARY
  	 * and this edge would have been labelled in the previous step.
  	 *
  	 * This code causes a problem when dimensional collapses are present,
  	 * since it may try and determine the location of a node where a
  	 * dimensional collapse has occurred.
  	 * The point should be considered to be on the EXTERIOR
  	 * of the polygon, but locate() will return INTERIOR, since it is
  	 * passed the original Geometry, not the collapsed version.
  	 *
  	 * If there are incident edges which are Line edges labelled BOUNDARY,
  	 * then they must be edges resulting from dimensional collapses.
  	 * In this case the other edges can be labelled EXTERIOR for this
  	 * Geometry.
  	 *
  	 * MD 8/11/01 - NOT TRUE!  The collapsed edges may in fact be in the
  	 * interior of the Geometry, which means the other edges should be
  	 * labelled INTERIOR for this Geometry.
  	 * Not sure how solve this...  Possibly labelling needs to be split
  	 * into several phases:
  	 * area label propagation, symLabel merging, then finally null label
  	 * resolution.
  	 */
  	bool hasDimensionalCollapseEdge[2]={false,false};
  
  	EdgeEndStar::iterator endIt=end();
  	for (EdgeEndStar::iterator it=begin(); it!=endIt; ++it)
  	{
  		EdgeEnd *e=*it;
  		assert(e);
  		const Label& label = e->getLabel();
  		for(int geomi=0; geomi<2; geomi++)
  		{
  			if (label.isLine(geomi) && label.getLocation(geomi) == Location::BOUNDARY)
  				hasDimensionalCollapseEdge[geomi]=true;
  		}
  	}
  
  	for (EdgeEndStar::iterator it=begin(); it!=end(); ++it)
  	{
  		EdgeEnd *e=*it;
  		assert(e);
  		Label& label = e->getLabel();
  		for(int geomi=0; geomi<2; ++geomi)
  		{
  			if (label.isAnyNull(geomi)) {
  				int loc=Location::UNDEF;
  				if (hasDimensionalCollapseEdge[geomi]){
  					loc=Location::EXTERIOR;
  				}else {
  					Coordinate& p=e->getCoordinate();
  					loc = getLocation(geomi, p, geomGraph);
  				}
  				label.setAllLocationsIfNull(geomi, loc);
  			}
  		}
  	}
  }
  
  /*private*/
  void
  EdgeEndStar::computeEdgeEndLabels(
  		const algorithm::BoundaryNodeRule& boundaryNodeRule)
  {
  	// Compute edge label for each EdgeEnd
  	for (EdgeEndStar::iterator it=begin(); it!=end(); ++it)
  	{
  		EdgeEnd *ee=*it;
  		assert(ee);
  		ee->computeLabel(boundaryNodeRule);
  	}
  }
  
  /*public*/
  int
  EdgeEndStar::getLocation(int geomIndex,
  	const Coordinate& p, std::vector<GeometryGraph*> *geom)
  {
  	// compute location only on demand
  	if (ptInAreaLocation[geomIndex]==Location::UNDEF)
  	{
  		ptInAreaLocation[geomIndex]=algorithm::locate::SimplePointInAreaLocator::locate(p,
  				(*geom)[geomIndex]->getGeometry());
  	}
  	return ptInAreaLocation[geomIndex];
  }
  
  /*public*/
  bool
  EdgeEndStar::isAreaLabelsConsistent(const GeometryGraph& geomGraph)
  {
  	computeEdgeEndLabels(geomGraph.getBoundaryNodeRule());
  	return checkAreaLabelsConsistent(0);
  }
  
  /*private*/
  bool
  EdgeEndStar::checkAreaLabelsConsistent(int geomIndex)
  {
  	// Since edges are stored in CCW order around the node,
  	// As we move around the ring we move from the right to
  	// the left side of the edge
  
  	// if no edges, trivially consistent
  	if (edgeMap.size()==0) return true;
  
  	// initialize startLoc to location of last L side (if any)
  	EdgeEndStar::reverse_iterator it=rbegin();
  
  	assert(*it);
  	const Label& startLabel = (*it)->getLabel();
  	int startLoc = startLabel.getLocation(geomIndex, Position::LEFT);
  
  	// Found unlabelled area edge
  	assert(startLoc!=Location::UNDEF);
  
  	int currLoc=startLoc;
  
  	for (EdgeEndStar::iterator it=begin(), itEnd=end(); it!=itEnd; ++it)
  	{
  		EdgeEnd *e=*it;
  		assert(e);
  		const Label& eLabel = e->getLabel();
  
  		// we assume that we are only checking a area
  
  		// Found non-area edge
  		assert(eLabel.isArea(geomIndex));
  
  		int leftLoc=eLabel.getLocation(geomIndex, Position::LEFT);
  		int rightLoc=eLabel.getLocation(geomIndex, Position::RIGHT);
  		// check that edge is really a boundary between inside and outside!
  		if (leftLoc==rightLoc) {
  			return false;
  		}
  		// check side location conflict
  		//assert(rightLoc == currLoc); // "side location conflict " + locStr);
  		if (rightLoc!=currLoc) {
  			return false;
  		}
  		currLoc=leftLoc;
  	}
  	return true;
  }
  
  /*public*/
  void
  EdgeEndStar::propagateSideLabels(int geomIndex)
  	//throw(TopologyException *)
  {
  	// Since edges are stored in CCW order around the node,
  	// As we move around the ring we move from the right to the
  	// left side of the edge
  	int startLoc=Location::UNDEF;
  
  	EdgeEndStar::iterator beginIt=begin();
  	EdgeEndStar::iterator endIt=end();
  	EdgeEndStar::iterator it;
  
  	// initialize loc to location of last L side (if any)
  	for (EdgeEndStar::iterator it=beginIt; it!=endIt; ++it)
  	{
  		EdgeEnd *e=*it;
  		assert(e);
  		const Label& label = e->getLabel();
  		if (label.isArea(geomIndex) &&
  		    label.getLocation(geomIndex,Position::LEFT) != Location::UNDEF)
  		{
  			startLoc = label.getLocation(geomIndex, Position::LEFT);
  		}
  	}
  
  	// no labelled sides found, so no labels to propagate
  	if (startLoc==Location::UNDEF) return;
  
  	int currLoc=startLoc;
  	for (it=beginIt; it!=endIt; ++it)
  	{
  		EdgeEnd *e=*it;
  		assert(e);
  		Label& label = e->getLabel();
  		// set null ON values to be in current location
  		if (label.getLocation(geomIndex,Position::ON) == Location::UNDEF)
  		{
  			label.setLocation(geomIndex,Position::ON,currLoc);
  		}
  
  		// set side labels (if any)
  		// if (label.isArea())  //ORIGINAL
  		if (label.isArea(geomIndex))
  		{
  			int leftLoc=label.getLocation(geomIndex,
  				Position::LEFT);
  
  			int rightLoc=label.getLocation(geomIndex,
  				Position::RIGHT);
  
  			// if there is a right location, that is the next
  			// location to propagate
  			if (rightLoc!=Location::UNDEF) {
  				if (rightLoc!=currLoc)
  					throw util::TopologyException("side location conflict",
  						e->getCoordinate());
  				if (leftLoc==Location::UNDEF) {
  					// found single null side at e->getCoordinate()
  					assert(0);
  				}
  				currLoc=leftLoc;
  			} else {
  				/**
  				 * RHS is null - LHS must be null too.
  				 * This must be an edge from the other
  				 * geometry, which has no location
  				 * labelling for this geometry.
  				 * This edge must lie wholly inside or
  				 * outside the other geometry (which is
  				 * determined by the current location).
  				 * Assign both sides to be the current
  				 * location.
  				 */
  				// found single null side
  				assert(label.getLocation(geomIndex,
  					Position::LEFT)==Location::UNDEF);
  
  				label.setLocation(geomIndex,Position::RIGHT,
  					currLoc);
  				label.setLocation(geomIndex,Position::LEFT,
  					currLoc);
  			}
  		}
  	}
  }
  
  /*public*/
  std::string
  EdgeEndStar::print()
  {
  	std::string out="EdgeEndStar:   " + getCoordinate().toString()+"\n";
  	for (EdgeEndStar::iterator it=begin(), itEnd=end(); it!=itEnd; ++it)
  	{
  		EdgeEnd *e=*it;
  		assert(e);
  		out+=e->print();
  	}
  	return out;
  }
  
  } // namespace geos.geomgraph
  } // namespace geos
  
  