@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 _______________________________________________ grass-dev mailing list [email protected] http://lists.osgeo.org/mailman/listinfo/grass-dev
