Re: Speeding up point-in-polygon

"Knowing your data" is the first step when optimizing. I'd plot, look and think about a managable subsample.

Then it could make sense to extend and simplify the screening algorithm idea.

The cartesian data makes it much easier to use squares. I'd reduce each polygon to a 'outer' square (min_x, max_x, min_y, max_y). Databases are good at searching, so the list of potential points is just a sql query away.

The next step is "punching a hole" into the polygon. This could find points that are surely inside. Iteratively extending an 'inner' box from the center of the outer box would work if the center is inside the polygon.

Comment on Re: Speeding up point-in-polygon

Replies are listed 'Best First'.
Re^2: Speeding up point-in-polygon by punkish (Priest) on Jul 24, 2006 at 00:44 UTC
Ok, so this seems like a possible approach, but applied in reverse (update: in other words, instead of `foreach point {foreach poly}}`, I am going to do `foreach poly {get all points {foreach point {more fine-grained}}`.. Generate a SQL table of x,y of all the points foreach rect bound of poly, find all the points that lie within -- this could be done via SQL -- `SELECT points WHERE (point.x > poly.xmin) AND (point.x < poly.xmax) AND (point.y > poly.ymin) AND (point.y < poly.ymax)` do more fine-grained point-in-poly analysis on the points SELECTed in #2 above, either by the said "Wolf Book" algorithm, or just use Math::Geometry::Planar Sounds like a plan. -- when small people start casting long shadows, it is time to go to bed	[reply] [d/l] [select]
Re^3: Speeding up point-in-polygon by explorer (Chaplain) on Jul 24, 2006 at 10:39 UTC
If you can reduce the data to cartesian coords. and the entire zone can reside into RAM, PDL is the faster solution. Example: If $zone is a piddle of bytes with an 1 where the point's coords, you can retrieve the coords of points into polygon's box limits with: `$area = $zone->slice("$xmin:$xmax,$ymin:$ymax"); $coord_points = wichND( $area );` [download] Now, you will have the coords of all points into the $area: `@x_coords = list $coord_points->slice("(0),:"); @y_coords = list $coord_points->slice("(1),:");` [download] This is the fast clipping method if you can reduce the data universe to cartesian coords. And PDL is a C compiled library.	[reply] [d/l] [select]