CODEWITHSUNDEEP
javascripthtml5-canvas
Ben
Ben

Reputation: 2045

Javascript html canvas organise lines to prevent overlap

I'm working on some logic for a labelling exercise.

enter image description here

I want to connect every red dot to a blue dot, but without the lines overlapping. (not as shown below)

enter image description here

I have a jsfiddle that generates dots and connects them here

https://jsfiddle.net/s1u7okd5/

enter code here

Red dots can vary, obviously, blue dots are fixed. I don't need someone to do the work for me, but I could do with some direction.

Questions:

1: I assume it's always possible to find a solution where the lines don't overlap (ignoring thickness of drawn line). Is this true?

2: I hoping to avoid a brute force approach. Is this possible?

Upvotes: 1

Views: 996

Answers (1)

Davide Visentin
Davide Visentin

Reputation: 751

Assuming that the number of red dots (N) is equal to the number of blue dots (from pictures seems so), a quite naive solution can be:

  1. calculate the length of all possible links between all pairs blueDot-redDot (time complexity O(N^2));
  2. sort links by increasing distance (O(Nlog(N)));
  3. until there are bluePoint still not selected:
    1. extract the shorter link;
    2. Check if the associated bluePoint and redPoint has already been involved in others links (O(1) if you store flags in arrays indexed by point IDs):
    3. if yes: discard the link;
    4. if no: connect the points and flag them as selected.

Probably there can be some optimization, but this is anyway an iterative O(N^2) solution: much better than a brute force solution that, for example, use backtracking to explore all possibilities and find the right one.

Upvotes: 1

Related Questions