2d rectangle overlap find and filter

[ralstogj]

Hi

I am updating some 20 year old code in Autocad lisp that takes rectangles that
surround text items and searches for text rectangles that overlap and filters out text based on a third elevation criteria.

The raw data comes from scans of the sea floor and there can be 1000's of text rectangles. The existing rountine is just a loop that takes hours to run for large datasets.

I found this discussion http://www.gamedev.net/community/forums/topic.asp?topic_id=445256 in a game programming forum from a couple of years ago where an r-tree is suggested as a good solution for a similar problem. Is there a build in r-tree type function in Autocad or something similar does anyone have some r-tree vb.net code or some other suggestion of how I could use built in functions in Autocad to search quickly
for the overlapping rectangles.


Regards


Justin Ralston

[Anonymous]

http://www.codeproject.com/KB/recipes/QuadTree.aspx

--
http://www.caddzone.com

AcadXTabs: MDI Document Tabs for AutoCAD
Supporting AutoCAD 2000 through 2010

http://www.acadxtabs.com

Email: string.Format("{0}@{1}.com", "tonyt", "caddzone");

wrote in message news:6250388@discussion.autodesk.com...
Hi

I am updating some 20 year old code in Autocad lisp that takes rectangles
that
surround text items and searches for text rectangles that overlap and
filters out text based on a third elevation criteria.

The raw data comes from scans of the sea floor and there can be 1000's of
text rectangles. The existing rountine is just a loop that takes hours to
run for large datasets.

I found this discussion
http://www.gamedev.net/community/forums/topic.asp?topic_id=445256 in a game
programming forum from a couple of years ago where an r-tree is suggested as
a good solution for a similar problem. Is there a build in r-tree type
function in Autocad or something similar does anyone have some r-tree vb.net
code or some other suggestion of how I could use built in functions in
Autocad to search quickly
for the overlapping rectangles.


Regards


Justin Ralston

[ralstogj]

Thanks for the link Tony

[ralstogj]

Hi Tony

Access the C# dll code is something I have never done before I have referenced the .dll ok and come up with the following to load rectangles into the tree and query it. But do not know how to define a rectangle object correctly or define the item as an IHasRect correctly for the tree definition. If you could provide an example of how you would do it that would be great.

Regards


Justin Ralston



Public Sub Find_Overlapping_Text()

'Create the quadtree using the C# .dll from the website http://www.codeproject.com/KB/recipes/QuadTree.aspx
'to the extents of the points text

'To access the C# code that you want it be compiled as a DLL. Once that is done,
'simple add a reference to that project to your VB.Net project, import the namespace you need,
'and then you can use the C# code

Dim r As Rectangle = (100),100,100,100) 'Me.ClientRectangle
Dim item As IHasRect

Dim m_quadTree As New QuadTree(Of Item)(r)
'Dim m_quadTree As New QuadTree(Of Item)(Me.ClientRectangle)

'add random points (text rectangles) into the quadtree for querying

Random(rand = New Random(DateTime.Now.Millisecond))
m_quadTree.Add(New Item(e.Location, rand.Next(25) + 4))


'loop through all the text rectangles and
'Query the quadtree with a rectangle to find any other text objects under it
Dim m_selectionRect As Rectangle = (20),20,20,20)
m_selectedItems = m_quadTree.Query(m_selectionRect)

End Sub