[postgis-devel] Optimizing contains/within

[Robert W. Burgholzer]

I am looking at the geos code for the contains calls for a point in a
multipolygon, which appears to boil down to the function:

point_in_ring(POINTARRAY *pts, POINT2D *point)

I am a real green C-coder, so if anyone could provide some basic feedback to my
questions, that would be great. Sorry if they are stupid or ridiculously basic.
 If anyone could simply tell me whether my assumptions below are true or false,
I would really appreciate it:

1. If I am looking at the correct function,
2. The time-consuming aspect is related to the sheer number of rings that a
given complicated polygon may contain.  This little function, point_in_ring,
could literally be called thousands of times for each shape - multiplied by the
number of possible points. (can be a really HUGE number)
3. The code uses a fairly compact algorithm that first determine the number of
sides of the ring that cross the y-axis defined by the y-coord of the point,
then adding up the number to the right and left of the point, an odd number
means the point is inside, an even number means the point is outside. (I got
this explanation from http://alienryderflex.com/polygon/ )
4. Given that point_in_ring may be called millions of times for a complex shape
with numerous points to evaluate, any small increase in efficiency in memory
addressing or other could cause a significant performance improvement.


This is where my knowledge of C comes to a grinding halt. I have seen some
information related to pointers, structures and such, so I was wondering what
degree of confidence the function writers have regarding the use of such things
in this particular function.

Thanks,
r.b.


--
Robert W. Burgholzer
--
Finding the occasional straw of truth awash in a great ocean of confusion and
bamboozle requires intelligence, vigilance, dedication and courage.  But if we
don't practice these tough habits of thought, we cannot hope to solve the truly
serious problems that face us -- and we risk becoming a nation of suckers, up
for grabs by the next charlatan who comes along.
-- Carl Sagan, "The Fine Art of Baloney Detection," Parade, February 1, 1987

Online Workout Editor:
http://www.swat-swimming.org/workoutlog/
http://soulswimmer.dynalias.net/