# Writing an algorithm to find the most efficient line angle at which to draw lines

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...

• 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. 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. 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. Jan 7, 2014 at 15:44