— Shang Liang

Interesting Math Problem

There are n dots, p red ones and q blue ones. The target is to link up the red ones without having cross overs, e.g.
crossovers
To produces this,
nocrossovers

To solve this problem. I consider all the red dots lie originally on a perfect circle and this irregular pattern is produced by moving the dots further or closer to the center of the circle. So, I first calculated the center point of all dots, centerX=(x1+x2+…+xn)/n, centerY=(y1+y2+…+yn)/n. Using a center point, I calculate the angle of a dot as angle1=Math.atan2(y1-centerY, x1-centerX). All the dots are sorted by their angles and linked clockwise or counterclockwise.
Not something difficult but quite interesting :) .

2 comments
  1. Maciek says: November 6, 20065:34 pm

    What do you need blue dots for?

  2. 5566 says: November 6, 20068:39 pm

    lol, true, the problem remains the same without the blue dots .

Submit comment

For spam filtering purposes, please copy the number 6417 to the field below: