Bug report #5162

points in polygon never ends

Added by alobo - over 7 years ago. Updated over 2 years ago.

Status:Closed
Priority:High
Assignee:-
Category:Processing/QGIS
Affected QGIS version:master Regression?:
Operating System: Easy fix?:
Pull Request or Patch supplied:No Resolution:worksforme
Crashes QGIS or corrupts data:Yes Copied to github as #:14914

Description

Vector/Analysis tools/Points in Polygon never ends for moderately complex
polygon layers such as the one provided as an example.

pointsinpolysdata.zip (4.17 MB) alobo -, 2012-03-12 03:34 AM

log.csv Magnifier (1.07 MB) Daniel Vaz, 2013-07-19 03:29 AM

36.png (328 KB) Giovanni Manghi, 2013-07-27 08:57 AM

errors.zip - output of "Check geometry validity" (39.7 KB) alobo -, 2013-07-28 03:22 AM

History

#1 Updated by Giovanni Manghi over 7 years ago

  • Priority changed from Normal to High
  • Operating System deleted (ubuntu 10.04)
  • OS version deleted (10.04)
  • Affected QGIS version changed from 1.7.4 to master
  • Crashes QGIS or corrupts data changed from No to Yes

Confirmed, and causes a complete freeze here.

#2 Updated by Giovanni Manghi over 7 years ago

  • Target version changed from 35 to Version 1.8.0

#3 Updated by Giovanni Manghi over 7 years ago

  • Status changed from Open to Feedback

Hi Agus,
are for any instance this data 3d vectors (like exported from geomedia)?

#4 Updated by alobo - over 7 years ago

No, the points are coordinates of fire pixels and the polygons are a vectorized ("polygonized")
raster landcover map.
I think this is just a question of the size and complexity of the polygon vector layer. The process runs
ok with a polygon vector layer made from a grid.

Agus

#5 Updated by Giovanni Manghi over 7 years ago

Alex and Salvatore, here same consideration made for #3828... :)

#6 Updated by Alexander Bruy over 7 years ago

Starting from 53684682f2 this tool runs in separate thread. Now it don't block main window and process can be interrupted. I know this is not much, but at least user can terminate long-running process without killing QGIS.

#7 Updated by Giovanni Manghi over 7 years ago

Alexander Bruy wrote:

Starting from 53684682f2 this tool runs in separate thread. Now it don't block main window and process can be interrupted. I know this is not much, but at least user can terminate long-running process without killing QGIS.

Hi Alexander, this is good, thanks a lot. Can this approach be used also for the dissolve issue?

#8 Updated by Alexander Bruy over 7 years ago

Giovanni Manghi wrote:

Hi Alexander, this is good, thanks a lot. Can this approach be used also for the dissolve issue?

Disslove (and all other geoprocessing tools) already used threads, but there is no option to interrupt running process. I'm looking on it now. Hope we can do something with this before 1.8

#9 Updated by Paolo Cavallini about 7 years ago

  • Target version changed from Version 1.8.0 to Version 2.0.0

#10 Updated by Giovanni Manghi about 7 years ago

  • Status changed from Feedback to Open

#11 Updated by Giovanni Manghi over 6 years ago

  • Priority changed from High to Severe/Regression

#12 Updated by Giovanni Manghi over 6 years ago

  • Priority changed from Severe/Regression to High

I don't why I set this as blocker as it is not a regression.

#13 Updated by Daniel Vaz over 6 years ago

I developed a simple plugin in c++ that try to do the same thing that tool points in polygon does. But I have no success (in a reasonable time) in the iterating process over all polygons, answering how many points has inside in each polygon.

I logged, in a csv file, the following debug output: (I check the geometry validity, if it's not valid I put on log file the line "#invalid")

inGeom->wkbType()
inGeom->length()
inGeom->area()
polygonVertex( polyFeat ) [number of vertices in polygon)
pointList.size() [number of points returned by spatial index query giving the polygon bounding box]
count [number of points that really intersects the polygon]
timer.nsecsElapsed() [nanoseconds since that current polygon started to be processed]

I am not sure if the attached log can help in the attempts to solve this issue.

The test plugin is accessible in:

https://bitbucket.org/danielvaz/mixed-ideas/src/2bc94814ebc03d66ded69375dd35c4d023c013d7/qgis/points_in_polygon?at=master

Thanks in advance

#14 Updated by vinayan Parameswaran over 6 years ago

the polygon layer contains quite a lot of invalid geometries(around 300 of them)..try a check geometry validity using topology checker..without fixing these errors, there is no point in running a PIP on this layer..I think we are wasting our time on this layer by keeping this bug..otherwise a complex layer with clean geometry should be added for testing..

#15 Updated by Giovanni Manghi over 6 years ago

vinayan Parameswaran wrote:

the polygon layer contains quite a lot of invalid geometries(around 300 of them)..try a check geometry validity using topology checker..without fixing these errors, there is no point in running a PIP on this layer..I think we are wasting our time on this layer by keeping this bug..otherwise a complex layer with clean geometry should be added for testing..

Hi Vinayan,
while you are right about geometry errors in general, I think this is kind of a "special" case, as the reported errors are all about different nodes of a same feature that do touch each other (see attached image). While I believe this is considered in general an error, we must also consider that when vectorizing (raster to vector) it is almost sure to get such "errors", and it is common to use such resulting vectors in further geoprocessing operations. We must also consider that other tools (like SAGA/SEXTANTE) are able to handle such feature while doing this operation.

We probably can lower the priority of the ticket because there is now an alternative (SEXTANTE), but for sure something we may want to improve, or not :)

#16 Updated by Daniel Vaz over 6 years ago

Hi Giovanni, I am curious about SAGA/SEXTANTE. Is these tools will replace fTools in future?

I see (in some issue, I can't remember the number) something about it.

If the fTools will be replaced I think that more time should be spent in the newer tool. :-)

Thank you

#17 Updated by Giovanni Manghi over 6 years ago

Daniel Vaz wrote:

Hi Giovanni, I am curious about SAGA/SEXTANTE. Is these tools will replace fTools in future?

I see (in some issue, I can't remember the number) something about it.

If the fTools will be replaced I think that more time should be spent in the newer tool. :-)

Olá Daniel,
as far as I understood sooner or later all the qgis geoprocessing/analysis tools will be moved in sextante... well, I hope moved and not removed. Redundancy in the analysis toolbox is good :) The same kind of tool can be more efficient in a software rather than another, and sometimes results are slightly different, so I hope nothing will be removed, just moved. But until SEXTANTE will be deeply tested I guess that keeping the tools in the qgis main menus is the right choice for now.

#18 Updated by alobo - over 6 years ago

Giovanni Manghi wrote:

vinayan Parameswaran wrote:

the polygon layer contains quite a lot of invalid geometries(around 300 of them)..try a check geometry validity using topology checker..without fixing these errors, there is no point in running a PIP on this layer..I think we are wasting our time on this layer by keeping this bug..otherwise a complex layer with clean geometry should be added for testing..

Hi Vinayan,
while you are right about geometry errors in general, I think this is kind of a "special" case, as the reported errors are all about different nodes of a same feature that do touch each other (see attached image). While I believe this is considered in general an error, we must also consider that when vectorizing (raster to vector) it is almost sure to get such "errors", and it is common to use such resulting vectors in further geoprocessing operations. We must also consider that other tools (like SAGA/SEXTANTE) are able to handle such feature while doing this operation.

I do not think we can consider these as errors (I attach the error layer produced by "Check geometry validity" ), just as characteristics of the layer: "Check geometry validity" is (wrongly I think) reporting as errors the cases in which 2 polygons share 1 single vertex, why should those be considered as errors? I think the problem is rather that ftools has not taken this case into account, and this could be the reason why it fails (and the reason why the plugin works for a test polygon derived from a rectangular grid, where no polygons sharing one single vertex exist).

We probably can lower the priority of the ticket because there is now an alternative (SEXTANTE), but for sure something we may want to improve, or not :)

I would agree, but "Counts points in polygon" in Sextante fails also (1.9.0-Master QGIS code revision 1847c61,
"Traceback (most recent call last):
File "/Users/agustinlobo/.qgis//python/plugins/sextante/core/GeoAlgorithm.py", line 145, in execute
self.processAlgorithm(progress)
File "/Users/agustinlobo/.qgis//python/plugins/sextante/algs/ftools/PointsInPolygon.py", line 76, in processAlgorithm
spatialIndex = utils.createSpatialIndex(pointLayer)
File "/Users/agustinlobo/.qgis//python/plugins/sextante/algs/ftools/FToolsUtils.py", line 32, in createSpatialIndex
provider = layer.provider()
AttributeError: 'QgsVectorLayer' object has no attribute 'provider'"

So there is no option.

#19 Updated by Giovanni Manghi over 6 years ago

I would agree, but "Counts points in polygon" in Sextante fails also

I just tested and it works ok on Windows. On Linux there is an issue as now it is needed SAGA 2.1 and there is a issue with packaging, at least on Ubuntu.

From your error message it seems you have something to fix, as it should show that you are using something that now is in .qgis2 not .qgis anymore.

#20 Updated by alobo - over 6 years ago

Giovanni Manghi wrote:

I would agree, but "Counts points in polygon" in Sextante fails also

I just tested and it works ok on Windows. On Linux there is an issue as now it is needed SAGA 2.1 and there is a issue with packaging, at least on Ubuntu.

From your error message it seems you have something to fix, as it should show that you are using something that now is in .qgis2 not .qgis anymore.

I'm using the mentioned code revision on Mac, as I'm away of my office cannot test on any other machine or build. If you are positive the Sextante alternative really works,
I agree decreasing the priority of this bug (but users should be warned in general that geoprocessing in Sextante is a more reliable option).
Agus

#21 Updated by alobo - over 6 years ago

Giovanni Manghi wrote:

Daniel Vaz wrote:

Hi Giovanni, I am curious about SAGA/SEXTANTE. Is these tools will replace fTools in future?

I see (in some issue, I can't remember the number) something about it.

If the fTools will be replaced I think that more time should be spent in the newer tool. :-)

Olá Daniel,
as far as I understood sooner or later all the qgis geoprocessing/analysis tools will be moved in sextante... well, I hope moved and not removed. Redundancy in the analysis toolbox is good :) The same kind of tool can be more efficient in a software rather than another, and sometimes results are slightly different, so I hope nothing will be removed, just moved. But until SEXTANTE will be deeply tested I guess that keeping the tools in the qgis main menus is the right choice for now.

I think we should keep just one method (the best) bust keep the dual access: many users will find having the geoprocessing vector tools in the main menu more natural. Currently the Sextante section is too heterogeneous.
Obviously this could be customizable.

#22 Updated by Paolo Cavallini almost 6 years ago

  • Target version changed from Version 2.0.0 to Future Release - High Priority

#23 Updated by Martin Dobias almost 6 years ago

  • Resolution set to worksforme
  • Status changed from Open to Closed

The main issue with the attached layer are the few huge geometries, especially the one with ID 26569 - with more than two thousand of holes and 90 thousand of vertices, it is a very complex polygon. There are about eight thousand of points that need to be tested for intersection, each of the tests takes ~1 second on my computer... so the computation would take few hours, but eventually will end.

This can be improved, though. I have done few tests with "prepared geometry" functionality from GEOS (>= 3.1) and that makes HUGE difference - the computation was done within few seconds. I have raised feature request #9521 to implement that.

Therefore I am closing this ticket (there is no bug, the computation just takes long time)

#24 Updated by Giovanni Manghi over 2 years ago

The "ftools" category is being removed from the tracker, changing the category of this ticket to "Processing/QGIS" to not leave the category orphaned.

Also available in: Atom PDF