Group By

Lost User

Say I have a custom object with parameters int XLoc int YLoc bool IsEnabled I would like to return groups connecting that have the enabled set. So then lets say I have a collection of thes eobjects (lets call them points cause of the X and Y) and there are 100 of them, being (0,0) through (10, 10). Then I go through and I flip some of the enabled flags for (2,3) (2,4) (3,3) (5,8) (5,9) (6,8) I would like a grouping of how I have displayed them. Essentially if they have connections and are enabled they become a group. Can this be done using the GroupBy ?

ASCII stupid question, get a stupid ANSI

dan sh

I don't have VS right now so I have nto verified. But I guess, this[^] should help.

Lost User

Yes I have been looking at that but the difficult part is the data is like a matrix. So using that methodaology I have 2 choices (I think) IEquality or ICompare If I use IEquality I am saying that each element is equal to each element it is next to... Obviously that logic is flawed since all elements then end up equal. So if it is ICompare I need to think of it in a sorting matter... Well how does one sort a 2D Array into a logical 1D array maintaining the 2Ds.. I dont think it can be done. But maybe I am missing something....

ASCII stupid question, get a stupid ANSI

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