GSoC: Find and implement a new label positioning algorithm

[larsyencken]

DIFFICULTY: MEDIUM, SIZE: 175 HOURS

Overview

Our scatter plots currently have labels directly next to points:

The algorithm we use for positioning the labels is quite basic and often leads to labels or points being hidden behind other labels or points. We would like to have a new label positioning algorithm that is performant and produces better results – less overlaps and improved positioning.

A better label positioning algorithm would potentially also make it possible for us to add labels directly on the plots of other charts, instead of having separate sections allocated to legends.

Required skills

• Javascript/Typescript
• React (bonus)
• Data visualisation (bonus)

Potential mentors

• @danielgavrilov
• @danyx23

Related links

• Vega-Lite Label Transforms
• Fast and Flexible Overlap Detection for Chart Labeling with Occupancy Bitmap

[togami2864]

Hi @larsyencken. I'm interested in this project as GSoC 2022.
I've set up the local environment of this repository and got some questions.

1. Will this project start with a survey of papers like the ones in the Related Link?

2. I was not able to find where the specific values of the positions that are passed to the ScatterPointsWithLabels component are obtained from. Is it from the server side?
   It would be helpful if you could tell me.

Thanks.

[danyx23]

Hi Togami!

Great that you have managed to set up the projects and thank you for you very good questions!

To answer your questions:

1. That is a possibility, yes. One important constraint is that the runtime performance of this has to be relatively good as we need to be able to run this for many dozens of labels and it should be done within a fraction of a second even on an older mobile device. I think it would be wise to plan a bit of time for looking at prior art but also to leave a good amount of time later in the project for performance tweaking. Totally optimal placement is less important for us than having a fast implementation.

2. Yes this is a bit opaque to understand. One key part is in initialRenderSeries where the domain values series.points is transformed into ScatterRenderPoint objects. I.e. this is where domain values get placed on the actual axis (using xAxis.place(point.x) and similar for y). If you follow the .seriesArray property then you see that this is set via props on construction and the data is actually prepared in ScatterPlotChart.series() which uses the data slightly process from the .transformedTable property. Transformed table is the tabular data structure that every chart builds for itself that contains the data. The data source can be either embedded data from the GrapherConfig (the json structure that configures a chart), a separate json file (this is what is used on most charts on our live website) or a CSV file (this is used for explorers on our site). If you look at the tests for the scatter plot chart then you can see yet another way to feed data into.

I hope this has answered your questions. Let me know if you need any further help and please feel free to email me any drafts for your proposal to [email protected]. Thanks!

[togami2864]

@danyx23
Hi. I send a draft of my proposal. I would be happy to get feedback.

[waiting4U0]

@danielgavrilov @danyx23, how are you today? I'm Yuting Zeng, a third-year undergraduate student at Southwest Petroleum University studying Information Management and Information Systems. I've been programming for around two years. I prefer visuals and charts because they help people understand and accept information more easily. I'm highly interested in data-related and open-source projects, and I'd want to contribute some code to this project.
As a team leader, my team and I have developed an app for medical IoT applications using uni-app. (uni-app is a Vue-based unified framework for designing applets, H5, and apps.) Front-end visualization and graphical presentation of some vital data are implemented in the app. I've also used uni-app to create the front-end for a WeChat applet for a student group. I've been introduced to data analysis and data mining this year. I've used Python for data visualization and other data pre-processing of large data to train machine learning classification models using CCL signal data from many oil and gas wells, and I'm trying to create a paper and publish it.
I feel I possess the necessary qualifications to work on this project. I am a quick learner who is always looking for fresh information.
I really want to help with this GSoC'22 project, however, this is my first foray into the open-source world. Could you kindly advise me on how to get started on this project and the proposal for it?

[danyx23]

Hi Yuting!

As I said in the other thread, a good next step is for you to try and start sketching out a proposal and formulating the project and it's benefits in your own words. Feel free to send me any drafts to [email protected]!

[ktk53x]

I am a Computer Science undergraduate at the Indian Institute of Technology Guwahati, India [IITG]. I have been working on Distributed Computing, Algorithms and Data Structures courses for over a year.
I have worked in C++, Python and Javascript as my primary languages.

I have decent participation in Algorithmic and Mathematical challenges on competitive programming platforms such as Codeforces, CodeChef, HackerRank, etc.
I have a decent hold over Geometry, Algorithms, and Mathematics in general.

I am particularly interested in this project.
I am currently going through the mentioned research papers and understanding the algorithms and will look for more papers regarding the papers.

How should I move further, what should be the optimal path to be followed?

[danyx23]

Hi @ktk53x!

Nice to hear that you are interested in contributing to GSoC with us! Could I ask you to write an email to [email protected] if you haven't done so already? This will help us track all applicants and communicate occasional updates to everyone. Thanks!

Great to hear that you are already looking into algorithms! A good next step would be for you to start sketching out the core of your proposal, i.e. to understand more about how our Grapher works and what this project would add. If you have any specific questions of understanding please feel free to ask here. When you have a first sketch of the proposal text please send it to me at [email protected] and I'll give you feedback on the draft.

It is probably helpful if you follow our documentation and are able to compile Grapher and run the tests on your machine.