Effacer les filtres
Effacer les filtres

Are polyshape vertices preserved reliably without floating point errors?

4 vues (au cours des 30 derniers jours)
Matt J
Matt J le 4 Mai 2024
Modifié(e) : Matt J le 5 Mai 2024
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.

Réponse acceptée

Paul
Paul le 5 Mai 2024
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.
  1 commentaire
Matt J
Matt J le 5 Mai 2024
Modifié(e) : Matt J le 5 Mai 2024
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])

Connectez-vous pour commenter.

Plus de réponses (1)

John D'Errico
John D'Errico le 5 Mai 2024
Modifié(e) : John D'Errico le 5 Mai 2024
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.

Catégories

En savoir plus sur Elementary Polygons dans Help Center et File Exchange

Produits


Version

R2023b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by