Transcript Robust Set Operations on Arrangement

Robust Topologically Invariant
Set Operations on
2D Semi-Algebraic Sets
By: Steven Trac
Advisor: Dr. Victor Milenkovic
09-06-05
Objectives:


Define sets in the plane (arrangement)
Apply rigid transformations (e.g. rotations)



Overlay of multiple sets




Milenkovic and Sacks’ Algorithm
Our topologically invariant algorithm
Milenkovic and Sacks’ Algorithm
Our topologically invariant algorithm
Perform set operations (union, intersection,
symmetric difference, etc.)
Test results
Background Terminology


Curve segment, semi-algebraic curve
Arrangement



Let L be a set of n semi-algebraic curves
L induces a subdivision of the plane, consisting of
cells made from vertices and edges
Regularized semi-algebraic set


Select some of the cells from the arrangement
Take the closure of the disjoint union of the
interiors of these cells
Prior Work

Exact Methods



Perturbation Methods



Rational numbers manipulated with rational
arithmetic
Exponential in expression depth
Perturb all ill-conditioned coordinates
Much larger error
Numerical Methods

Milenkovic and Sack’s approach
Motivation and Goals


Topology changing arrangements
The topology, once defined, should not change
when transformed by a translation or rotation


Incidence relationship should remain invariant
This thesis builds on the work by Milenkovic and
Sacks



Arrangement construction is based off their work
Our transformation algorithm is topologically invariant
Our overlay algorithm is topologically invariant
Robust Topological Invariance

Euler operations





+EVE, splitting an edge at a new vertex
-EVE, joining two edges at a common vertex
VFV, combining two vertices, not connected by an
edge
VEV, contracting an edge to a single vertex
Euler formula: F – E + V = 2



F for faces, E for edges, V for vertices
Planar topology
More complicated if faces not simply connected
Acceptable Euler Operation:
Add/Remove a Vertex


+EVE, splitting an edge at a new vertex
-EVE, joining two edges at a common vertex
Floating Point Rounding
Example 1
Example 2
Example 3
Unavoidable Euler Operations
VFV Euler Operation
EVE → VFV → VFV
VEV Euler Operation
Use of Euler Operations for Robustness
Equal x vertices
Vertical segment
Inconsistent incoming place holder
Arrangement Algorithm

Input of an arrangement



Set L of x-monotonic curve
segments defined by two
endpoints: tail(f) and head(f),
where function f defines the
curve.
Generic orientation
segment above
circular
order
outgoing
Output of an arrangement



Segments split at intersections
Order sub-segments vertically
Minimal information


Incoming / outgoing order for
circular order
Sub-segment above and below
incoming
segment below
Generating Loops
Pairing Loops
Segment above
cell 3
cell 2
cell 1
Segment below
Transforming a Region
0
1



0



Orient segments so
interior has winding = 1
Transform segments
Split at new turning
points as needed
Calculate arrangement
Calculate cells
Calculate winding
numbers of cells
Transforming a Region
0

PROBLEM

1


0
Milenkovic and Sacks
solution




Winding = -1 or
Winding = 2
-1 = 0
2=1
NOT topologically invariant
Sub-segments that do not
bound a selected cell from a
not-selected cell are
discarded.
Transformation: Invalid Winding Cell
Winding = -1
0
0
-1
1
Transformation: Invalid Winding Cell
Winding = 2
1
0
21
1
Overlaying Two Regions

(0,0)
(1,0)


(1,1)

Orient segments of each
region
Calculate arrangement and
cells
Assign pair of winding
numbers
Set Operations

(0,1)




Intersection: (1,1)
Union: (1,0), (0,1), (1,1)
Set symmetric diff: (1,0), (0,1)
Discard not-boundary
segments accordingly by the
set operation
Re-orient segments, recalculate arrangement and
cells
Overlaying Two Regions


(0,0)
(1,0)
PROBLEM


(1,1)
Milenkovic and Sacks
solution

(0,1)



Winding = -1 or
Winding = 2
-1 = 0
2=1
NOT topologically invariant
Sub-segments that do not
bound a selected cell from a
not-selected cell are
discarded.
Invariantly Transforming a Region
?
?
?
Invariantly Transforming a Region
Invariantly Transforming a Region


Remove place holder
segments
Restore minimal
information
8
3
7
2
6
9
4
1
5
Invariantly Transforming a Region


Remove place holder
segments
Restore minimal
information
8
3
7
2
6
9
1
5
Incoming Place Holders


We look at segment above and
below
Four possible place holding
segments


Find out left-most corner of
bounded box



top left, top right, bottom left,
bottom right
If top left/right corner, connect
to segment above
If bottom left/right corner,
connect to segment below
Connect to smallest x end
point after rotation
Incoming Place Holders continued…



Other vertex larger x,
place directly next to
cluster segment
Other vertex smaller x,
place direction next to
last place holder
Maintain planarity
Inconsistent Cases in the Topologically
Invariant Algorithm
Invalid turning points
Inconsistent Case in the Topologically
Invariant Algorithm
Inconsistent incoming place holder
Invariantly Overlaying Two Regions


Maintain vertical order
in each region
No self intersections in
each region
Invariantly Overlaying Two Regions

Use of two heights



Original arrangement height
New overlay height
Insertion of segment

Establish range of
segments



Only segments from other
region
Insert only between this
range
No intersections allowed
between segments from
same region
Hypothesis

Faster?


Accurate?


Yes or no?
More or less?
Our Hypothesis


Faster
Less accurate
Test Input
Test Input
a1
a0
Test Input
a3
Testing Error
Error 1
Error 2
Error 5
Testing Information






Segs – Number of
segments
EP – Number of vertices
Cell – Number of cells
ARR – Running time of
the arrangement
algorithm
ROOT – Running time of
the root calls.
TRNS – Running time of
transform calls.






Error 1 – Max y-distance
Error 2 – Max y-distance
with the segment above
Error 3 – Max y-distance
with the segment below
Error 4 – Max intersection
y-distance
Error 5 – Max closest
distance error
Error 6 – Max closest
distance intersection error
Testing Results
Milenkovic and Sacks
Topology Invariant
Testing Results
Milenkovic and Sacks
Topology Invariant
Testing Results
Milenkovic and Sacks
Topology Invariant
Conclusions


Validated algorithm on random, structured,
and degenerate inputs
Besides unavoidable changes, the topology
were robustly invariant



Unavoidable changes were rare in testing
On rotation, our algorithm computed the
arrangements faster
Our topologically invariant algorithms did not
introduce a significant increase in error

Similar accuracy to Milenkovic and Sacks
The End!
THANK YOU!