Visual analytics for spatial clustering
A computerized clustering method. The method comprises receiving a spatial point dataset comprising a plurality of spatial points in a space, heuristically calculating, using a processor, a plurality of α-shape based segmentations such that each of the plurality of α-shape based segmentations defines a plurality of polygonal areas that cluster the plurality of spatial points in a plurality of clusters which collectively bounds the plurality of spatial points, presenting to an operator in each sequential iteration of a plurality of sequential iterations another of the plurality of α-shape based segmentations, and selecting by the operator one or more of the plurality of α-shape based segmentations.
1. A computerized clustering method, comprising:
receiving a spatial point dataset comprising a plurality of spatial points in a space;
heuristically calculating, using a processor, a plurality of α-shape based segmentations such that each of said plurality of α-shape based segmentations defines a plurality of polygonal areas that cluster said plurality of spatial points in a plurality of clusters which collectively bounds said plurality of spatial points;
presenting to an operator in each sequential iteration of a plurality of sequential iterations another of said plurality of α-shape based segmentations; and
selecting by said operator at least one of said plurality of α-shape based segmentations.
2. The computerized method of claim 1 , wherein said heuristically calculating comprises calculating Delaunay triangulation on said spatial point dataset and calculating a plurality of α-shapes based on said Delaunay triangulation, wherein each of said plurality of α-shape based segmentations is defined according to another of said plurality of α-shapes.
3. The computerized method of claim 1 , wherein said heuristically calculating comprises selecting at least one of said plurality of α-shape based segmentations such that a corresponding geometric graph that represents a respective α-shape contains only simple polygonal cycles.
4. The computerized method of claim 1 , wherein said heuristically calculating comprises dividing said plurality of α-shape based segmentations to a plurality of topologically equivalent classes; selecting one member of said plurality of topologically equivalent classes; wherein said presenting comprises presenting to said operator in each sequential iteration of said plurality of sequential iterations another said member.
5. The computerized method of claim 1 , wherein said presenting comprises receiving from said operator instructions to adapt a topology of at least one of said plurality of polygonal areas.
6. The computerized method of claim 5 , wherein said presenting comprises generating a visual feedback to said instructions.
7. The computerized method of claim 1 , wherein said plurality of spatial points are plurality of objects located on a map.
8. The computerized method of claim 1 , wherein said heuristically calculating comprises selecting at least one of said plurality of α-shape based segmentations such that a corresponding α value of a respective α-shape that bounds at least one of said plurality of clusters is minimal.
9. The computerized method of claim 1 , wherein said heuristically calculating comprises selecting at least one of said plurality of α-shape based segmentations such that a corresponding α value of a respective α-shape defined by a minimum number of polygonal cycles has at least one of said plurality of clusters is minimal.
10. The computerized method of claim 1 , wherein said heuristically calculating comprises selecting at least one of said plurality of α-shape based segmentations such that a corresponding α value of a respective α-shape that bounds at least one of said plurality of clusters is maximal.
11. The computerized method of claim 1 , wherein said heuristically calculating comprises heuristically calculating a second of said plurality of α-shape based segmentations based on topological features of respective said plurality of clusters a first of said plurality of α-shape based segmentations.
12. The computerized method of claim 1 , wherein said heuristically calculating comprises heuristically calculating a second of said plurality of α-shape based segmentations based on geometric features of respective said plurality of polygonal areas a first of said plurality of α-shape based segmentations.
13. The computerized method of claim 1 , wherein each one of said α-shape based segmentations bounds a respective cluster from said plurality of clusters and visually marked to indicate spatial points density in said respective cluster.
14. The computerized method of claim 1 , further comprising allowing a user to select any of said plurality of α-shape based segmentations before presenting at least one subsequent α-shape based segmentation from said plurality of α-shape based segmentations.
15. The computerized method of claim 1 , further comprising using colors for at least one of drawing edges between points and filling polygonal areas of said plurality of polygonal areas.
16. The computerized method of claim 1 , wherein said presenting comprises receiving from said operator instructions to at least one of reclustering and restructuring of some of said plurality of polygonal areas.
17. A non-transitory computer program product for computerized clustering method, comprising:
a non-transitory computer readable storage medium;
first program instructions to receive a spatial point dataset comprising a plurality of spatial points in a space;
second program instructions to calculate heuristically a plurality of α-shape based segmentations such that each of said plurality of α-shape based segmentations defines a plurality of polygonal areas that cluster said plurality of spatial points in a plurality of clusters which collectively bounds said plurality of spatial points; and
third program instructions to present to an operator in each sequential iteration of a plurality of sequential iterations another of said plurality of α-shape based segmentations;
fourth program instructions to select by said operator at least one of said plurality of α-shape based segmentations;
wherein said first, second, third, and fourth program instructions are stored on said computer readable storage medium.
18. The non-transitory computer program product of claim 17 , wherein said heuristically calculating comprises selecting at least one of said plurality of α-shape based segmentations such that a corresponding geometric graph that represents a respective α-shape contains only simple polygonal cycles.
19. The non-transitory computer program product of claim 17 , wherein said heuristically calculating comprises dividing said plurality of α-shape based segmentations to a plurality of topologically equivalent classes; selecting one member of said plurality of topologically equivalent classes; wherein said presenting comprises presenting to said operator in each sequential iteration of said plurality of sequential iterations another said member.
20. A clustering system, comprising:
an input module which receives a spatial point dataset comprising a plurality of spatial points in a space;
a processor;
a clustering module which uses said processor for calculating a plurality of α-shape based segmentations such that each of said plurality of α-shape based segmentations defines a plurality of polygonal areas that cluster said plurality of spatial points in a plurality of clusters which collectively bounds said plurality of spatial points;
a user interface module which presents to an operator in each sequential iteration of a plurality of sequential iterations another of said plurality of α-shape based segmentations and allows said operator to select at least one of said plurality of α-shape based segmentations.