Re: [Plplot-devel] Example 25 illustrates a plfill bug

[Alan W. I. <ir...@be...>]

Hi Arjen:

I think it is time to take our off-list conversation about a replacement for
the code in plP_plfclp back to the list.

For the others here, Arjen fixed all the fill issues shown by example 25,
but neither Arjen nor I were positive that the code in plP_plfclp would work
for an arbitrary polygon (even for the "simple" case where the polygon is
guaranteed not to self-intersect).  Even if that code can be proved to be
correct by some code guru, it is a huge bunch of code which makes the code
difficult to understand for mere mortals.  Furthermore, I was not satisfied
with the plgradient software fallback defined area approach so I wanted to
try a different approach there by specifying the fill of the intersection of
two arbitrary polygons which is a generalization of the fill of the
intersection of a polygon + rectangle that is solved by plP_plfclp.

For both the general case and the special case where one of the polygons is
a rectangle, I felt the most reliable algorithm would be a recursive one
where the boundary of polygon 1 is traversed looking for the first two
intersections that have not been found before, and splitting polygon 2 into
two parts with the boundary between the two parts specified by the two
intersections and the polygon 1 boundary (if any) between those, and dealing
recursively with the intersection of polygon 1 with those two parts.

I have implemented a partial version of this algorithm as of revision 10720.
The only way to test this new algorithm (rather than using the traditional
plP_plfclp code) is to specify -DUSE_FILL_INTERSECTION_POLYGON=ON.

The valgrind applications gives the new code a clean bill of health (no
memory management issues, no memory leaks) for example 25.  Also, the code
is quite straightforward so mere mortals can understand it.

However, there are some limitations to the current implementation which
generate a lot of PLplot warnings and bad looking example 25 plots.

* Intersections between polygon boundaries that occur at vertices are not
   handled correctly yet.  I still have to implement code to decide if a
   vertex intersection corresponds to an actual crossing of the two polygon
   boundaries or just a "touch" between them with no crossing.

* Once the algorithm reduces polygon 2 to pieces that do not cross the
polygon 1 boundary, then the tests have to be refined to deal properly
with the case where polgyon 1 is inscribed inside the polygon 2 piece
or vice versa.

* The code to deal with self-intersecting polygons has not been implemented
yet.  However, example 25 does not test that case yet so you probably won't
notice this deficiency.

I am confident thes three issues should be straightforward to deal with, but
until at least the first two of them are solved do not expect much from the 
-DUSE_FILL_INTERSECTION_POLYGON=ON experience.

What I am working on at the moment is another issue where I found
pointinpolygon was giving an incorrect result.  (The documentation of that
routine specifically states it returns false if the test point is on the
boundary, but I have a test case generated by the new code where the test
point was actually a vertex of the polygon, and pointinpolygon incorrectly
returned true.)

More later.

Alan
__________________________
Alan W. Irwin

Astronomical research affiliation with Department of Physics and Astronomy,
University of Victoria (astrowww.phys.uvic.ca).

Programming affiliations with the FreeEOS equation-of-state implementation
for stellar interiors (freeeos.sf.net); PLplot scientific plotting software
package (plplot.org); the libLASi project (unifont.org/lasi); the Loads of
Linux Links project (loll.sf.net); and the Linux Brochure Project
(lbproject.sf.net).
__________________________

Linux-powered Science
__________________________