Straight walk over triangulation

[micycle1]

I've been doing some work with voronoi diagrams and would find it useful to perform a straight walk over the triangulation from one point to another (my use case would be to crop the voronoi diagram's thiessen polygon lines to the constrained polygon triangulation from which it was made).

In other words: functionality to return which triangles/edges overlap with a line segment given by a start and end coordinate in an efficient manner.

[gwlucastrig]

Interesting problem. How many vertices in the triangulation?

…

On Thu, Apr 8, 2021, 5:15 PM Michael Carleton ***@***.***> wrote: I've been doing some work with voronoi diagrams and would find it useful to perform a straight walk over the triangulation (in order to crop the voronoi diagram's thiessen polygon lines to the constrained polygon triangulation from which it was made). In other words: functionality to return which triangles/edges overlap with a line segment given by a start and end coordinate in an efficient manner. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#70>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AEWJDYPFFBYQTG47R7RYWYTTHYMIBANCNFSM42TWOQSQ> .

[micycle1]

Up to a few thousand I suppose.

[gwlucastrig]

Your data set is small enough that you should be able to take a brute-force approach and let the computer do all the hard work.

I would loop over the edges in the triangulation using the edge iterator (which is the preferred method of doing so) and solve for intersections using the parametric equation for a straight line. Then I would sort the intersections by their distance along the segment of interest.
for(IQuadEdge edge: tin.edges()){ // solve for intersections }

The iterator filters out the ghost edges (the ones that have null vertices), so that makes things simpler.

Alternately, if you had your Voronoi diagrams Thiessen polygons in a finite form, you could get the convex hull from the TIN using Tinfour's getPerimeter() method, and then use a 3rd party API to compute the intersection of your polygons and the convex hull polygon. I believe that the Java Area class might support this operation. But I would also recommend looking at the Java Topology Suite (JTS) which has very good implementations of that kind of geometric operations and is a reasonably sized API.

Tinfour does have a "bounded Voronoi" implementation, but I haven't used it extensively and it is not written to the same standard as the Delaunay code. I've mainly used it for drawing pictures for some of the Tinfour documentation.

This weekend, I can take a crack at some code for the intersection computations if you need it. I have various pieces lying around, I would just have to assemble them into an appropriate form. Let me know.

[micycle1]

This was actually motivated by trying to avoid JTS' geometry intersection() since that was very slow. I've since used its sweep-line segment intersection implementation and it's much faster.

[gwlucastrig]

That is major cool.

…

On Sat, Apr 10, 2021, 6:34 PM Michael Carleton ***@***.***> wrote: This was actually motivated by trying to avoid JTS' geometry intersection() since that was very slow. I've since used its sweep-line segment intersection implementation and it's much faster. [image: image] <https://user-images.githubusercontent.com/9304234/114285594-44f68580-9a50-11eb-8555-887f74662016.png> — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#70 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AEWJDYKPAOZJFUCEYJBDHULTIDG6VANCNFSM42TWOQSQ> .

[gwlucastrig]

How did you do it? I did some work a few years back trying to use Vincente's algorithm to find the median lines of a fish silhouette, but this is so much better than what I was able to accomplish.

…

On Sat, Apr 10, 2021, 7:14 PM Gary Lucas ***@***.***> wrote: That is major cool. On Sat, Apr 10, 2021, 6:34 PM Michael Carleton ***@***.***> wrote: > This was actually motivated by trying to avoid JTS' geometry > intersection() since that was very slow. I've since used its sweep-line > segment intersection implementation and it's much faster. > > [image: image] > <https://user-images.githubusercontent.com/9304234/114285594-44f68580-9a50-11eb-8555-887f74662016.png> > > — > You are receiving this because you commented. > Reply to this email directly, view it on GitHub > <#70 (reply in thread)>, > or unsubscribe > <https://github.com/notifications/unsubscribe-auth/AEWJDYKPAOZJFUCEYJBDHULTIDG6VANCNFSM42TWOQSQ> > . >

[micycle1]

How did you do it?

Code

find the median lines

I'm actually in the middle of creating a medial axis library backed by TinFour. Most of it is done -- I just need to clean the code and repo up a little. It finds the axis lines by joining triangle circumcenters, which is basically equivalent to using the voronoi diagram, filtering out all edges that are not contained entirely within the shape.