jvx.geom
Class PwGeodesic

java.lang.Object
  jv.object.PsObject
      jvx.project.PjWorkshop
          jvx.geom.PwGeodesic

All Implemented Interfaces:

java.lang.Cloneable, PjWorkshopIf, PsUpdateIf, PvPickListenerIf, java.io.Serializable

public class PwGeodesic

extends PjWorkshop

implements PvPickListenerIf

Workshop for the computation of shortest and straightest geodesics that connect two given points on an element set. Can be used as numerics library if only static method getShortest(...) is used, or as a workshop by creating an instance of PwGeodesic and registering a geometry and a display. Pick events will be caught in the second case and the curve automatically computed. You can access the computed curve by method getPolygon(). After use as a workshop you need to call close() to tidy things up!

See Also:

Serialized Form

Field Summary

static int	SHORTEST Method is set to this if pick events shall result in computation of shortest geodesics.
static int	SHORTEST_DIJKSTRA Initial triangle run for SHORTEST is selected by smallest face-dijkstra distance.
static int	SHORTEST_DIJKSTRA_REUSE Initial triangle run for SHORTEST is selected by smallest face-dijkstra distance if new end/start face is not neighbouring old end/start face.
static int	SHORTEST_ELEMENT_TREE Initial triangle run for SHORTEST is selected by smallest face-dijkstra distance.
static int	SHORTEST_EUCL_DIJKSTRA Initial triangle run for SHORTEST is selected by smallest euclidean face-dijkstra distance.
static int	STRAIGHTEST Method is set to this if pick events shall result in computation straightest geodesics.

Fields inherited from class jv.object.PsObject

HAS_CONFIG_PANEL, HAS_INFO_PANEL, HAS_LABEL_PANEL, HAS_MATERIAL_PANEL, HAS_TEXTURE_PANEL, HAS_VECTOR_PANEL, INSPECTOR_INFO, INSPECTOR_INFO_EXT, IS_DELETED, IS_FIXED, IS_FOCUSSED, IS_PICKED, IS_SELECTED, IS_USED, NUM_TAGS

Constructor Summary

PwGeodesic()

Method Summary

void	cancel() Cancels and closes the workshop (removing the computed geodesic from display).
void	close() Has to be called to remove workshop from element set as update listener and to remove polygon from display.
void	computeWay() Initiates re-calculation of geodesic.
void	dragDisplay(PvPickEvent pos) Drag a location in the display with 2d display and 3d world coordinates.
void	dragInitial(PvPickEvent pos) Drag an arbitrary point along a geometry, point may lie inside an element.
void	dragVertex(PgGeometryIf geom, int index, PdVector vertex) Drag a picked vertex of a geometry.
double	getActualLength() The current actual length of the computed geodesic.
double	getAngle()
static int[]	getConnectingStrip(PgElementSet geom, int startelem, int endelem) Gets a strip from startelem to endelem by marking the elements (beginning with startelem) and their neighbours with the 'distance' to the starting element (measured in 'number of elements') until the endelement is reached.
static PiVector	getDijkstraDistance(PgElementSet geom, PiVector front) Computes the combinatorial edge distance of all vertices to a given center vertex respectively on a given set of vertices using Dijkstra's algorithm.
PvDisplayIf	getDisplay() Display where geodesics are shown and where pick events are caught from.
static PdVector	getEuclideanDijkstraDistance(PgElementSet geom, PiVector front) Computes the combinatorial edge distance of all vertices to a given center vertex respectively on a given set of vertices using Dijkstra's algorithm.
int	getMethod() Whether shortest or straightest geodesics are computed.
PgPolygon	getPolygon() The computed geodesic as an independent n-dimensional polygon.
PgPolygonOnElementSet	getPolygonOnElementSet() The computed geodesic as a polygon that depends on the geometry.
static PgPolygonOnElementSet	getShortest(PgElementSet geom, PdBary start, int startelem, PdBary end, int endelem) Computes a shortest geodesic that connects given points on a triangulation.
static PgPolygonOnElementSet	getShortest(PgElementSet geom, PdBary start, int startelem, PdBary end, int endelem, PiVector trianglerun, PgPolygonOnElementSet outpoly) Computes a shortest geodesic that connects given points on a triangulation.
static PgPolygonOnElementSet	getShortest(PgElementSet geom, PdBary start, int startelem, PdBary end, int endelem, PiVector trianglerun, PgPolygonOnElementSet outpoly, PgElementSet unfolded, PiVector vertexlist, PiVector left, PiVector right, PdVector previous, PdVector next, PdVector t2d, PdBary tempbary) Computes a shortest geodesic that connects given points on a triangulation.
static PgPolygon[]	getShortestInStrip(PgElementSet geom, PdBary start, PdBary end, int[] strip, PiVector outSide, PiVector outvertind, PdBaryDir initialDir) Deprecated. since 06.05.04, use getShortestInUnfoldedTriangleRun(...) instead.
static PiVector	getShortestInUnfoldedTriangleRun(PgElementSet unfolded, PiVector left, PiVector right, PiVector output) Takes a triangle run (unfolded to 2d) and computes the shortest connection in this closed polygon between the start and end vertex.
int	getShortestMode() If shortest geodesics are computed, you have several different choices which local minimum is computed.
void	init() Sets the default length, angle and method.
static boolean	isConnected(PiVector[] neighb, PiVector elementrun) Checks whether the given element indices belong to an edge connected element run.
void	markVertices(PvPickEvent pos) Mark a set of vertices of a geometry within a given bounding box.
void	ok() Accept current version of the geometry as new version.
void	pickDisplay(PvPickEvent pos) Get a location in the display with 2d display and 3d world coordinates.
void	pickInitial(PvPickEvent pos) Pick an arbitrary point on a geometry, point may lie inside an element.
void	pickVertex(PgGeometryIf geom, int index, PdVector vertex) Get a picked vertex of a geometry.
void	removeGeometry() Remove the assigned geometry and its backup clone.
static int	removeLoops(int[] source, int len, int[] temp) Removes subintervals with same starting and ending value (processing from left to right), for instance 10,9,5,7,2,10,2 becomes 10,2
void	selectGeometry(PgGeometryIf geom) Currently not supported by display.
void	setAngle(double angle)
void	setDisplay(PvDisplayIf disp) Sets the display where the resulting geodesic shall be shown.
void	setEndBary(PdBary bary) Set the endpoint of the geodesic.
void	setEndElement(int elemindex) Set the element where the geodesic shall end in.
void	setGeometry(PgElementSet elemset) Geodesics are computed on the given surface.
void	setMethod(int mode) Set whether shortest or straightest geodesics are computed.
void	setPickFirst() User shall pick starting point.
void	setPickLast() User shall pick endpoint.
void	setShortestMode(int flag) If shortest geodesics are computed, you have several different choices which local minimum is computed.
void	setStartBary(PdBary bary) Set the starting point of the geodesic.
void	setStartElement(int elemindex) Set the element where the geodesic shall start in.
void	showWay() Deprecated. Use computeWay() instead.
static PiVector	unfoldTriangleRun(PgElementSet geom, PiVector run, PgElementSet unfolded, PiVector left, PiVector right) Triangle number i in given run is triangle i in unfolded geometry.
void	unmarkVertices(PvPickEvent pos) Unmark a set of vertices of a geometry within a given bounding box.
boolean	update(java.lang.Object event) Update the class whenever a child has changed.

Methods inherited from class jvx.project.PjWorkshop

getDisplays, getGeometry, getSavedGeometry, getViewer, isModal, reset, setDisplays, setGeometry, setModal, setViewer

Methods inherited from class jv.object.PsObject

addInspector, addUpdateListener, assureInspector, clearTag, clone, clone, clone, copy, getFather, getInfoPanel, getInspector, getName, getNumObjects, getSymbol, hasInspector, hasTag, hasUpdateListener, instanceOf, instanceOf, newInspector, newInspector, removeInspector, removeInspector, removeUpdateListener, setName, setParent, setSymbol, setTag, toString, updatePanels

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface jv.project.PvPickListenerIf

getName

Methods inherited from interface jv.object.PsUpdateIf

getFather, getName, setParent

Field Detail

SHORTEST

public static final int SHORTEST

Method is set to this if pick events shall result in computation of shortest geodesics.

See Also:

Constant Field Values

STRAIGHTEST

public static final int STRAIGHTEST

Method is set to this if pick events shall result in computation straightest geodesics.

See Also:

Constant Field Values

SHORTEST_DIJKSTRA

public static final int SHORTEST_DIJKSTRA

Initial triangle run for SHORTEST is selected by smallest face-dijkstra distance.

See Also:

Constant Field Values

SHORTEST_DIJKSTRA_REUSE

public static final int SHORTEST_DIJKSTRA_REUSE

Initial triangle run for SHORTEST is selected by smallest face-dijkstra distance if new end/start face is not neighbouring old end/start face.

See Also:

Constant Field Values

SHORTEST_EUCL_DIJKSTRA

public static final int SHORTEST_EUCL_DIJKSTRA

Initial triangle run for SHORTEST is selected by smallest euclidean face-dijkstra distance.

See Also:

Constant Field Values

SHORTEST_ELEMENT_TREE

public static final int SHORTEST_ELEMENT_TREE

Initial triangle run for SHORTEST is selected by smallest face-dijkstra distance.

See Also:

Constant Field Values

Constructor Detail

PwGeodesic

public PwGeodesic()

Method Detail

init

public void init()

Sets the default length, angle and method. Does not remove the settings for the geometry or display.

Overrides:

init in class PjWorkshop

update

public boolean update(java.lang.Object event)

Update the class whenever a child has changed. Method is usually invoked from the children.

Specified by:

update in interface PsUpdateIf

Overrides:

update in class PjWorkshop

Parameters:

event - sender of this update.

Returns:

true if update was correctly handled by superclass.

showWay

public void showWay()

Deprecated. Use computeWay() instead.

Initiates re-calculation of geodesic and shows the result in the given display.

computeWay

public void computeWay()

Initiates re-calculation of geodesic. You need to call update(this) to make things visible.

setGeometry

public void setGeometry(PgElementSet elemset)

Geodesics are computed on the given surface. Sets starting element and endelement to default values that fit the geometry. Triangulates the geometry if necessary. Removes degenerated faces if necessary. Creates face normals if necessary.
Call computeWay() to compute default geodesic.

Parameters:

elemset - Is triangulated if necessary. cancel() returnes element set to non-triangulated state in this case.

removeGeometry

public void removeGeometry()

Description copied from class: PjWorkshop

Remove the assigned geometry and its backup clone. Subclasses frequently overwrite this method but are adviced to call this method.

Overrides:

removeGeometry in class PjWorkshop

getActualLength

public double getActualLength()

The current actual length of the computed geodesic.

Returns:

-1 if no geodesic is visible

setDisplay

public void setDisplay(PvDisplayIf disp)

Sets the display where the resulting geodesic shall be shown. Pick events are caught from this display also.

Specified by:

setDisplay in interface PjWorkshopIf

Overrides:

setDisplay in class PjWorkshop

Parameters:

disp - may be null - then the geodesic is not shown anywhere (default)

getDisplay

public PvDisplayIf getDisplay()

Display where geodesics are shown and where pick events are caught from.

Specified by:

getDisplay in interface PjWorkshopIf

Overrides:

getDisplay in class PjWorkshop

Returns:

display that was set with setDisplay(PvDisplayIf)

close

public void close()

Has to be called to remove workshop from element set as update listener and to remove polygon from display.

Overrides:

close in class PjWorkshop

cancel

public void cancel()

Cancels and closes the workshop (removing the computed geodesic from display).

Overrides:

cancel in class PjWorkshop

ok

public void ok()

Description copied from class: PjWorkshop

Accept current version of the geometry as new version. Close workshop. The copy of the original geometry is ignored.

Implementation in this class calls close().

Overrides:

ok in class PjWorkshop

getPolygon

public PgPolygon getPolygon()

The computed geodesic as an independent n-dimensional polygon. Is always the same instance of PgPolygon.

Returns:

computed geodesic as polygon.

getPolygonOnElementSet

public PgPolygonOnElementSet getPolygonOnElementSet()

The computed geodesic as a polygon that depends on the geometry. Is always a new one for each computation.

selectGeometry

public void selectGeometry(PgGeometryIf geom)

Currently not supported by display.

Specified by:

selectGeometry in interface PvPickListenerIf

pickDisplay

public void pickDisplay(PvPickEvent pos)

Get a location in the display with 2d display and 3d world coordinates. Point may be independent of any geometry.

Specified by:

pickDisplay in interface PvPickListenerIf

Parameters:

pos - Pick event issued by the display

See Also:

PvPickListenerIf

dragDisplay

public void dragDisplay(PvPickEvent pos)

Drag a location in the display with 2d display and 3d world coordinates. Point may be independent of any geometry.

Specified by:

dragDisplay in interface PvPickListenerIf

Parameters:

pos - Pick event issued by the display

See Also:

PvPickListenerIf

pickInitial

public void pickInitial(PvPickEvent pos)

Pick an arbitrary point on a geometry, point may lie inside an element.

Specified by:

pickInitial in interface PvPickListenerIf

Parameters:

pos - Pick event issued by the display

See Also:

PvPickListenerIf

dragInitial

public void dragInitial(PvPickEvent pos)

Drag an arbitrary point along a geometry, point may lie inside an element.

Specified by:

dragInitial in interface PvPickListenerIf

Parameters:

pos - Pick event issued by the display

See Also:

PvPickListenerIf

pickVertex

public void pickVertex(PgGeometryIf geom,
                       int index,
                       PdVector vertex)

Get a picked vertex of a geometry.

Specified by:

pickVertex in interface PvPickListenerIf

Parameters:

geom - Picked geometry on which vertex lies

index - Index of vertex in vertex array of geometry

vertex - 3d coordinates of vertex position

See Also:

PvPickListenerIf

dragVertex

public void dragVertex(PgGeometryIf geom,
                       int index,
                       PdVector vertex)

Drag a picked vertex of a geometry.

Specified by:

dragVertex in interface PvPickListenerIf

Parameters:

geom - Picked geometry on which vertex lies

index - Index of vertex in vertex array of geometry

vertex - 3d coordinates of vertex position

markVertices

public void markVertices(PvPickEvent pos)

Mark a set of vertices of a geometry within a given bounding box.

Specified by:

markVertices in interface PvPickListenerIf

Parameters:

pos - Contains mark box that is selected.

unmarkVertices

public void unmarkVertices(PvPickEvent pos)

Unmark a set of vertices of a geometry within a given bounding box.

Specified by:

unmarkVertices in interface PvPickListenerIf

Parameters:

pos - Contains mark box that is selected.

setPickFirst

public void setPickFirst()

User shall pick starting point. Call of update(this) is needed afterwards.

setPickLast

public void setPickLast()

User shall pick endpoint. Call of update(this) is needed afterwards.

setMethod

public void setMethod(int mode)

Set whether shortest or straightest geodesics are computed. Use the constants of this workshop. You need to call computeWay() and update(this) for changes to take effect.

See Also:

SHORTEST, STRAIGHTEST

getMethod

public int getMethod()

Whether shortest or straightest geodesics are computed.

Returns:

either SHORTEST or STRAIGHTEST.

See Also:

setMethod(int)

setShortestMode

public void setShortestMode(int flag)

If shortest geodesics are computed, you have several different choices which local minimum is computed.

Parameters:

flag -

See Also:

SHORTEST_DIJKSTRA, SHORTEST_EUCL_DIJKSTRA, SHORTEST_ELEMENT_TREE

getShortestMode

public int getShortestMode()

If shortest geodesics are computed, you have several different choices which local minimum is computed.

See Also:

SHORTEST_DIJKSTRA, SHORTEST_EUCL_DIJKSTRA, SHORTEST_ELEMENT_TREE

setAngle

public void setAngle(double angle)

getAngle

public double getAngle()

setStartBary

public void setStartBary(PdBary bary)

Set the starting point of the geodesic.

Parameters:

bary - 3dim barycentric coordinates of starting point in start element

See Also:

setStartElement(int)

setStartElement

public void setStartElement(int elemindex)

Set the element where the geodesic shall start in.

See Also:

setStartBary(PdBary)

setEndBary

public void setEndBary(PdBary bary)

Set the endpoint of the geodesic.

Parameters:

bary - 3dim barycentric coordinates of endpoint in endelement

See Also:

setEndElement(int)

setEndElement

public void setEndElement(int elemindex)

Set the element where the geodesic shall end in.

See Also:

setEndBary(PdBary)

isConnected

public static boolean isConnected(PiVector[] neighb,
                                  PiVector elementrun)

Checks whether the given element indices belong to an edge connected element run. Added for debugging purposes.

Parameters:

neighb - neighbourhood information of geometry

elementrun - list of element indices

Returns:

true if the given list of elements is connected wrt the neighbourhood information

See Also:

PgElementSet.getNeighbours()

getConnectingStrip

public static int[] getConnectingStrip(PgElementSet geom,
                                       int startelem,
                                       int endelem)

Gets a strip from startelem to endelem by marking the elements (beginning with startelem) and their neighbours with the 'distance' to the starting element (measured in 'number of elements') until the endelement is reached. Then the algorithm constructs a way by going backwards from endelement to elements with decreasing distance.

getShortestInStrip

public static PgPolygon[] getShortestInStrip(PgElementSet geom,
                                             PdBary start,
                                             PdBary end,
                                             int[] strip,
                                             PiVector outSide,
                                             PiVector outvertind,
                                             PdBaryDir initialDir)

Deprecated. since 06.05.04, use getShortestInUnfoldedTriangleRun(...) instead.

Computes the shortest polygon between two points that lies in elements that is given as parameter. It lays the elements into a plane and uses another method to get the points of the curve.

Parameters:

start - barycentric coordinates of starting point in element strip[0]

end - barycentric coordinates of endpoint in element strip[strip.length-1]

strip - array that contains the global element indices of the elements that shall be traversed on the way from start to end. Must contain the elements in the order in which they shall be traversed.

outSide - output: contains numbers {0,1}. outSide.getEntry(i)==0 if i-th vertex (excluding starting and endpoint) of shortest polygon lies on left border. ==1 if i-th vertex (exclusive starting and endpoint) of shortest polygon lies on right border.

outvertind - output: global vertex index in element set of the geometry vertex that the polygon hits with its vertex

initialDir - output: initial barycentric direction of shortest polygon in element strip[0]

Returns:

list of 2-dim polygons:
[0]= left border of element strip or null if only one element in strip
[1]= right border of element strip or null if only one element in strip
[2]= shortest polygon. if only one element in strip then only the length is correct, the rest arbitrary.
returns null if an error occured

getShortest

public static PgPolygonOnElementSet getShortest(PgElementSet geom,
                                                PdBary start,
                                                int startelem,
                                                PdBary end,
                                                int endelem)

Computes a shortest geodesic that connects given points on a triangulation. That doesn't have to be THE shortest connection between the points. It is the locally shortest that is generated by contracting the curve in a given triangle run. The one that connects start and endpoint crossing the least number of triangles is used (shortest face dijkstra connection).
NOTE: The element indices are always of the following form: first element is the starting element, then given a polygon vertex the next vertex has an element assigned that is a neighbour to the element of the current vertex, except the next vertex lies on a vertex.

Parameters:

geom - The element set. Must have valid neighourhood information and must be triangulated.

start - Barycentric coordinates of starting point in starting element

startelem - The starting element. Global index in geometry. Note that the first element of the computed geodesic may be different from this parameter if startpoint lies on a vertex.

end - Barycentric coordinates of endpoint in endelement

endelem - The endelement. Global index in geometry. Note that the last element of the computed geodesic may be different from this parameter if endpoint lies on a vertex.

Returns:

A shortest connection between starting and endpoint as a polygon on element set, or null if an error occured.

See Also:

PgPolygonOnElementSet

getShortest

public static PgPolygonOnElementSet getShortest(PgElementSet geom,
                                                PdBary start,
                                                int startelem,
                                                PdBary end,
                                                int endelem,
                                                PiVector trianglerun,
                                                PgPolygonOnElementSet outpoly)

Computes a shortest geodesic that connects given points on a triangulation. That doesn't have to be THE shortest connection between the points. It is the locally shortest that is generated by contracting the curve in a given triangle run. If no triangle run is given, then the one that connects start and endpoint crossing the least number of triangles is used (shortest face dijkstra connection).
NOTE: The element indices are always of the following form: first element is the starting element, then given a polygon vertex the next vertex has an element assigned that is a neighbour to the element of the current vertex, except the next vertex lies on a vertex.

Parameters:

geom - The element set. Must have valid neighourhood information and must be triangulated. Must NOT have degenerate edges.

start - Barycentric coordinates of starting point in starting element

startelem - The starting element. Global index in geometry. Note that the first element of the computed geodesic may be different from this parameter if startpoint lies on a vertex.

end - Barycentric coordinates of endpoint in endelement

endelem - The endelement. Global index in geometry. Note that the last element of the computed geodesic may be different from this parameter if endpoint lies on a vertex.

trianglerun - A list of connected triangles from startelem to endelem, that will be used as the first guess. May be null. As output: The triangle run which contains the computed geodesic is returned here.

outpoly - Result is put here if not null. New polygon is allocated if null. Is returned as function value.

Returns:

A (locally) shortest connection between starting and endpoint as a polygon on element set, or null if an error occured.

See Also:

PgPolygonOnElementSet

getShortest

public static PgPolygonOnElementSet getShortest(PgElementSet geom,
                                                PdBary start,
                                                int startelem,
                                                PdBary end,
                                                int endelem,
                                                PiVector trianglerun,
                                                PgPolygonOnElementSet outpoly,
                                                PgElementSet unfolded,
                                                PiVector vertexlist,
                                                PiVector left,
                                                PiVector right,
                                                PdVector previous,
                                                PdVector next,
                                                PdVector t2d,
                                                PdBary tempbary)

Computes a shortest geodesic that connects given points on a triangulation. That doesn't have to be THE shortest connection between the points. It is the locally shortest that is generated by contracting the curve in a given triangle run. If no triangle run is given, then the one that connects start and endpoint crossing the least number of triangles is used (shortest face dijkstra connection).
NOTE: The element indices are always of the following form: first element is the starting element, then given a polygon vertex the next vertex has an element assigned that is a neighbour to the element of the current vertex, except the next vertex lies on a vertex.

Parameters:

geom - The element set. Must have valid neighourhood information and must be triangulated. Must NOT have degenerate edges.

start - Barycentric coordinates of starting point in starting element

startelem - The starting element. Global index in geometry. Note that the first element of the computed geodesic may be different from this parameter if startpoint lies on a vertex.

end - Barycentric coordinates of endpoint in endelement

endelem - The endelement. Global index in geometry. Note that the last element of the computed geodesic may be different from this parameter if endpoint lies on a vertex.

trianglerun - A list of connected triangles from startelem to endelem, that will be used as the first guess. May be null. As output: The triangle run which contains the computed geodesic is returned here.

outpoly - Result is put here if not null. New polygon is allocated if null. Is returned as function value.

unfolded - temporary 2d geometry for unfolded triangle runs; may be null.

vertexlist - variable size temporary container, references to left and right boundary in unfolded geometry; may be null.

left - variable size temporary container for left unfolded boundary; may be null.

right - variable size temporary container for right unfolded boundary; may be null.

previous - temporary 2d vector; may be null.

next - temporary 2d vector; may be null.

t2d - temporary 2d vector; may be null.

tempbary - temporary barycentric coordinates in a triangle; may be null.

Returns:

A (locally) shortest connection between starting and endpoint as a polygon on element set, or null if an error occured.

See Also:

PgPolygonOnElementSet

unfoldTriangleRun

public static PiVector unfoldTriangleRun(PgElementSet geom,
                                         PiVector run,
                                         PgElementSet unfolded,
                                         PiVector left,
                                         PiVector right)

Triangle number i in given run is triangle i in unfolded geometry. The same local indices are used for the vertices of the triangle. (geom.getElement(run.getEntry(i)).getEntry(k) is unfolded to unfolded.getElement(i).getEntry(k).)
The generated geometry has no neighbourhood information or normals.

Parameters:

geom - a triangulation with dimOfVertices >= 3; may not contain degenerate edges

run - must have length >= 1 and must be a connected list of triangles in geom

unfolded - output is a 2d geometry

left - left and right contain vertex indices in unfolded geometry where left[i],right[i] is the i-th diagonal. I.e. both can contain intervals i,i+k with identical indices that represent the same point on the bounds of unfolded. They include both initial and endvertex.

right - see left

Returns:

the modified triangle run or null if error occured

getShortestInUnfoldedTriangleRun

public static PiVector getShortestInUnfoldedTriangleRun(PgElementSet unfolded,
                                                        PiVector left,
                                                        PiVector right,
                                                        PiVector output)

Takes a triangle run (unfolded to 2d) and computes the shortest connection in this closed polygon between the start and end vertex. Returned is a sequence of indices to the lists of the left and right boundary. Use unfoldTriangleRun(...) to get the data needed by this method from a higher dimensional surface.
Run must contain at least 2 triangles.
Algorithm is the one from Lee, Preparata; Euclidean Shortest Paths in the Presence of Rectilinear Barriers; Networks vol 14 (1984).

Parameters:

unfolded - 2d triangle run

left - Sequence of vertex indices in 'unfolded' that describe the left hand boundary of the run. It implicitely contains information about the behaviour of the diagonals (inner edges): A boundary vertex with N diagonals emanating from it is repeated N times in sequence. The sequence contains the first and last vertex of the triangle run exactly once.

right - same as 'left' for the right hand boundary

output - contains indices for left/right arrays of the vertices that are hit. negative index refers to right array, positive to left array

Returns:

same instance as parameter 'output' or a new instance if 'output' is null.

getDijkstraDistance

public static PiVector getDijkstraDistance(PgElementSet geom,
                                           PiVector front)

Computes the combinatorial edge distance of all vertices to a given center vertex respectively on a given set of vertices using Dijkstra's algorithm.

Parameters:

geom - The element set. Neighourhood information is not needed.

front - Indices of vertices on the initial front.

Returns:

Distance of each vertex to the given center vertex.

removeLoops

public static int removeLoops(int[] source,
                              int len,
                              int[] temp)

Removes subintervals with same starting and ending value (processing from left to right), for instance 10,9,5,7,2,10,2 becomes 10,2

Parameters:

source - inout (source with loops removed is put here)

len - number of entries in source to be considered

temp - should be of length >= max_{i}(source[i]) (no check performed)

Returns:

length of relevant output entries in parameter 'source'

getEuclideanDijkstraDistance

public static PdVector getEuclideanDijkstraDistance(PgElementSet geom,
                                                    PiVector front)

Computes the combinatorial edge distance of all vertices to a given center vertex respectively on a given set of vertices using Dijkstra's algorithm.

Returns:

PdVector dist of each vertex to the initial vertex.