JM Lopez - 2012-05-29 01:33:44

First of all, many thanks to Brenor for this amazing library. It has saved me a lot of work.

After pulling my hair for quite a while, I have found a shortcoming/bug in the boolean OR method ("A|B") in some corner cases. I'm reporting it here in hopes that it can help somebody else, and that somebody more knowledgeable than me with the algebra involved can fix it for everyone's benefit.

In a nutshell, if you calculate the union of two shapes which form a 'doughnut' (that is, one of the shapes closes the other, leaving an unconnected 'island' inside), the returned polygon is completely wrong. For instance, in the following code I create an L-shaped polygon, copy and rotate it 180 degrees (so that I have a ¬-shaped polygon), then combine the two:

<?php

require ('polygon.php');

$P1 = new polygon();

$P1 -> addv(0,0);

$P1 -> addv(1,0);

$P1 -> addv(1,0.25);

$P1 -> addv(0.25,0.25);

$P1 -> addv(0.25,1);

$P1 -> addv(0,1);

$P2 = $P1 -> copy_poly();

$P2 -> rotate(0.5,0.5,M_PI);

$P3 = $P2 -> boolean($P1,"A|B");

$P3->print_poly();

?>

The expected result would be something like a picture frame: a square with a hole in the center. The returned result, however, is quite weird (for clarity, I have edited out the slight deviations from 0/1 due to the perturbations):

Polygon:

(0.75)(0.75) Unchecked

(0.75)(0.25) Unchecked

Next Polygon:

Polygon:

(0) (1) Unchecked

(1) (1) Unchecked

(1) (0) Unchecked

(0.75)(0) Unchecked

(0.75)(0.25) Unchecked

(1) (0.25) Unchecked

(1) (0) Unchecked

(0) (0) Unchecked

(0) (0.75) Unchecked

There are two polygons; the first is just a line (2 vertexes) which doesn't have much to do with the expected result (it would be one of the sides of the internal boundary of the polygon); the second polygon is indeed the outer limits of the combined polygons (the outer square), but it has a "twist" in one of the corners (the (1,0) corner) in which it becomes self-intersecting.

The best result would be returning the outer limit as the first polygon, then the inner limit as a linked polygon with reverse winding. Or, at least, correctly calculate the outer limit.

I hope this report is useful, I'll be happy if I can contribute something back with it. Thanks again for an amazing work!