[fix] Prevent Overlapping of Clusters in netjsongraph.js #171

[cestercian]

Checklist

• [x] I have read the OpenWISP Contributing Guidelines.
• [x] I have manually tested the changes proposed in this pull request.
• [x] I have written new test cases for new code and/or updated existing tests for changes to existing code.
• [x] I have updated the documentation.

Reference to Existing Issue

Closes #171

Description of Changes

This PR addresses issue #171 by preventing the overlapping of clusters in the netjsongraph.js visualization.

Changes Implemented:

• Introduced spatial indexing using KDBush to optimize clustering performance.
• Implemented grouping of nodes based on proximity and clustering attributes.
• Modified cluster assignment logic to prevent overlapping.
• Updated centroid calculations for accurate cluster placement.
• Ensured better handling of non-clustered nodes.

Testing

A test file (cluster_overlap_test.html) was created to visualize and verify the clustering behavior. The test file simulates overlapping nodes with different statuses and ensures they are properly clustered without overlaps.

Screenshot

[cestercian]

Thanks for the review @nemesifier! The cluster_overlap_test.html file was initially created to visualize the issue, but I removed it since I thought it wasn't necessary after fixing the overlap problem. However, I see your point—it could be useful for verifying improvements. I can reintroduce it and ensure it effectively compares the branch behavior with master. Let me know if you'd like any specific tests included!

[cestercian]

Hi @nemesifier ,

I've made the requested changes:

✅ Moved netjson-cluster-overlap.html to /public/example_templates for consistency. ✅ Updated index.html to include a link to the new example, styled like the others.

Let me know if you need any further modifications or if you'd like me to proceed with replacing the current clustering example with this one. Thanks for your feedback!

[cestercian]

hey @nemesifier

I’ve fixed the issue. The error occurred because the requested file was not being served correctly. I’ve updated netjson-cluster-overlap.html and changed the file location in index.html my latest commit, which should resolve it.

Let me know if you still encounter any issues!

[cestercian]

It looks like the NetJSONGraph library isn't being recognized. This often happens when the project isn't started properly.

@nemesifier, are you running yarn start, or are you just opening the index.html file directly? If you're just opening the file, the dependencies might not be loading correctly. Try starting the project with yarn start and let me know if the issue persists.

[niteshsinha17]

I don't know if I am doing something wrong but this isn't working for me, here's what I see:

netjsongraphjs-clustering-pr.webm @niteshsinha17 do you see a different situation or do you get the same result I get?

@nemesifier I am getting this result. Seems something is wrong. I will look into PR in detail.

[cestercian]

Thank you, @niteshsinha17, for your review and valuable feedback!

I've made the following updates based on your suggestions:

• Updated the CSS import paths to ensure they are loaded from the library, keeping it consistent with other examples.
• Adjusted the styling of the legend to align with existing examples for a uniform look.
• Retained the <script src="../dist/netjsongraph.min.js"></script> line, as it is essential for loading the NetJSONGraph library.
  • Without it, the new NetJSONGraph() constructor would be undefined, causing the graph rendering and clustering logic to fail.

Let me know if there's anything else you'd like me to refine. Thanks again for your insights!

and FYI 😊 the changes that reflect in projects are made to file in example templates directory I don't know why this issue persists Im trying to find the bug, but the changes in the file examples/netjson-cluster-overlap.html doesn't reflect in the demo

[cestercian]

this is output I'm getting, let me know if there are any other issues, Thanks again for the review !!

[cestercian]

I've added more nodes (20-30) so that each status forms a distinct cluster when opening the example.

However, ensuring that the circles display the correct status color when zooming in requires modifying src/js/netjsongraph.config.js, specifically the nodeStyle.color property at line 172 (as seen in the attached screenshot). This change would affect the map rendering across the entire project.

Since this PR is already quite long, I think it would be best to handle this in a separate PR. Would you be open to creating a new issue for this, so we can track and work on it separately?

[cestercian]

Moved cluster overlap prevention logic to lib/js/clusterUtils.js for better modularity.

Changes Made

• Extracted preventClusterOverlap() into clusterUtils.js
• Added setupClusterOverlapPrevention() for centralized event handling
• Updated netjson-cluster-overlap.html to use ES module imports
• Improved README.md with project structure and usage details

[cestercian]

This is what I am seeing:

Peek.2025-03-27.16-56.webm

When zooming in, the circles should appear of the color of their status, not blue. When zooming out, I expect to see a few clusters of different colors, but I see they're overlapping.

Please, in the next iteration post a similar GIF/Webp recording of the result, I am using a Linux program called Peek which is very handy.

Thanks for the feedback, @nemesifier !

I already mentioned the need to modify nodeStyle.color in src/js/netjsongraph.config.js (line 172) in my earlier comment. Since this change affects the entire project’s map rendering, I suggested handling it in a separate PR, since this PR is getting to long already.

Would you be open to creating a new issue for this so we can track it separately?

[cestercian]

when Zoomed IN

When Zoomed OUT

I've made the necessary changes to improve the cluster separation and have included updated images for review. Let me know if there's anything else you'd like to tweak!

[cestercian]

Thanks for the review @nemesifier , I am currently working on it would let you when it's ready for review !!

[cestercian]

Hey @nemesifier is this what were you talking about when zoomed out

[cestercian]

https://github.com/user-attachments/assets/ce5774ea-0e0a-42ec-b305-dab09f9fa55b

[cestercian]

https://github.com/user-attachments/assets/bdc14039-3e95-4360-99f1-61cc264db0f0

Hey @nemesifier , @niteshsinha17 ! I've made a couple of the updates:

• Replaced the main cluster example with my own.
• Adjusted the number of nodes in each cluster so they now vary (e.g. 22, 15, 7, etc.).

However, I haven't yet implemented the fix for the node colors when zooming in — currently, they still appear blue instead of reflecting their actual status color, currently working on it.

Let me know if anything still looks off.

[cestercian]

https://github.com/user-attachments/assets/d37bb25e-8821-488c-9413-06196f706474

Applied Node Coloring based on node status

[cestercian]

Hey @niteshsinha17 , I moved overlap prevention logic from lib/js/clusterUtils.js to src/js/cluster-utils.js, updated imports, and removed the old file. and optimized getNodeStyle() usage in netjsongraph.render.js by properly using all returned style configs.

let me know if any other changes are needed 😁

[niteshsinha17]

@cestercian It's really good you are putting efforts. But I am interested in knowing your observations and reasoning behind your changes.

[cestercian]

https://github.com/user-attachments/assets/8e3c6ec3-bdc3-4f15-a1ce-685f7622afee

Logic Changes for Cluster Separation

Enhanced Cluster Logic:

• Implemented a mechanism to offset clusters of different attribute groups that originate from the same pixel location to prevent overlap.
• Clusters are arranged in a circular pattern using angle-based separation (360° divided by the number of clusters) around the original position using a configurable clusterSeparation distance.
• The offset is calculated in pixels and then converted back to geographical coordinates using Leaflet's containerPointToLatLng method.

[cestercian]

Hey @nemesifier ,

I've updated the clustering logic to form clusters even for single nodes and added test cases to cover this change.

[cestercian]

https://github.com/user-attachments/assets/577a179c-b2a9-4295-8d55-7d18fb115454

made cluster separation robust for all attribute clusters at a location, and then applied a repulsion function to guarantee that all clusters on the map repel each other and never overlap, regardless of their initial positions or sizes.

[cestercian]

@nemesifier I've updated the PR with the requested changes.

Let me know if any other modification are required

[cestercian]

Please squash all the commits into one which will make managing both PRs at the same time easier (#396 and #171).

Squashed in https://github.com/openwisp/netjsongraph.js/pull/349/commits/4aaecad04a674837cacdd698caab7a90ac205f6b

[cestercian]

Hey @nemesifier I have tested the clustering PR with the changes from the streamlining PR by applying new clustering logic to the geojson sample data

[cestercian]

Hey @nemesifier , I've addressed all the changes requested by @niteshsinha17 , and also created new test cases for the coveralls , I've also updated the clustering example to use geojson-saple.json for better testing

Let me know if any other changes are required