Just another Perl shrine | |
PerlMonks |
comment on |
( [id://3333]=superdoc: print w/replies, xml ) | Need Help?? |
If this is a task you're going to do repeatedly, and your polygon list is relatively static, then you should consider redefining the problem. I suspect that the loop and indexing operations my be consuming a considerable amount of your time. So maybe you can change the problem to unroll the loops.Yes, the polys are relatively static, although the points are not so. Nevertheless, I do indeed unroll both polys and points, and move them into the SQLite db. That way I avoid going back to the files repeatedly. You are correct about "loop and indexing operations my be consuming a considerable amount of your time". Below is the output from my latest run of 5000 polys using Devel::Profiler. More than 220k points were evaluated and updated, and my point-in-poly test was performed 220k times. Total Elapsed Time = 251.1784 Seconds User+System Time = 189.3034 Seconds Exclusive Times %Time ExclSec CumulS #Calls sec/call Csec/c Name 72.3 136.9 136.91 220726 0.0006 0.0006 main::_pointIsInPolygon 9.09 17.21 17.216 5001 0.0034 0.0034 DBI::st::fetchall_arrayref 6.25 11.82 11.825 13887 0.0009 0.0009 DBI::st::execute 4.84 9.162 178.99 1 9.1622 178.99 main::updatePoints 1.82 3.442 3.442 3885 0.0009 0.0009 DBI::db::commit 0.16 0.298 0.298 5001 0.0001 0.0001 DBI::st::fetchrow_array 0.07 0.141 0.141 3887 0 0 DBI::st::finish 0.01 0.01 0.01 3 0.0033 0.0033 IO::Handle::new 0 0 0.01 5 0 0.002 Geo::ShapeFile::get_bytes 0 0 0 6 0 0 DBI::_new_handle 0 0 0.01 5 0 0.002 Geo::ShapeFile::get_handle 0 0 0 1 0 0 DBI::connect 0 0 0 4 0 0 DBI::db::prepare 0 0 0 4 0 0 DBI::_new_sth 0 0 0 3 0 0 Geo::ShapeFile::dbf_handleWhat I really have to figure out is to reduce those tests. I have an idea which I have to now figure out how to implement. Basically, it is like so -- Once I get a bunch of potential points within the rect of a poly, I should find the 4 outermost points in each dimension. Once I determine those four definitively, all points within those 4 would be also within that poly, and I wouldn't have to do the checks for them. Now the hard part -- realize the above hypothesis.
--
when small people start casting long shadows, it is time to go to bed In reply to Re^2: Speeding up point-in-polygon -- take two
by punkish
|
|