10

I have a shapefile containing arcs representing the path travelled by a truck spreading fertiliser onto a farm.

Let's say I know the spread width is 30m, i.e. the truck can spread fertiliser 15m either side of the vehicle.

I want to generate a set of polygons, which show:
1) The total area that received fertiliser
2) The areas of overlap, i.e. where two separate passes were too close together, such that some parts of the farm received twice the correct "dose" of fertiliser.

A naive approach is to just create the coverage polygons as buffers around the arcs. This works in the special case where the spread lines are distinct from each other. However, the truck could conceivably travel around the farm in an ever-decreasing spiral, and a simple buffer would fail to show overlaps where two passes of the spiral were too close together (if the spiral is a single arc, I would end up with a single polygon with no overlapping parts).

If it's relevant, I'm using the TatukGIS VCL DK, but I'm really looking for an algorithm rather than a specific solution.

Some clarifications in response to the discussion so far:

1) I can't rely on the vector data having any particular metadata (e.g. GPS logs or spread rate). I allow the user to choose a layer and specify a spread width, then the report runs.

2) The purpose of the report is really to show the user how "skilled" the vehicle operator was, where "skilled" means "achieved the highest coverage with the lowest overlap".

3) I'm more comfortable in vector land than raster land, so will prefer vector-based solutions.

Thanks,

Darren.

Improve this question
1
  • 1
    I wonder if this would be similar to methods that predict cumulative precipitation based on forecasted storm paths.
    – Kirk Kuykendall
    Commented Feb 22, 2011 at 16:35

4 Answers 4

Reset to default
3

Perhaps the simplest solution is to break up the single geometry into segments, and buffer those individual segments: in your spiral case, you'd buffer each arc, then intersect the individual arcs to come up with a count. Take care to avoid false overlaps by not buffering the ends of the segments, only to the left and right of the segments themselves.

Another approach is to overlay a polygon grid on the data, and then within each grid cell, buffer every intersecting line segment separately. To be accurate in this, you'd want to take the grid cell under analysis, buffer it, then collect the intersecting segments, and buffer those, performing your analysis within the original cell window.

Either of these options should give you a reasonable estimate of overlap, I can think of a few more accurate approaches but they'd require knowing something about the data.

Improve this answer
2
  • Thanks. I was thinking along the lines of your first suggestion - breaking the geometry up into segments & buffering them. I think I'll need to also buffer the ends of the segments, so that I get rounded edges at corners. Thinking of the case where I start with a right-angle line - if I don't buffer the ends, I'll end up with two overlapping rectangles with a square missing at the outside of the corner (difficult to express as text!)
    – dbruning
    Commented Feb 22, 2011 at 20:32
  • I think I'll need to also buffer the ends of the segments, so that I get rounded edges at corners. I was further thinking of intersecting the buffer for each segment with the buffer for the previous segment, and then accumulating just the "new" parts of each buffer into a master buffer. The idea being to ignore overlaps with the previous segment but pickup overlaps with older segments.
    – dbruning
    Commented Feb 22, 2011 at 20:39
2

No solution, but some inputs:

This problem seems similar to the line coalescence detection problem in map generalization. It happens when a large style is applied on a sinuous line (the symbol self-overlaps):

enter image description here

This document pp. 176 to 180 (in french...sorry) gives an algorithms to detect such self intersecting parts. The principle is, as proposed by scw, to use a single side buffer of each segment composed of a segment plus 0, 1 or 2 circle arcs. JTS contains an implementation of this single side buffer that may be useful.

Improve this answer
2
  • Why are you concerned about detecting self intersections? And why do you propose "single side" buffers? Neither seems germane to the problem.
    – whuber
    Commented Feb 22, 2011 at 15:36
  • The purpose is to detect where the truck spreads fertilizer several times, that is where the spreading area self-intersects.
    – julien
    Commented Feb 23, 2011 at 8:32
2

A vector solution is going to miss a potentially critical variable: time, and through it, spreading rate. When the tractor moves faster, less fertilizer is spread per unit area and when it moves slower (decelerating into a turn and accelerating out of one) is will spread more fertilizer per unit area. Moreover, if the tractor is spreading material while turning, the material will be more concentrated toward the inside of the turn and less concentrated toward the outside.

Time data would be available in a GPS record of the tractor's progress. Slopes (distance traveled divided by time elapsed) will estimate the speeds at every point. Alternatively, one might (as an approximation) assume a constant speed within the interior of a field and a slower speed within a reasonable internal buffer of the field's boundary.

A raster representation can handle these issues. Rasterize the path of the tractor. This sets all cells not crossed by the tractor to NoData values (or to zero). If the tractor were to move at a standard, constant speed, it would suffice to put a constant value in each of the data cells. Now, for example, if the tractor were moving at twice this speed, (presumably) its application rate would be halved, and this can be represented by halving the value in the cells.

In general, the value to put in any cell is the application rate per unit area. If the tractor is uniformly spreading x Kg of fertilizer per second out to 15 m on each side while traveling at a speed of y m/sec, then it is spreading x/y Kg/sec / [m/sec] / (2*15 m) = x/(30 y) Kg/m^2 fertilizer. Thus, x/(30 y) is the value to put in each cell. x is given and y is computed from the GPS data.

Self-intersections are no problem in principle. If the tractor's path crosses itself, add the contributions each time it recrosses a cell. It may require some special processing to accomplish this, depending on how the grid is being created and on the capabilities of the GIS software.

Having done that preparation, the rest is fast and easy: a focal sum of this grid, using a circular neighborhood with 15 m radius, finds the cumulative amount spread per unit area in every cell.

Improve this answer
10
  • 1
    +1 it seems like if you had a tool that allowed a kernel (representing the tractor) to move along a path (instead of along each row) this problem would be more manageable.
    – Kirk Kuykendall
    Commented Feb 22, 2011 at 17:52
  • @Kirk There's no need to follow a path or rows or whatever with a kernel. It's important to appreciate the change in point of view that accompanies a focal sum: instead of looking at the problem as one of spreading material from a path of points, look at it as one of computing how much material accumulates at every point in the field. Obviously it's the same problem with the same solution. The moving kernel approach (and the proposed buffering approaches) take the first point of view; the focal sum, the second. But the focal sum tool is available; a moving kernel calculation is not.
    – whuber
    Commented Feb 22, 2011 at 18:02
  • I think the raster approach you outline would be the best method if we knew speed and spread rate. Unfortunately in this particular scenario we know neither. Our end user can choose any layer as input to this coverage report, and we can't rely on the geometry having any particular metadata.
    – dbruning
    Commented Feb 22, 2011 at 20:26
  • @dbruning This approach doesn't seem to require known speed/spread rates; it just allows for them (+ the more accurate model of reality) if you have them. However, it's also more going to require some cell thresholding+counting to get the metrics you want (total area coverage; area-of-overlap) out of the system, and there's accuracy trade-offs mixed in there as well.
    – Dan S.
    Commented Feb 22, 2011 at 21:59
  • @dbruning If you don't know spread rate, you will get a relative spread rate. If you don't know speed, you still know (or ought to know) how people drive tractors and should be able to derive reasonable estimates of relative speeds. If you assume constant speeds and constant spread rates you will still get reasonable answers; they will agree with the buffer-based answers over straight portions of the tractor routes; and they are likely to be more realistic in the curved portions.
    – whuber
    Commented Feb 22, 2011 at 22:12
2

I'm not 100% sure on StackExchange protocol so I'm posting this as an answer to my question. It's the answer I ended up using anyway.

The basic algorithm is:
1. Break up any geometry on the layer into segments no longer than 1/2 the spread width.
2. For each segment:
- Create a "rolling buffer" by looking backwards along the shape, and buffering all previous segments where the cumulative length of those segments is less than the spread width (buffer radius = 1/2 spread width)
- Create a "next segment buffer" of just the next segment (buffer radius = 1/2 spread width)
- Subtract the "rolling buffer" from the "next segment buffer" to get "new buffer"
- join all of the "new buffer" polygons together to get a single polygon per shape.

Essentially this allows for the spreader vehicle driver to make right-angle (or wider) turns without overlap penalty, but if they turn back too sharply such that they spread over "old ground", we start to get overlaps.

Overlaps in blue

Spiral looks like I want it to:

spiral

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.