JTS Topology Suite

On Tue, Dec 4, 2012 at 12:42 PM, Karel Bruneel <karel.bruneel@...:

> Hi Everybody,
>
> I have a Design Ruler Checker that builds a STRtree of all objects on a
> PCB for each check. I now want to make this more dynamic and want to update
> the tree each time an object is moved. I understand this is not possible
> with an STRtree, because it can simply not be updated after the first query.
>
> Am I correct that I should switch to a QuadTree for this purpose?
>

Yes.

>
> If an object is moved, I guess I should remove it from the tree and then
> reinsert it?
>

Yes.

>
> Will this help to make my DRC check faster? Is removing an object and
> reinserting it in a Quadtree faster then rebuilding the complete STRtree?
>

Depends on dataset size, but for larger sizes I think the dynamic QuadTree
should be faster.

Hi Martin

You are amazingly fast :)

I'm experimenting with the quadTree now and I have the feeling that the query returns a lot more results than the STRTree. Could this be, or am I delusional? :)

Thanks!
Karel
 
On Dec 4, 2012, at 9:48 PM, Martin Davis wrote:

> 
> 
> On Tue, Dec 4, 2012 at 12:42 PM, Karel Bruneel <karel.bruneel@...> wrote:
> Hi Everybody,
> 
> I have a Design Ruler Checker that builds a STRtree of all objects on a PCB for each check. I now want to make this more dynamic and want to update the tree each time an object is moved. I understand this is not possible with an STRtree, because it can simply not be updated after the first query.
> 
> Am I correct that I should switch to a QuadTree for this purpose?
> 
> Yes. 
> 
> If an object is moved, I guess I should remove it from the tree and then reinsert it?
> 
> Yes. 
> 
> Will this help to make my DRC check faster? Is removing an object and reinserting it in a Quadtree faster then rebuilding the complete STRtree?
>  
> Depends on dataset size, but for larger sizes I think the dynamic QuadTree should be faster.  
> ------------------------------------------------------------------------------
> LogMeIn Rescue: Anywhere, Anytime Remote support for IT. Free Trial
> Remotely access PCs and mobile devices and provide instant support
> Improve your efficiency, and focus on delivering more value-add services
> Discover what IT Professionals Know. Rescue delivers
> http://p.sf.net/sfu/logmein_12329d2d_______________________________________________
> Jts-topo-suite-user mailing list
> Jts-topo-suite-user@...
> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user

Yes, it does.  This is because it doesn't actually store envelopes for the
items in the tree (in order to save on space).  So what it returns is a
list of candidate items, which is guaranteed to contain the intersecting
items, but maybe other ones as well.  You need to implement a secondary
filter to find the actual intersecting items.  This is usually not a
problem - just check for envelope intersection before using each query
result item.

Hopefully this is clear from the class Javadoc.

On Tue, Dec 4, 2012 at 3:11 PM, Karel Bruneel <karel.bruneel@...:

> Hi Martin
>
> You are amazingly fast :)
>
> I'm experimenting with the quadTree now and I have the feeling that the
> query returns a lot more results than the STRTree. Could this be, or am I
> delusional? :)
>
> Thanks!
> Karel
>
> On Dec 4, 2012, at 9:48 PM, Martin Davis wrote:
>
> >
> >
> > On Tue, Dec 4, 2012 at 12:42 PM, Karel Bruneel <karel.bruneel@...>
> wrote:
> > Hi Everybody,
> >
> > I have a Design Ruler Checker that builds a STRtree of all objects on a
> PCB for each check. I now want to make this more dynamic and want to update
> the tree each time an object is moved. I understand this is not possible
> with an STRtree, because it can simply not be updated after the first query.
> >
> > Am I correct that I should switch to a QuadTree for this purpose?
> >
> > Yes.
> >
> > If an object is moved, I guess I should remove it from the tree and then
> reinsert it?
> >
> > Yes.
> >
> > Will this help to make my DRC check faster? Is removing an object and
> reinserting it in a Quadtree faster then rebuilding the complete STRtree?
> >
> > Depends on dataset size, but for larger sizes I think the dynamic
> QuadTree should be faster.
> >
> ------------------------------------------------------------------------------
> > LogMeIn Rescue: Anywhere, Anytime Remote support for IT. Free Trial
> > Remotely access PCs and mobile devices and provide instant support
> > Improve your efficiency, and focus on delivering more value-add services
> > Discover what IT Professionals Know. Rescue delivers
> >
> http://p.sf.net/sfu/logmein_12329d2d_______________________________________________
> > Jts-topo-suite-user mailing list
> > Jts-topo-suite-user@...
> > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>
>