Answers.Body: <p>One solution can be a computational geometric approach. First grid the plane of points with the desired size, denoted by <span class="math-container">$\epsilon$</span>. Then, row by row, find the points (you can make an appropriate data structure, for example, KD-tree, to have an efficient search). Now, you can decide how many rows of gap are required between two sets of points that should be counted until starting a new line of points. Finally, according to this row index for each point, rank them from 1 to <span class="math-container">$n$</span>, from left to right of each line (sort all points of each line based on their <span class="math-container">$x$</span> coordinate value).</p>
  <p>There are two clear advantages to this method:</p>
  <ol>
  <li>it is easy to be implemented.</li>
  <li>it can be easily employed to work for any number of points.</li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-12-14T14:35:28.587Z
Answers.LastActivityDate: 2022-12-14T14:35:28.587Z
Answers.UserDisplayName: OmG
Body: <p>I have a problem wherein I have 2D points in an image that would be associated with a corresponding label/sequence number. For instance following are 4 such examples:</p>
  <p><a href="https://i.sstatic.net/GpwgF.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/GpwgF.png" alt="2D points" /></a></p>
  <p>As you can see all of them have a certain sequence. As if a human were to read them (left to right, top to bottom) but in some cases, it's a little more complicated (see bottom right example above)</p>
  <p>As of yet, I am using simple X-Y co-ordinate based sorting to figure out the sequence but it doesn't always work (imagine example top left above, but all the points are arranged at an angle) I'm trying to approach this from a machine learning angle and curious to know how would you do it.</p>
  <p>Another challenge is there could be arbitrary number of such points (anywhere between 4 to 16)</p>
  <p>We can for instance, use a Neural Network, or an SVM based classifier where the features would be normalized x,y co-ordinates, but I'm wondering if there's a simpler way to do it. Furthermore, I will have to use a lot of augmentations since the output has to be permutation invariant.</p>
  <p>I have looked at Geometric Deep Learning based point segmentation methods like <a href="https://arxiv.org/abs/1612.00593" rel="nofollow noreferrer">PointNet</a>, <a href="https://arxiv.org/abs/1801.07791" rel="nofollow noreferrer">PointCNN</a>, and so forth but these methods mainly work with point clouds, and would be an overkill for my purpose.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-12-12T23:37:14.523Z
Comments.Text: To me it looks like you could cover this change of the labeling strategy (top-left vs. bottom-right) with a clustering method. First, look if there are clear clusters, if yes number each cluster separately, if no clear clusters then just label 'line-by-line'. If you can use a bit more domain knowledge (where do the points come from; where do the labels come from; ...) try to do that as well.
Comments.UserDisplayName: Chillston
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-12-12T23:41:01.413Z
Comments.Text: And a small heads up: You wouldn't want the output to be permutation invariant, but permutation equivariant (as you want your labels to permute similar to the points). Invariant would mean that you get the same result for permuted input.
Comments.UserDisplayName: Chillston
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-12-23T18:02:11.200Z
Comments.Text: Yes, would want it to be permutation equivariant +1
Comments.UserDisplayName: Mayur Kulkarni
Tags: <neural-networks><geometric-deep-learning><support-vector-machine>
Title: Machine learning for arranging 2D points
UserDisplayName: Mayur Kulkarni
ThreadText: # Machine learning for arranging 2D points
  
  (Asked by: username_0 on 2022-12-12)
  
  I have a problem wherein I have 2D points in an image that would be associated with a corresponding label/sequence number. For instance following are 4 such examples:
  
  [![2D points](https://i.sstatic.net/GpwgF.png)](https://i.sstatic.net/GpwgF.png)
  
  As you can see all of them have a certain sequence. As if a human were to read them (left to right, top to bottom) but in some cases, it's a little more complicated (see bottom right example above)
  
  As of yet, I am using simple X-Y co-ordinate based sorting to figure out the sequence but it doesn't always work (imagine example top left above, but all the points are arranged at an angle) I'm trying to approach this from a machine learning angle and curious to know how would you do it.
  
  Another challenge is there could be arbitrary number of such points (anywhere between 4 to 16)
  
  We can for instance, use a Neural Network, or an SVM based classifier where the features would be normalized x,y co-ordinates, but I'm wondering if there's a simpler way to do it. Furthermore, I will have to use a lot of augmentations since the output has to be permutation invariant.
  
  I have looked at Geometric Deep Learning based point segmentation methods like [PointNet](https://arxiv.org/abs/1612.00593), [PointCNN](https://arxiv.org/abs/1801.07791), and so forth but these methods mainly work with point clouds, and would be an overkill for my purpose.
  
  **Tags:** neural-networks, geometric-deep-learning, support-vector-machine
  > **Comments:**
  > **username_1**: To me it looks like you could cover this change of the labeling strategy (top-left vs. bottom-right) with a clustering method. First, look if there are clear clusters, if yes number each cluster separately, if no clear clusters then just label 'line-by-line'. If you can use a bit more domain knowledge (where do the points come from; where do the labels come from; ...) try to do that as well.  
  > **username_1**: And a small heads up: You wouldn't want the output to be permutation invariant, but permutation equivariant (as you want your labels to permute similar to the points). Invariant would mean that you get the same result for permuted input.  
  > **username_0**: Yes, would want it to be permutation equivariant +1  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2022-12-14. Score: 0
  
  One solution can be a computational geometric approach. First grid the plane of points with the desired size, denoted by $\epsilon$. Then, row by row, find the points (you can make an appropriate data structure, for example, KD-tree, to have an efficient search). Now, you can decide how many rows of gap are required between two sets of points that should be counted until starting a new line of points. Finally, according to this row index for each point, rank them from 1 to $n$, from left to right of each line (sort all points of each line based on their $x$ coordinate value).
  
  There are two clear advantages to this method:
  
  1. it is easy to be implemented.
  2. it can be easily employed to work for any number of points.
  
  
  ---
  
  