Path Planner Algorthim with constraints?

Question

Issue:

Ran into an interesting problem at work today. I am trying to build a multi path planner algorithm with some interesting rules. I wanted to get the communities thoughts on approaches while I work on whatever I try first. Hoping this is a solved problem already and I just don't know the search terms.

Rules:

• There are Nr red start points, there are Nb blue start points. You must draw one path for each start point.
• Each path should only intersect once for each combination, for instance path red_1 may only intersect path blue_1 at a single point.
• Paths of the same color need to maintain D(istance) from each other and by extension may not intersect. Paths must be contagious to start.
• Paths have width 0 < W < 1/3 D.
• Paths may not exit the region of interest.
• The region is an arbitrary polygon, it may be convex or concave.
• Start positions should be predefined by may be placed anywhere within the area of interest or on its edges.

Goal:

• Paths should cover as much of the area of interest as possible.

Answer 1

A first pass:

Draw red lines vertically
If red line too close to another on right, move left
If red line too close to another on left, move right
Remove one line from any pair of red lines too close
Draw blue lines horizontally
If blue line too close to another below, move up
If blue line too close to another above, move down
Remove one line from any pair of blue lines too close

Example of random starts in square region

Complete C++ code for this application at https://github.com/JamesBremner/aris2

I have added convex polygon regions of interest, here is an example for a triangular region