Given a set of 2D points ( or vertices if you want ), the values stored for each point are:

  • coordinate on x
  • coordinate on y
  • an enum or a value from a list in general

for the sake of this example let's say that this last value is the name of a fruit, so the record in the data structure for each point looks like

"34.3" "845.2" "apple"

The set of fruits considered is finite and well defined at the moment the algorithm comes in to play, with this I mean that I can easily list all the possible variations for that 3rd value, if I need to.

Since in my model that 3rd value is assigned per-face, I don't really care if my algorithm acts on faces or on vertices; I should also note that the number of vertices for each face are not equals, so with the term "face" I mean a generic geometry that can be a triangle, a quad, and so on, but no matter how many vertices a face owns, the property is given per-face.

Now the real problem: I need to do some clustering based on that 3rd arbitrary value.

I don't have any pattern here, I have no guarantee on anything, for what I know it's possible to have the entire map composed of single faces with a different 3rd value, they can be convex or concave, the only thing is, I have this kind of records in input, and as output I need a set of areas grouped according to this 3rd value that they have in common. Offcourse if 2 faces share the same 3rd value but they are not adjacent ( don't share at least 1 edge/verts ) they should be considered as 2 separated areas.

What is an algorithm for this kind of clustering ?

Since the dataset is relatively small the time-complexity of the algorithm doesn't really matters that much.

PS If needed I can simplify every face down to a triangle; I am also not sure if this problem can be solved with a Convex Hull algorithm.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.