# Clustering algorithm with specific cluster grouping areas

I'm looking for a way to cluster points in a given space, where clusters form around specific closed, allowed zones of that initial space. Each allowed zone should be surrounded by points of its cluster.

However, it is not only necessary to match the points to the closest allowed zone, but also to take into consideration the distance to other points of the same cluster.

In the example image given, in the clustered picture, the green points at the top right belong to the green cluster despite being closest to the blue area, because their neighbours are all green.

Ultimately, a network would be created from each cluster (lets say the points are a series of sinks), and linked to each respective zone via a single optimally placed point within the zone (which represents the source). A cost function would evaluate the cost of the network (i.e. minimizing the cost of a weighted graph). The difficulty is that the optimal placement of the source point is not known until the cluster is defined. The overall goal is to minimize the cost of all the networks combined.

Is there any algorithm available that can do this type of clustering? Otherwise how would you proceed?

• I think you can try running clustering disregarding the zones first. Then placing dummy dots in the zones and running again. This can potentially cause some of the dots to be in different clusters. And for each such dot, you can decide then, if the dummy dots would not be in the map, which other cluster from the first run it would be part of. Feb 6, 2020 at 14:32
• This sounds a bit vague: "take into consideration" doesn't say how you want to weight the tradeoff between "nearest zone" vs "cluster of nearest points".
– D.W.
Feb 6, 2020 at 19:05
• Ultimately, a network would created from each cluster (lets say the points are a series of sinks), and linked to each respective zone via a single optimally placed point within the zone (which represents the source). A cost function would evaluate the cost of the network (i.e. minimizing the cost of a weighted graph). The difficulty is that the optimal placement of the source point is not known until the cluster is defined. The overall goal is to minimize the cost of all the networks combined. I hope this helped clarify the problem. Feb 6, 2020 at 21:29
• OK. Please edit the question to incorporate that information. We prefer that questions read well for someone who encounters them for the first time (so don't use "edit: ..."), and that people don't need to read the comments to understand the question. Thank you!
– D.W.
Feb 6, 2020 at 23:12