random instances of map-coloring in python

Question

I need to generate random instances of map coloring problem in python to implement a min-conflict solver. I should follow this strategy: scatter n points on the unit square; select a point X at random, connect X by a line segment to the nearest point Y such that X is not already connected to Y and the segment crosses no other segment (see, e.g., here how to test for segment-segment intersection); repeat the previous step until no more connections are possible. The points represent regions on the map and the lines connect neighbors. I don't even know how to start.

Answer 1

Something for you to start, take this class:

class Node:
  def __init__(self, x, y):
    self.x = x
    self.y = y
    self.neighbours = set()

  def is_neighbour(node: Node):
    return node in self.neighbours

  def connect(node: Node):
    self.neighbours.add(node)
    node.neighbours.add(self)

  def distance(node: Node):
    return ((self.x - node.x)**2 + (self.y - node.y)**2)**0.5

The hardest part will be detecting if the connection between points you're trying to make won't cross with another connection, but I'll leave it to you.