2

I've written a tool that fills a polygon in ArcMap with parallel lines at a user specified distance apart and at a user specified angle, written in vb.net and arcobjects. What i'm looking to do next is write a tool that calculates the most efficient angle at which to draw these lines (i.e. the angle which fills the polygon with the least number of lines, or greatest average line length), given the specified line separation distance.

For example if the polygon was a simple rectangle, then the most efficient line angle to fill the rectangle would be parallel to the long axis, as it would take more lines to fill the polygon if they were drawn parallel to the shorter axis. For more complicated shapes I have little knowledge of how to achieve this.

The only way I can think of doing it is to write a loop that creates lines at every angle and then pick the output with the greatest average line length, but that would take too long (drawing each set of lines takes a good 5-10 seconds depending on the number of lines).

I know it's a longshot but does anyone have any ideas? Probably quite a tricky one...

Improve this question
3
  • 1
    You used the example of a rectangle but can these polygons be more complex? For example a reservoir boundary? Will your polygons have holes in them? How do you intend to deal with those? Also to optimize your code you only need to test 0° - 179°, I don't think you need to render it until the optimal solution is found and you could employ an in_memory workspace for fast storage until the final write to disk.
    – Hornbydd
    Commented Jan 7, 2014 at 13:08
  • Thanks for the reply. Some polygons may be more complex (i.e. may have a stepped shape) although most are relatively rectangular and none have holes/islands. I'm not so sure that it's the rendering which takes up the most time, I do a fair bit of clipping (using topological operator), and segment extension during the line generation workflow, which I think is the main culprit. I need a pretty fast solution, or it won't be worth implementing.
    – pvdev
    Commented Jan 7, 2014 at 14:52
  • For this question to be objectively answerable, you need to quantify "efficient." The question assumes that the number of "lines" is proportional to the cost of filling. I presume that is the number of line segments. But is this really correct? The actual cost apparently is the time your algorithm requires to compute these line segments. That depends on the structure of the algorithm itself. How, exactly, does it work? Note, too, that if your precomputation of the "most efficient" angle is more expensive than the actual filling, then the entire exercise would seem pointless.
    – whuber
    Commented Jan 7, 2014 at 15:44

1 Answer 1

Reset to default
3

I cannot prove it, but I think that the best orientation will (most of the time) be the orientation of the minimum bounding rectangle by width. You can use the built in tool "minimum bounding geometry" (RECTANGLE_BY_WIDTH), which also compute the angle. It should be faster than building all your lines if the spacing between lines is small.

Improve this answer
4
  • 1
    I think you're correct for the most part, that the long axis of a minimum bounding rectangle (by width) will give the best orientation for simple shapes. But a lot of my polygons have odd shapes, which is the main problem. I might implement this anyway and just see how well it works, as it won't take long. Thanks very much for the input!
    – pvdev
    Commented Jan 7, 2014 at 15:19
  • Follow up question: Any way I can get the minimum bounding rectangle by width without using geoprocessing tools? Want to avoid that if possible...
    – pvdev
    Commented Jan 7, 2014 at 15:35
  • The MBR is the correct answer in general only for convex polygons. For others it is easy to construct simple counterexamples, assuming we are counting line segments rather than lines.
    – whuber
    Commented Jan 7, 2014 at 15:40
  • Just to follow up - I got decent results using MBR width. Thanks again.
    – pvdev
    Commented Mar 6, 2014 at 15:40

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.