Group By

[Dan Mos]

Hy, Why not use a where clause. Something like:

var enabledPoints = (from rec in points
where rec.Enabled
select new
{
Enabled = true,
Pointt = String.Format("({0},{1})", rec.X, rec.Y)
}).ToList();

[Lost User]

Doesn't that just return all of the points that are enabled? I need them grouped when they are next to each other (x or y). So my example I posted in the first message should return 2 groups of enabled points.

ASCII stupid question, get a stupid ANSI

[Lost User]

Another way to explain what I am doing is BLOBing (Binary Large OBjects) but I want to do it after the fact. Most algorithms make a modifcation (binary part.. i.e. IsEnabled) and then look at other BLOBs to see if it belongs. I would like to skip the check state and use querying one time via some other event. Any insight into this?

ASCII stupid question, get a stupid ANSI

[Dan Mos]

yes it does. ;P

[Dan Mos]

define "connections". Is it like a graph? When are 2 points connected?

[Lost User]

Yes Like a graph. so my example I made a 10x10 plot and had various points in it. My origin is Upper Left (0,0) and expands right and downward (as an image does) (2,2) has 8 neighbors as do all locations (1,1) -upper left(if this is too difficult then it can be worked around, meaning diagnols. In that case all locations have 4 neighbors) (2,1) -above (3,1) - upper right (diagnol) (1,2) - Left (3,2) -right (1,3) -lower left (2,3) - bellow (3,3) -lower right

ASCII stupid question, get a stupid ANSI

[Gideon Engelberth]

You could create a custom IEqualityComparer that uses the Equals method to do "near" comparisons instead of the typical meaning of equals. The comparer could keep some state to know which points have already been added, and group new points as "equal" to other "nearby" points. Something like this could get you started:

Public Class NearEqualityComparer
Implements IEqualityComparer(Of CustomPoint)

Public Sub New(ByVal xRange As Integer, ByVal yRange As Integer)
    \_xRange = xRange
    \_yRange = yRange
End Sub

Private \_xRange As Integer
Private \_yRange As Integer
Private \_groups As New List(Of HashSet(Of CustomPoint))

Public Overloads Function Equals(ByVal x As CustomPoint, ByVal y As CustomPoint) As Boolean \_
  Implements System.Collections.Generic.IEqualityComparer(Of CustomPoint).Equals
    Return FindOrCreateGroup(x) Is FindOrCreateGroup(y)
End Function

Public Overloads Function GetHashCode(ByVal obj As CustomPoint) As Integer \_
  Implements System.Collections.Generic.IEqualityComparer(Of CustomPoint).GetHashCode
    'always return the same hash code to let Equals do the work
    Return 1
End Function

Private Function PointNearGroup(ByVal newPoint As CustomPoint, \_
                                ByVal group As IEnumerable(Of CustomPoint)) As Boolean
    Return group.Any(Function(oldPoint) Math.Abs(newPoint.X - oldPoint.X) <= \_xRange AndAlso \_
                                        Math.Abs(newPoint.Y - oldPoint.Y) <= \_yRange)
End Function

Private Function FindOrCreateGroup(ByVal point As CustomPoint) As HashSet(Of CustomPoint)
    Dim matchingGroup = (From g In \_groups \_
                         Where PointNearGroup(point, g)).FirstOrDefault()

    If matchingGroup Is Nothing Then
        matchingGroup = New HashSet(Of CustomPoint)()
        \_groups.Add(matchingGroup)
    End If
    matchingGroup.Add(point)
    Return matchingGroup
End Function

End Class

This will not catch certain cases where you may have two groups that are not connected at first, but a later row connects them through a set of points. (In fact, that may not be possible with the framework GroupBy, since I do not know of any way to tell it to merge groups.) However, it should at least give you an idea of how this might work. And in actuality, this ends up doing all the work that GroupBy is doing anyway, so you do not really gain much

[Lost User]

OK Thank you! I had tried something similar lacking the FindOrCreateGroup... Alls that did was return a whole bunch of small groups. I ama C#er so I had to take some time to review your code. I think something is still missing. Won't this just return a group of xrange yrange? I need the connected points to grow as long as they have some bool set. There should not be a limiting range. Range should only tell a point it is next to a point and it should be 1 (i.e. hard coded). Maybe I am missing something and the code will return the connections. Still investigating. [EDIT] Got it to work. Thank you! This should work!!!

ASCII stupid question, get a stupid ANSI

modified on Tuesday, March 23, 2010 4:25 PM

[Eslam Afifi]

So, you have a 2D array? If so, you can use Flood fill[^], Scanline fill[^] (which is actually an improved flood fill) or Connected Component Labeling[^]. If it's a collection of points, create a 2D array representation of the points and apply one of those algorithms. Or you may be able apply one of those logics to the collection. Whichever suits your needs.

Eslam Afifi

[Lost User]

Well I think you understand what I am doing but I am trying to avoid large loops. Our ROIs are numerous and large so if I am going to do that logic I should just use BLOB ing methods[^] since they are actively done. I was trying to see if there was a way to avoid the Group merging etc that comes along with it though by using LINQ and doing a query of my settable attributes afterwards. It seems the beenefit is lacking though since the Query will take more time than the combined hit of merginging all groups as they are created.

ASCII stupid question, get a stupid ANSI

[Eslam Afifi]

I assumed you were talking about LINQ-to-Objects so I didn't put a database into consideration while answering your question. I'm not aware of the BLOBing methods that you mentioned. Would you please provide a link to those methods? Are those points stored in a table or are they calculated per query? Is it possible to just store references to connected points (blobs) in another table and update it upon creation/deletion/modification of the points? Are the points' range so large that you can't represent them in a 2D array to perform scanline fill? I think you should say more about the nature of the data (the range of point's, how many blobs expected, how many points per blob, how many points are expected to be returned from a query...). I've read Gideon Engelberth[^] answer and it's checking for 8-connectivity. But you may need another pass over the groups to merge them, but that would be computationally expensive since you'll be determining whether 2 groups are connected or not by comparing the edges of the groups together (which requires calculating the edges of the groups during or after the first pass).

Eslam Afifi