in reply to Re: Speeding up point-in-polygon
in thread Speeding up point-in-polygon

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}}..
  1. Generate a SQL table of x,y of all the points
  2. 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)
  3. 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

Replies are listed 'Best First'.
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]

In Section Seekers of Perl Wisdom