By rTIN do you mean this?
http://www.cs.arizona.edu/~gmt/pdf/rtin.pdf
If so, it seems like using general Delaunay Triangulation would not be the
more efficient method to generate the rTIN, and the QuadEdge structure
would not be the most efficient representation.
It sounds like you are well into research territory, unfortunately. And
there's no guarantee that trying to improve the current JTS algorithm will
get you where you want to be. Unfortunately introducing a parallel
paradigm into geometric algorithms usually requires a thorough rethink of
approach. And it can be useful to consider algorithms and structures which
are suboptimal in the sequential context, but which are simple/regular
enough to allow exploiting parallelism easily.
Isenburg has a different approach which involved taking advantage of the
spatial coherency of the input:
http://www.cs.unc.edu/~isenburg/sd/
As I said, it seems like his focus was on massive data volume rather than
performance, but he quotes impressive performance numbers.
On Tue, Aug 6, 2013 at 12:24 PM, Blake Peno <[email protected]> wrote:
> That's kind of what I was worried about...
>
> I'm working with rTIN's which start as a Delaunay Triangulation, which JTS
> helped marvelously for, but once the grid is triangulated, I'm just using
> the QuadEdge functions to do what I may with the "grid".
>
> Everything works great if that's all we look at, but the problem is that
> this becomes marvelously slow as the grid increases in size. My current
> problem with concurrent modification is that the grid is not a viable
> triangulation while the deletions of points and lines are taking place (as
> soon as the operation completes, everything is dandy). This is only a
> problem in the small area around the point that is being worked on, but the
> LastFoundQuadEdge locator gets caught up if I try to locate some other quad
> on the other side of the grid. My next idea is that maybe more than one
> locator could help me out as long as I stay away from locating anywhere
> that is currently being worked on.
>
> I'll check out some of the stuff you talked about, thanks Martin.
>
>
> On Tue, Aug 6, 2013 at 1:44 PM, Martin Davis <[email protected]> wrote:
>
>> AFAIK concurrent algorithms involving triangulations is still an active
>> research area. So there is nothing currently in the JTS code which
>> explicitly supports this. In particular, you are correct in observing that
>> the QuadEdgeSubdivision does not support concurrent modification. This is
>> a hard problem, in general.
>>
>> You might provide a bit more information about the problem you are
>> actually trying to solve using a parallel solution. Is it Delaunay
>> Triangulation, or some variant of that? If so, you might try doing a
>> search for parallel Delaunay algorithms. Agarwhal and Isenburg have some
>> some interesting work in this area (focussed on massive datasets rather
>> than performance, however).
>>
>>
>>
>> On Tue, Aug 6, 2013 at 10:46 AM, Blake Peno <[email protected]>wrote:
>>
>>> Hey everyone.
>>>
>>> I'm getting kinda stuck again, and don't really know how to progress.
>>> I'm attempting to speed up an algorithm I'm working on that is using
>>> QuadEdges to represent data, but I can't seem to find a working way to
>>> accomplish this.
>>>
>>> I've tried concurrently accessing the subdivision for deletions and
>>> whatnot, but due to the way the LastFoundQuadEdgeLocator works, this isn't
>>> really working (NPEs, etc). My second approach was to split my original set
>>> of data into subsets and then merge the subdivisions back together at the
>>> end, but this seems to be a disgusting amount of work that won't actually
>>> speed anything up. Maybe I'm just going about it the wrong way though.
>>>
>>> Does anyone have any idea how I could parallelize something like this,
>>> or at least concurrently access it? I've spent a few too many days getting
>>> nothing done, so I figured I'd ask you guys who actually know what you are
>>> doing.
>>>
>>> Thanks.
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> Get 100% visibility into Java/.NET code with AppDynamics Lite!
>>> It's a free troubleshooting tool designed for production.
>>> Get down to code-level detail for bottlenecks, with <2% overhead.
>>> Download for free and get started troubleshooting in minutes.
>>>
>>> http://pubads.g.doubleclick.net/gampad/clk?id=48897031&iu=/4140/ostg.clktrk
>>> _______________________________________________
>>> Jts-topo-suite-user mailing list
>>> [email protected]
>>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>>>
>>>
>>
>>
>> ------------------------------------------------------------------------------
>> Get 100% visibility into Java/.NET code with AppDynamics Lite!
>> It's a free troubleshooting tool designed for production.
>> Get down to code-level detail for bottlenecks, with <2% overhead.
>> Download for free and get started troubleshooting in minutes.
>>
>> http://pubads.g.doubleclick.net/gampad/clk?id=48897031&iu=/4140/ostg.clktrk
>> _______________________________________________
>> Jts-topo-suite-user mailing list
>> [email protected]
>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
>>
>>
>
------------------------------------------------------------------------------
Get 100% visibility into Java/.NET code with AppDynamics Lite!
It's a free troubleshooting tool designed for production.
Get down to code-level detail for bottlenecks, with <2% overhead.
Download for free and get started troubleshooting in minutes.
http://pubads.g.doubleclick.net/gampad/clk?id=48897031&iu=/4140/ostg.clktrk
_______________________________________________
Jts-topo-suite-user mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
