17 #include <QtConcurrentMap> 30 QgsSnapIndex::PointSnapItem::PointSnapItem(
const QgsSnapIndex::CoordIdx *_idx,
bool isEndPoint )
31 : SnapItem( isEndPoint ? QgsSnapIndex::SnapEndPoint : QgsSnapIndex::SnapPoint )
40 QgsSnapIndex::SegmentSnapItem::SegmentSnapItem(
const QgsSnapIndex::CoordIdx *_idxFrom,
const QgsSnapIndex::CoordIdx *_idxTo )
41 : SnapItem( QgsSnapIndex::SnapSegment )
46 QgsPoint QgsSnapIndex::SegmentSnapItem::getSnapPoint(
const QgsPoint &p )
const 53 const QgsPoint &q1 = idxFrom->point(), & q2 = idxTo->point();
57 double wl = w.length();
66 double d = v.y() * w.x() - v.x() * w.y();
71 double dx = q1.
x() - p1.
x();
72 double dy = q1.
y() - p1.
y();
73 double k = ( dy * w.x() - dx * w.y() ) / d;
75 inter =
QgsPoint( p1.
x() + v.x() * k, p1.
y() + v.y() * k );
77 double lambdav =
QgsVector( inter.
x() - p1.
x(), inter.
y() - p1.
y() ) * v;
78 if ( lambdav < 0. + 1E-8 || lambdav > vl - 1E-8 )
81 double lambdaw =
QgsVector( inter.
x() - q1.
x(), inter.
y() - q1.
y() ) * w;
82 return !( lambdaw < 0. + 1E-8 || lambdaw >= wl - 1E-8 );
85 bool QgsSnapIndex::SegmentSnapItem::getProjection(
const QgsPoint &p,
QgsPoint &pProj )
87 const QgsPoint &s1 = idxFrom->point();
89 double nx = s2.
y() - s1.
y();
90 double ny = -( s2.
x() - s1.
x() );
91 double t = ( p.
x() * ny - p.
y() * nx - s1.
x() * ny + s1.
y() * nx ) / ( ( s2.
x() - s1.
x() ) * ny - ( s2.
y() - s1.
y() ) * nx );
92 if ( t < 0. || t > 1. )
96 pProj =
QgsPoint( s1.
x() + ( s2.
x() - s1.
x() ) * t, s1.
y() + ( s2.
y() - s1.
y() ) * t );
107 Raytracer(
float x0,
float y0,
float x1,
float y1 )
108 : m_dx( std::fabs( x1 - x0 ) )
109 , m_dy( std::fabs( y1 - y0 ) )
110 , m_x( std::floor( x0 ) )
111 , m_y( std::floor( y0 ) )
117 m_error = std::numeric_limits<float>::infinity();
122 m_n += int( std::floor( x1 ) ) - m_x;
123 m_error = ( std::floor( x0 ) + 1 - x0 ) * m_dy;
128 m_n += m_x - int( std::floor( x1 ) );
129 m_error = ( x0 - std::floor( x0 ) ) * m_dy;
134 m_error = -std::numeric_limits<float>::infinity();
139 m_n += int( std::floor( y1 ) ) - m_y;
140 m_error -= ( std::floor( y0 ) + 1 - y0 ) * m_dx;
145 m_n += m_y - int( std::floor( y1 ) );
146 m_error -= ( y0 - std::floor( y0 ) ) * m_dx;
149 int curCol()
const {
return m_x; }
150 int curRow()
const {
return m_y; }
158 else if ( m_error < 0 )
174 bool isValid()
const {
return m_n > 0; }
186 QgsSnapIndex::GridRow::~GridRow()
188 Q_FOREACH (
const QgsSnapIndex::Cell &cell, mCells )
194 QgsSnapIndex::Cell &QgsSnapIndex::GridRow::getCreateCell(
int col )
196 if ( col < mColStartIdx )
198 for (
int i = col; i < mColStartIdx; ++i )
200 mCells.prepend( Cell() );
203 return mCells.front();
205 else if ( col >= mColStartIdx + mCells.size() )
207 for (
int i = mColStartIdx + mCells.size(); i <= col; ++i )
209 mCells.append( Cell() );
211 return mCells.back();
215 return mCells[col - mColStartIdx];
219 const QgsSnapIndex::Cell *QgsSnapIndex::GridRow::getCell(
int col )
const 221 if ( col < mColStartIdx || col >= mColStartIdx + mCells.size() )
227 return &mCells[col - mColStartIdx];
231 QList<QgsSnapIndex::SnapItem *> QgsSnapIndex::GridRow::getSnapItems(
int colStart,
int colEnd )
const 233 colStart = std::max( colStart, mColStartIdx );
234 colEnd = std::min( colEnd, mColStartIdx + mCells.size() - 1 );
236 QList<SnapItem *> items;
238 for (
int col = colStart; col <= colEnd; ++col )
240 items.append( mCells[col - mColStartIdx] );
247 QgsSnapIndex::QgsSnapIndex(
const QgsPoint &origin,
double cellSize )
249 , mCellSize( cellSize )
254 QgsSnapIndex::~QgsSnapIndex()
256 qDeleteAll( mCoordIdxs );
260 const QgsSnapIndex::Cell *QgsSnapIndex::getCell(
int col,
int row )
const 262 if ( row < mRowsStartIdx || row >= mRowsStartIdx + mGridRows.size() )
268 return mGridRows[row - mRowsStartIdx].getCell( col );
272 QgsSnapIndex::Cell &QgsSnapIndex::getCreateCell(
int col,
int row )
274 if ( row < mRowsStartIdx )
276 for (
int i = row; i < mRowsStartIdx; ++i )
278 mGridRows.prepend( GridRow() );
281 return mGridRows.front().getCreateCell( col );
283 else if ( row >= mRowsStartIdx + mGridRows.size() )
285 for (
int i = mRowsStartIdx + mGridRows.size(); i <= row; ++i )
287 mGridRows.append( GridRow() );
289 return mGridRows.back().getCreateCell( col );
293 return mGridRows[row - mRowsStartIdx].getCreateCell( col );
297 void QgsSnapIndex::addPoint(
const CoordIdx *idx,
bool isEndPoint )
300 int col = std::floor( ( p.
x() - mOrigin.x() ) / mCellSize );
301 int row = std::floor( ( p.
y() - mOrigin.y() ) / mCellSize );
302 getCreateCell( col, row ).append(
new PointSnapItem( idx, isEndPoint ) );
305 void QgsSnapIndex::addSegment(
const CoordIdx *idxFrom,
const CoordIdx *idxTo )
310 float x0 = ( pFrom.
x() - mOrigin.x() ) / mCellSize;
311 float y0 = ( pFrom.
y() - mOrigin.y() ) / mCellSize;
312 float x1 = ( pTo.
x() - mOrigin.x() ) / mCellSize;
313 float y1 = ( pTo.
y() - mOrigin.y() ) / mCellSize;
315 Raytracer rt( x0, y0, x1, y1 );
316 for ( ; rt.isValid(); rt.next() )
318 getCreateCell( rt.curCol(), rt.curRow() ).append(
new SegmentSnapItem( idxFrom, idxTo ) );
324 for (
int iPart = 0, nParts = geom->
partCount(); iPart < nParts; ++iPart )
326 for (
int iRing = 0, nRings = geom->
ringCount( iPart ); iRing < nRings; ++iRing )
330 if ( qgsgeometry_cast< const QgsSurface * >( geom ) )
332 else if (
const QgsCurve *curve = qgsgeometry_cast< const QgsCurve * >( geom ) )
334 if ( curve->isClosed() )
338 for (
int iVert = 0; iVert < nVerts; ++iVert )
340 CoordIdx *idx =
new CoordIdx( geom,
QgsVertexId( iPart, iRing, iVert ) );
341 CoordIdx *idx1 =
new CoordIdx( geom,
QgsVertexId( iPart, iRing, iVert + 1 ) );
342 mCoordIdxs.append( idx );
343 mCoordIdxs.append( idx1 );
344 addPoint( idx, iVert == 0 || iVert == nVerts - 1 );
345 if ( iVert < nVerts - 1 )
346 addSegment( idx, idx1 );
360 float x0 = ( p.
x() - mOrigin.x() ) / mCellSize;
361 float y0 = ( p.
y() - mOrigin.y() ) / mCellSize;
362 float x1 = ( p2.
x() - mOrigin.x() ) / mCellSize;
363 float y1 = ( p2.
y() - mOrigin.y() ) / mCellSize;
365 Raytracer rt( x0, y0, x1, y1 );
366 double dMin = std::numeric_limits<double>::max();
368 for ( ; rt.isValid(); rt.next() )
370 const Cell *cell = getCell( rt.curCol(), rt.curRow() );
375 Q_FOREACH (
const SnapItem *item, *cell )
377 if ( item->type == SnapSegment )
380 if ( static_cast<const SegmentSnapItem *>( item )->getIntersection( p, p2, inter ) )
396 QgsSnapIndex::SnapItem *QgsSnapIndex::getSnapItem(
const QgsPoint &pos,
double tol, QgsSnapIndex::PointSnapItem **pSnapPoint, QgsSnapIndex::SegmentSnapItem **pSnapSegment,
bool endPointOnly )
const 398 int colStart = std::floor( ( pos.
x() - tol - mOrigin.x() ) / mCellSize );
399 int rowStart = std::floor( ( pos.
y() - tol - mOrigin.y() ) / mCellSize );
400 int colEnd = std::floor( ( pos.
x() + tol - mOrigin.x() ) / mCellSize );
401 int rowEnd = std::floor( ( pos.
y() + tol - mOrigin.y() ) / mCellSize );
403 rowStart = std::max( rowStart, mRowsStartIdx );
404 rowEnd = std::min( rowEnd, mRowsStartIdx + mGridRows.size() - 1 );
406 QList<SnapItem *> items;
407 for (
int row = rowStart; row <= rowEnd; ++row )
409 items.append( mGridRows[row - mRowsStartIdx].getSnapItems( colStart, colEnd ) );
412 double minDistSegment = std::numeric_limits<double>::max();
413 double minDistPoint = std::numeric_limits<double>::max();
414 QgsSnapIndex::SegmentSnapItem *snapSegment =
nullptr;
415 QgsSnapIndex::PointSnapItem *snapPoint =
nullptr;
417 Q_FOREACH ( QgsSnapIndex::SnapItem *item, items )
419 if ( ( ! endPointOnly && item->type == SnapPoint ) || item->type == SnapEndPoint )
422 if ( dist < minDistPoint )
425 snapPoint =
static_cast<PointSnapItem *
>( item );
428 else if ( item->type == SnapSegment && !endPointOnly )
431 if ( !static_cast<SegmentSnapItem *>( item )->getProjection( pos, pProj ) )
436 if ( dist < minDistSegment )
438 minDistSegment = dist;
439 snapSegment =
static_cast<SegmentSnapItem *
>( item );
443 snapPoint = minDistPoint < tol * tol ? snapPoint :
nullptr;
444 snapSegment = minDistSegment < tol * tol ? snapSegment :
nullptr;
445 if ( pSnapPoint ) *pSnapPoint = snapPoint;
446 if ( pSnapSegment ) *pSnapSegment = snapSegment;
447 return minDistPoint < minDistSegment ? static_cast<QgsSnapIndex::SnapItem *>( snapPoint ) : static_cast<QgsSnapIndex::SnapItem *>( snapSegment );
458 : mReferenceSource( referenceSource )
467 QtConcurrent::blockingMap( list, ProcessFeatureWrapper(
this, snapTolerance, mode ) );
471 void QgsGeometrySnapper::processFeature(
QgsFeature &feature,
double snapTolerance,
SnapMode mode )
481 QList<QgsGeometry> refGeometries;
484 searchBounds.
grow( snapTolerance );
486 mIndexMutex.unlock();
489 mReferenceLayerMutex.lock();
495 refGeometries.append( refFeature.
geometry() );
497 mReferenceLayerMutex.unlock();
499 return snapGeometry( geometry, snapTolerance, refGeometries, mode );
511 QgsSnapIndex refSnapIndex( center, 10 * snapTolerance );
512 Q_FOREACH (
const QgsGeometry &geom, referenceGeometries )
514 refSnapIndex.addGeometry( geom.
constGet() );
519 QList < QList< QList<PointFlag> > > subjPointFlags;
522 for (
int iPart = 0, nParts = subjGeom->
partCount(); iPart < nParts; ++iPart )
524 subjPointFlags.append( QList< QList<PointFlag> >() );
526 for (
int iRing = 0, nRings = subjGeom->
ringCount( iPart ); iRing < nRings; ++iRing )
528 subjPointFlags[iPart].append( QList<PointFlag>() );
530 for (
int iVert = 0, nVerts = polyLineSize( subjGeom, iPart, iRing ); iVert < nVerts; ++iVert )
536 subjPointFlags[iPart][iRing].append( Unsnapped );
540 QgsSnapIndex::PointSnapItem *snapPoint =
nullptr;
541 QgsSnapIndex::SegmentSnapItem *snapSegment =
nullptr;
544 if ( !refSnapIndex.getSnapItem( p, snapTolerance, &snapPoint, &snapSegment, mode ==
EndPointToEndPoint ) )
546 subjPointFlags[iPart][iRing].append( Unsnapped );
560 subjGeom->
moveVertex( vidx, snapPoint->getSnapPoint( p ) );
561 subjPointFlags[iPart][iRing].append( SnappedToRefNode );
563 else if ( snapSegment )
565 subjGeom->
moveVertex( vidx, snapSegment->getSnapPoint( p ) );
566 subjPointFlags[iPart][iRing].append( SnappedToRefSegment );
576 double distanceNode = DBL_MAX;
577 double distanceSegment = DBL_MAX;
580 nodeSnap = snapPoint->getSnapPoint( p );
585 segmentSnap = snapSegment->getSnapPoint( p );
588 if ( snapPoint && distanceNode < distanceSegment )
591 subjPointFlags[iPart][iRing].append( SnappedToRefNode );
593 else if ( snapSegment )
596 subjPointFlags[iPart][iRing].append( SnappedToRefSegment );
607 if ( qgsgeometry_cast< const QgsPoint * >( subjGeom ) )
618 std::unique_ptr< QgsSnapIndex > subjSnapIndex(
new QgsSnapIndex( center, 10 * snapTolerance ) );
619 subjSnapIndex->addGeometry( subjGeom );
621 std::unique_ptr< QgsAbstractGeometry > origSubjGeom( subjGeom->
clone() );
622 std::unique_ptr< QgsSnapIndex > origSubjSnapIndex(
new QgsSnapIndex( center, 10 * snapTolerance ) );
623 origSubjSnapIndex->addGeometry( origSubjGeom.get() );
626 Q_FOREACH (
const QgsGeometry &refGeom, referenceGeometries )
628 for (
int iPart = 0, nParts = refGeom.
constGet()->
partCount(); iPart < nParts; ++iPart )
630 for (
int iRing = 0, nRings = refGeom.
constGet()->
ringCount( iPart ); iRing < nRings; ++iRing )
632 for (
int iVert = 0, nVerts = polyLineSize( refGeom.
constGet(), iPart, iRing ); iVert < nVerts; ++iVert )
635 QgsSnapIndex::PointSnapItem *snapPoint =
nullptr;
636 QgsSnapIndex::SegmentSnapItem *snapSegment =
nullptr;
638 if ( subjSnapIndex->getSnapItem( point, snapTolerance, &snapPoint, &snapSegment ) )
645 else if ( snapSegment )
648 QgsPoint pProj = snapSegment->getSnapPoint( point );
649 QgsPoint closest = refSnapIndex.getClosestSnapToPoint( point, pProj );
656 if ( !origSubjSnapIndex->getSnapItem( point, snapTolerance ) )
661 const QgsSnapIndex::CoordIdx *idx = snapSegment->idxFrom;
663 subjPointFlags[idx->vidx.part][idx->vidx.ring].insert( idx->vidx.vertex + 1, SnappedToRefNode );
664 subjSnapIndex.reset(
new QgsSnapIndex( center, 10 * snapTolerance ) );
665 subjSnapIndex->addGeometry( subjGeom );
672 subjSnapIndex.reset();
673 origSubjSnapIndex.reset();
674 origSubjGeom.reset();
677 for (
int iPart = 0, nParts = subjGeom->
partCount(); iPart < nParts; ++iPart )
679 for (
int iRing = 0, nRings = subjGeom->
ringCount( iPart ); iRing < nRings; ++iRing )
682 for (
int iVert = 0, nVerts = polyLineSize( subjGeom, iPart, iRing ); iVert < nVerts; ++iVert )
684 int iPrev = ( iVert - 1 + nVerts ) % nVerts;
685 int iNext = ( iVert + 1 ) % nVerts;
690 if ( subjPointFlags[iPart][iRing][iVert] == SnappedToRefSegment &&
691 subjPointFlags[iPart][iRing][iPrev] != Unsnapped &&
692 subjPointFlags[iPart][iRing][iNext] != Unsnapped &&
695 if ( ( ringIsClosed && nVerts > 3 ) || ( !ringIsClosed && nVerts > 2 ) )
698 subjPointFlags[iPart][iRing].removeAt( iVert );
717 int QgsGeometrySnapper::polyLineSize(
const QgsAbstractGeometry *geom,
int iPart,
int iRing )
721 if ( qgsgeometry_cast< const QgsSurface * >( geom ) )
741 : mSnapTolerance( snapTolerance )
752 if ( !mFirstFeature )
757 searchBounds.
grow( mSnapTolerance );
759 if ( !refFeatureIds.isEmpty() )
761 QList< QgsGeometry > refGeometries;
764 refGeometries << mProcessedGeometries.value(
id );
770 mProcessedGeometries.insert( feat.
id(), geometry );
772 mFirstFeature =
false;
Wrapper for iterator of features from vector data provider or vector layer.
A rectangle specified with double values.
virtual bool deleteVertex(QgsVertexId position)=0
Deletes a vertex within the geometry.
bool isNull() const
Returns true if the geometry is null (ie, contains no underlying geometry accessible via geometry() )...
virtual bool insertVertex(QgsVertexId position, const QgsPoint &vertex)=0
Inserts a vertex into the geometry.
QSet< QgsFeatureId > QgsFeatureIds
QList< QgsFeature > QgsFeatureList
QgsWkbTypes::Type wkbType() const
Returns type of the geometry as a WKB type (point / linestring / polygon etc.)
Only snap the start/end points of lines to other start/end points of lines.
QgsGeometrySnapper(QgsFeatureSource *referenceSource)
Constructor for QgsGeometrySnapper.
QgsFeatureRequest & setSubsetOfAttributes(const QgsAttributeList &attrs)
Set a subset of attributes that will be fetched.
void featureSnapped()
Emitted each time a feature has been processed when calling snapFeatures()
A geometry is the spatial representation of a feature.
bool insertFeature(const QgsFeature &feature)
Adds a feature to the index.
The feature class encapsulates a single feature including its id, geometry and a list of field/values...
virtual QgsRectangle boundingBox() const =0
Returns the minimal bounding box for the geometry.
bool hasGeometry() const
Returns true if the feature has an associated geometry.
virtual QgsAbstractGeometry * clone() const =0
Clones the geometry by performing a deep copy.
bool qgsDoubleNear(double a, double b, double epsilon=4 *DBL_EPSILON)
Compare two doubles (but allow some difference)
QgsFeatureList snapFeatures(const QgsFeatureList &features, double snapTolerance, SnapMode mode=PreferNodes)
Snaps a set of features to the reference layer and returns the result.
Utility class for identifying a unique vertex within a geometry.
void grow(double delta)
Grows the rectangle in place by the specified amount.
Only snap start/end points of lines (point features will also be snapped, polygon features will not b...
static GeometryType geometryType(Type type)
Returns the geometry type for a WKB type, e.g., both MultiPolygon and CurvePolygon would have a Polyg...
This class wraps a request for features to a vector layer (or directly its vector data provider)...
T qgsgeometry_cast(const QgsAbstractGeometry *geom)
virtual int ringCount(int part=0) const =0
Returns the number of rings of which this geometry is built.
Abstract base class for curved geometry type.
Abstract base class for all geometries.
QgsGeometry geometry() const
Returns the geometry associated with this feature.
QgsWkbTypes::Type wkbType() const
Returns the WKB type of the geometry.
Point geometry type, with support for z-dimension and m-values.
double length() const
Returns the length of the vector.
A class to represent a vector.
const QgsAbstractGeometry * constGet() const
Returns a non-modifiable (const) reference to the underlying abstract geometry primitive.
QgsGeometry snapGeometry(const QgsGeometry &geometry, double snapTolerance, SnapMode mode=PreferNodes) const
Snaps a geometry to the reference layer and returns the result.
Prefer to snap to nodes, even when a segment may be closer than a node. New nodes will be inserted to...
static double sqrDistance2D(const QgsPoint &pt1, const QgsPoint &pt2)
Returns the squared 2D distance between two points.
A spatial index for QgsFeature objects.
QgsFeatureRequest & setFilterFids(const QgsFeatureIds &fids)
Set feature IDs that should be fetched.
Snap to closest point, regardless of it is a node or a segment. New nodes will be inserted to make ge...
An interface for objects which provide features via a getFeatures method.
virtual bool moveVertex(QgsVertexId position, const QgsPoint &newPos)=0
Moves a vertex within the geometry.
QgsGeometry snapFeature(const QgsFeature &feature)
Snaps a single feature's geometry against all feature geometries already processed by calls to snapFe...
virtual int vertexCount(int part=0, int ring=0) const =0
Returns the number of vertices of which this geometry is built.
QgsRectangle boundingBox() const
Returns the bounding box of the geometry.
void setGeometry(const QgsGeometry &geometry)
Set the feature's geometry.
static QgsPoint projectPointOnSegment(const QgsPoint &p, const QgsPoint &s1, const QgsPoint &s2)
Project the point on a segment.
QgsInternalGeometrySnapper(double snapTolerance, QgsGeometrySnapper::SnapMode mode=QgsGeometrySnapper::PreferNodes)
Constructor for QgsInternalGeometrySnapper.
Prefer to snap to nodes, even when a segment may be closer than a node. No new nodes will be inserted...
QgsPointXY center() const
Returns the center point of the rectangle.
QList< int > QgsAttributeList
Only snap start/end points of lines (point features will also be snapped, polygon features will not b...
bool nextFeature(QgsFeature &f)
double distanceSquared(double x, double y) const
Returns the squared distance between this point a specified x, y coordinate.
virtual QgsPoint vertexAt(QgsVertexId id) const =0
Returns the point corresponding to a specified vertex id.
Snap to closest point, regardless of it is a node or a segment. No new nodes will be inserted...
QList< QgsFeatureId > intersects(const QgsRectangle &rectangle) const
Returns a list of features with a bounding box which intersects the specified rectangle.
bool removeDuplicateNodes(double epsilon=4 *DBL_EPSILON, bool useZValues=false)
Removes duplicate nodes from the geometry, wherever removing the nodes does not result in a degenerat...
virtual int partCount() const =0
Returns count of parts contained in the geometry.
virtual QgsFeatureIterator getFeatures(const QgsFeatureRequest &request=QgsFeatureRequest()) const =0
Returns an iterator for the features in the source.