Are polyshape vertices preserved reliably without floating point errors?

Suppose I have two polyshapes p1 and p2 and I want to do operations on them (intersection, unions) that in theory should preserve some of the vertices of p1 and p2. My question is, can I always count on this to occur without floating point error from the underlying software algorithm?

In the following example, it seems to be true. The union of p1 and p2 is a quadrilateral whos vertices ought to be the union of the vertices of p1 and p2 separately,

load Data
figure; plot([p1,p2]);axis equal

and this is indeed shown to be the case without the need to apply a floating point error tolerance,

Union=union(p1,p2);

all(ismember(p1.Vertices,Union.Vertices,'rows'))

ans = logical
   1

all(ismember(p2.Vertices,Union.Vertices,'rows'))

ans = logical
   1

The same thing appears to be true with intersections:

figure; plot([p2,p3]);axis equal

Intersection=intersect(p2,p3);

nnz(ismember(p3.Vertices,Intersection.Vertices,'rows'))

ans = logical
   1

But there's no reason this had to be the case, right? There must be something about the underlying union() and intersect() algorithms that ensure this.

Answer 1

[Paul]

Hi Matt,

The doc pages for intersect, union, subtract, and xor all show a second output (ShapeID) that indicates if a vertex in polyout comes from poly1, poly2, or is created from the boolean operation itself.

In my opinion it would very peculiar if the ShapeID indicates a vertex in polyout came from poly1 (poly2) and it wasn't exactly the same as the corresponding vertex in poly1 (poly2).

I'd hope that any tolerances are applied to determine whether or not keep a particular vertex, but once a determination is made to keep it, the vertex data themselves should not be changed.

[Matt J]

Thanks to both of you (@Paul and @John D'Errico). The shapeID output does indeed seem to be an authoritative sign that vertices are preserved when possible, as well as confirming that numerical failures can occur, like the example below which considers the scenario suggested by John.

p1=polyshape(rand(3,2)); 

  d= p1.Vertices(1,:)-p1.Vertices(2,:) ; %translate along edge
p2=translate(p1,d/2);

[~,shapeID]=intersect(p1,p2) %With inf precision, 2 vertices should be preserved

shapeID = 3x1

2 0 0

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

plot([p1,p2])

Answer 2

[John D'Errico]

Um, probably, yes. But potentially no.

Yes, because on most operations, you will just be indexing into the original set of vertices. And that MUST preserve the exact numbers.

Potentially no because consider an intersection, where one of the vertices from one of the shapes just happens to fall along an edge of the other. Now there will be floating point operations applied, where the least significant bits could be wrong. Can I say this would never happen? No. But I'd not trust it, at least not without some significant testing. Anyway, that is where I would be looking. Anything else seems unlikely to cause a problem.