[GRASS-dev] About v.distance, v.what.vect (wrt "count points within...").

[Nikos Alexandris]

@Markus M: Thank you Markus. Below I have put more questions (before reading 
the document) on purpose. No need to reply (except if you have the time) - 
it's for the sake of a potential beginner's "question and answer" wiki-page.

I'll go through the Ray casting algorithm details. I guess my questions will 
be answered there.

Nikos A wrote:
> >> >> "v.distance" is slow (for the impatient user) with very large vectors
> >> >> (from my memory I estimate that it took ~20h for ~600.000 features).
> >> >> Trying to get the "dmax=" first in order to tell "v.distance" to look
> >> >> for features within a certain radius, might _not_ be very efficient as 
> >> >> well. It takes time to get results from "v.distance -pa" and, 
> >> >> depending on the vector(s), the addition of the _real_ v.distance can
> >> >> be a deal-breaker.

Moritz L:

> >> > Just an innocent question (partly directed to Markus M): could this be
> >> > linked to the spatial index ? And is v.distance faster with spatial
> >> > index on file in grass7 ?
 
Markus M:

> >> No consistent speed difference between grass 6.x and grass 7.
> >> Sometimes grass 6 is faster, sometimes grass 7, but nothing dramatic.
> >> The time-consuming parts are distance calculations and tests whether a
> >> point is inside an area or inside an isle of an area. These
> >> calculations should be done only when necessary. I have added some
> >> tests using bounding boxes to my local copy to avoid
> >> distance-from-point-to-line calculations; in combination with dmax and
> >> without -a there is a real speed gain for point to area distances, but
> >> I need to do more testing to make sure results stay identical.
> >> 
> >> It might save some time to get distances from points to centroids
> >> first with -p (I don't think -a is necessary) because getting
> >> distances to centroids is much faster than getting distances to areas.

Nikos A:

> > "Area = boundary + centroid", so what exactly is the point to area
> > distance?

Markus M:

> If a point is inside an area (the polygon composed of the area's
> boundaries), the distance is 0 (zero):

This sentence makes me think that it is a priori known (based on something 
else - related to topology?) when a point is inside an area. Why all the need 
to measure distances then in order to count how many points are inside?

> A centroid is always inside the area it belongs to, therefore the
> distance of a point outside an area to the area's centroid is always
> larger than the distance of that point to the area's boundaries.

What happens when the centroid (gravity center) falls outside of the 
boundaries?

> > Point to boundary? Specifically, point to all-lines that compose a
> > boundary? Many distances? And then, keep the maximum?

> If a point is outside an area, v.distance determines the shortest
> distance to the area's boundaries (point to all-lines that compose a
> boundary), IOW, keep the minimum not the maximum because v.distance
> searches for the nearest feature.

All right. But, (repeating the same question): why is distance measuring 
required at all? To compare it with what?

> A point is also outside an area if it is inside an isle of the area.
> This isle might in turn be another area with centroid.

This complicates the process I guess.

> > Oh, I am still not within the logic of how exactly the "within area"
> > point detection works.

> Do you really want to know?

At some points yes. I am curious to understand stuff - at least their basic 
concept.

> Start with
> http://en.wikipedia.org/wiki/Point_in_polygon
> GRASS uses the ray casting algorithm

Seems to have all the answers I want. Thanks.

> > Markus, would you mind pointing out the code lines where distance
> > measuring (points to areas) is happening?
> 
> from
> https://trac.osgeo.org/grass/browser/grass/trunk/vector/v.distance/main.c#L
> 676 to
> https://trac.osgeo.org/grass/browser/grass/trunk/vector/v.distance/main.c#L
> 702

> IMHO, there is not a lot of potential for speed improvements, a bit,
> but that comes at the cost of more complicated code.

Why are (supposedly) other tools faster in counting points within polygons?

> I think dmax is the crucial option to speed things up. Without dmax,
> v.distance has to determine for each point in <from> the distance to
> all areas in <to>. With many points and many areas, this will
> obviously take some time. A reasonably fast way to estimate a good
> dmax helps much more than trying to hack v.distance for distances to
> areas.

Then my intentions to test v.distanve/v.what.vect with and without "dmax=" 
where on the right track (right?).

Thank you very much for your time and the details. All the best, Nikos