Bresenham

[ivogeorg]

Employ Bresenhams' line algorithm, possible in reverse, to shorten "sawtooth" (aka "zig-zag") sections of the grid-based path for drone flight.

[ivogeorg]

Zig-zag sections cannot be removed without the use of Bresenham or a similar approach. Here's what GPT says:

Apologies for the confusion, Ivo. I understand your question now. If you want to use the Bresenham algorithm to dynamically trim zig-zag sections of a path without knowing the start and end points ahead of time, you can follow these steps:

Iterate through each consecutive triplet of points in the path.

Check if the three points form a zig-zag pattern. You can determine this by comparing the slopes of the line segments formed by the three points. If the slopes alternate between positive and negative, or vice versa, it indicates a zig-zag pattern.

If a zig-zag pattern is detected, use the Bresenham algorithm to generate a set of grid cells that lie on a straight line between the first and third points of the triplet.

Replace the second point and any intermediate points between the first and third points with the set of grid cells generated by the Bresenham algorithm. This effectively replaces the zig-zag section with a straight line.

Repeat this process for all consecutive triplets of points in the path until no more zig-zag sections are found.

By applying the Bresenham algorithm iteratively on zig-zag sections, you can dynamically trim the path and replace those sections with straight lines. This can help simplify the path and reduce unnecessary turns or maneuvers.

Keep in mind that the effectiveness of this approach depends on the resolution of the grid and the specific characteristics of the zig-zag sections in your path. Adjusting the parameters and thresholds for detecting zig-zag patterns may be necessary to achieve the desired results.

I hope this clarifies the process of using the Bresenham algorithm to trim zig-zag sections dynamically. Let me know if you have any further questions!

After the following (Ivo) comment:

Yes, this sounds more like it. And, indeed, I can see how this approach may only trim part of a zig-zag section as every intermediate point removal will cause the slopes to approach the threshold between negative and positive.

GPT clarified:

Exactly, Ivo! You've understood it correctly. As you iteratively apply the Bresenham algorithm to trim zig-zag sections, it's possible that only part of a zig-zag section will be trimmed in each iteration. This is because removing intermediate points will cause the slopes to approach the threshold between negative and positive.

By gradually removing intermediate points and replacing them with a straight line, you can effectively reduce the zig-zag pattern and create a smoother path. However, it's important to note that the extent of trimming will depend on the specific parameters and thresholds you set for detecting and replacing zig-zag sections.

You may need to experiment with different thresholds and observe the resulting paths to find the right balance between path smoothness and maintaining the desired trajectory. It's also worth considering the trade-off between path smoothness and the computational cost of applying the Bresenham algorithm iteratively.

Remember to test and validate the results of your approach to ensure that the trimmed paths still meet the requirements of your application and achieve the desired performance.

If you have any more questions or need further clarification, feel free to ask!

[ivogeorg]

The above depends too much on parameter tuning unless it is unfolded to more than three consecutive points. How about the following idea (which can use Bresenham or not):

1. Apply collinearity first to decrease the work the next pass will do.
2. The idea is to keep a running "direction" within a certain angle defined by consecutive points:
   1. Mark each but the first point. Keep their indices in a local structure.
   2. If the next point is within the angle (THIS NEEDS TO BE SPECIFIED), continue.
   3. If the next point is outside the angle (there is a change in direction), this is the last point of the zig-zag section. Remove the intermediate ones.