Theodore Papadopoulo wrote:

Barend Gehrels wrote:

...

Herewith the URL to the preview of Geodan's Geometry Library, including documentation and some examples.

There are still implementation issues and algorithmic details to be figured out or to be implemented. This is a preview and not yet a real submission. However I think that the community will get a feeling how it works and/or should work.

The URL with documentation is here: http://geometrylibrary.geodan.nl/geometry.html and sources can be downloaded from that webpage.

I just had a glance on the library. One thing that strikes me is its 2D perspective, which is not reflected in the names. I would at least call the namespace geometry2d or the classes point2d .... It really seems awkward to use the generic names for the specific 2D case. That being said, from my point of view any geometry basic layer (ie basic representation not the sophisticated algorithms) should be as dimension agnostic as possible... but I may be biased.

Thanks. For the namespace, it is no problem to change it and I agree, geometry2d would have been better. We might change it to "geospatial" or maybe "geospatial2d". For the dimensions, we could have added a Z or a N-templatized array of coordinate values, but because we don't do anything with them nor didn't planned to, they are not there.

Regards,

Theo.

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

-- ------------------------------------- Barend Gehrels, Geodan Holding b.v., Amsterdam, The Netherlands, www.geodan.nl

Hervé Brönnimann wrote:

Dear Bernd: I started with a few quick notes (I really didn't do much more than glance at the documentation), which grew into a somewhat more extensive review - sorry, I've been thinking about geometric software library for a while now :)

I have many concerns/questions/suggestions with your library:

[...]

* naming: within_point_in_polygon is not a good name. I understand the desire to have all of them start with "within_" but is_point_within_polygon would read like English, at least. As Theo mentioned, having 2D somewhere in the name would also avoid deflated expectations from users.

My background in using geometry is 3D graphics. So I found some naming is a little strange too me, like "evelope", "within", "linestring"... IMO, "within_*" would be better is changes to "contain": template<typename POI, typename POL> bool contain(const POL& poly, const POI& pnt) I am still wondering if "evelope" is "Bounding Box" or "Hull", if "linestring" is "Poly Line" or "Line Strip".

* more algorithms and more implementations: you can find working code for many intersection / detection / distance computation in many books. Perhaps the most relevant for your purposes is the excellent "Geometric Tools for Computer Graphics" by Philip Schneider & David Eberly (http://www.amazon.com/dp/1558605940? tag=softsurfergeomet&link_code=as3&creativeASIN=1558605940&creative=3734 89&camp=211189)

Yeah, this book is very good. Also, David Eberly has a library implemented almost all the geometry primitives and algorithm introduced in the book, it is worth to have a look: http://www.geometrictools.com/

Dear Hervé, Thanks for your extensive review on my preview... Maybe I should have stated more clearly that I'm a geographer and built this library from a GIS perspective. We (at least in my company) normally do not distinguish between polygon types, for example. Therefore, as in my other mail, we might change the namespace to "geospatial" or to "geospatial2d" to make this more clear. For the rest I put my comments between yours. Hervé Brönnimann wrote:

Dear Bernd: I started with a few quick notes (I really didn't do much more than glance at the documentation), which grew into a somewhat more extensive review - sorry, I've been thinking about geometric software library for a while now :)

I have many concerns/questions/suggestions with your library:

* If you treat a polygon as a sequence of points, you should really provide generic algorithms with iterators, with two algorithms for differentiating between closed and open polygonal lines. There is no distinction and/or specialization of algorithm for (general) polygons, and special classes: monotone, convex, orthogonal, or orthogonally convex polygons, for which better algorithm often exist (simpler geometric primitive computation, better algorithmic efficiency, elimination of special cases, etc.)

I agree that some algorithms are better for, for example, convex polygons. However, we didn't make a distinction indeed. It is normally not done in GIS systems. The states of the US, for example, are polygons of which some might be convex. However, if you edit a convex polygon by adding one point it might result in a non convex one. We could add a flag "is_convex", however (until now) we didn't do that and see the polygon as one or more series of linear rings. Polygons are or should always be closed, it is a "surface", having an area. An "open polygonal line" is a linestring in our case. Or maybe I do not understand you completely.

* generally, for checking, testing, and for further processing, I found it a good idea to return a witness/certificate with your answers. For instance, for the point in polygon test, if you use ray- shooting (upward), you could also return some information that identifies the edge immediately above the point (if inside). For intersection detection (returning a bool if intersection), returning a point inside both polygons. For distance computation, returning the two closest points between the closest features. Most times, you already have this information without any overhead, making it optional allows the user to toss it away if they don't need it. If there is an overhead in providing the witness, I would always provide two algorithms.

Interesting, actually we did this thing in the intersection of segments and you are right, the information is often there. However, I think you should also provide generic alternatives, calling those witnessed functions, but without that information because to be honest, I have never needed the edge above the point in a point-in-polygon case.

* definition of polygon: is a polygon a boundary or a topological disk? eg. do two nested polygons intersect? Is there an intersection algorithm for polygonal *regions* or for polygonal *boundaries* only? Seems that every algorithm on polygon would have two versions.

I think that it is not clear enough in the documentation then: a polygon is a polygonal closed region, a surface, an open polygonal boundary is a linestring. The intersection of two polygons deliver a multi_polygon. The intersection of two linestrings (being closed or open) delivers a multi_point or actually a (not defined) multi_geometry (points and maybe line segments in collinear cases)

* naming: within_point_in_polygon is not a good name. I understand the desire to have all of them start with "within_" but is_point_within_polygon would read like English, at least. As Theo mentioned, having 2D somewhere in the name would also avoid deflated expectations from users.

Good idea. We designed it like this: all algorithms start with the OGC name, so "within" in this case and "intersection" in another case. But your name is probably more clear indeed. However, the name "point_in_polygon" is also very common, and "within" is justed prefixed there. I also thought about putting all those algorithms in the namespace "within" but we have to find another name for the function "within" then.

* is point necessarily defined by two coordinates? (eg. how about intersection points - do they require computation or can I store two lines?) Is a box necessarily axis-aligned? Is a circle always defined by center and radius? (e.g., how about a circle defined by three points? do I have to invoke sqrt() thrice to compute center and radius or can I keep three points as definition?)

The circle is there because of circle-selections (selecting points, lines or polygons falling completly within circles), we do not other things with it, sorry. Maybe we should have omitted in our library but because we had it and need it ourselves we kept it there. There are indeed no circles defined by three points or other circle algorithms in this library.

In general, you make broad assumptions as to your objects representations, which may not be very useful for users in different but very common settings (e.g. in meshing a 2D polygonal region, doing map overlays, motion planning in 2D).

* genericity: I find it very limiting that you're tying your concepts of points to 2d Cartesian coordinates. This confuses the concept of geometry with that of representation. I'm of course biased but I think CGAL got it right by defining kernels and predicates, and implementing algorithms solely based on kernels. Your approach on the other hand does not clearly say what the *concept* of point is, compared to your implementation. Defining concept by an archetype is not a good way to do it.

Good point, the "concept" documentation and implementation must be better. We didn't plan to rebuilt CGAL because it is already there. This is another library and more directed to GIS systems and therefore, as said above, we will probably rename the namespace to "geospatial::". It is more clear then.

The addition of traits as a baggage grouping all fundamental types is a good idea, as does CGAL, but I think "traits" should be renamed "geometry", be the central concept, and define both types (points, lines, segments, etc.) and primitives (intersection of lines, constructing a line joining two points, etc.) and take it from there. Grading geometries with several concepts (one with points only, one with lines, one with convexity - implying segments, polygons, etc.) would help to define minimal requirements for each algorithm. OK In short, templatizing your existing geometry falls short (at least for me) in making it "generic".

* concerning the scope, 2d is somewhat easy especially with epsilon geometry. This sounds like a naive approach. In addition, this only speaks about a single geometry traits class, i.e., yours. But since it is not quite clear what one has to provide to have one's one alternate geometric traits class, I don't know without looking at the implementation how much work it would be Please talk to Fernando who has offered to discuss with you the details of exact predicate. Or read my former student Sylvain Pion's PhD thesis (now manager in the CGAL project). Or read Fortune and vanVyk's and/or Shewchuk's excellent landmark articles for 2D and 3D exact predicates using integral or floating point computation.

* more algorithms and more implementations: you can find working code for many intersection / detection / distance computation in many books. Perhaps the most relevant for your purposes is the excellent "Geometric Tools for Computer Graphics" by Philip Schneider & David Eberly (http://www.amazon.com/dp/1558605940? tag=softsurfergeomet&link_code=as3&creativeASIN=1558605940&creative=3734 89&camp=211189)

Thanks for the suggestions

In all truth and honesty, I for one would not vote in favor of your library for Boost, and I suspect that many potential users would find it unnecessarily restrictive. For the algorithms and primitives you supply, I do not see enough care in the design of your library besides the specific setting/implementation you intend it for. This is what makes a boost geometry library a difficult proposition, imho, since there are many users of geometry out there, and all seem to require different performance -vs- exactness tradeoffs, genericity, coordinate models, algorithms, or all of the above.

I didn't expect vote intentions at this time but, however, I'm glad with it. Making the preview took more time than planned and if many people would vote negatively I would rather not submit (but let's first wait for other reactions.). I agree with you, I always look at the geometry from a GIS perspective but there are ways more to do it, and needs for other geometries or 3D or whatsoever. However, we will not implement those things as we don't need them and have not enough spare time / experience.

Not that I've had success with it either (I had some hopes my student in his GSoC project would come up with generic representations of 2D subdivisions, but he was sick for the second half of the project, had to graduate, the usual excuses, not to mention my own excuses... well, he dropped the project midway). At this point, I'm not sure I believe that there can be a geometry library in Boost, perhaps several libraries for their own respective domains (CGAL, graphics/ OpenGL, GDAL, GTL, OpenMesh, etc.) is the highest level of factoring.

Maybe indeed more geometry libraries would be convenient because I think it is better to have two than none of them. I really miss things as point-in-polygon or area in boost, things which are very common and scattered over the internet but not yet in boost. Thanks again for your comments. Barend

-- Hervé Brönnimann hervebronnimann@mac.com

On Jan 29, 2008, at 4:34 PM, Barend Gehrels wrote:

...

Hi,

Herewith the URL to the preview of Geodan's Geometry Library, including documentation and some examples.

There are still implementation issues and algorithmic details to be figured out or to be implemented. This is a preview and not yet a real submission. However I think that the community will get a feeling how it works and/or should work.

The URL with documentation is here: http://geometrylibrary.geodan.nl/geometry.html and sources can be downloaded from that webpage.

Best regards, Barend Gehrels

------------------------------------- Barend Gehrels, Geodan Holding b.v., Amsterdam, The Netherlands, www.geodan.nl

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

-- ------------------------------------- Barend Gehrels, Geodan Holding b.v., Amsterdam, The Netherlands, www.geodan.nl

Hi Michael, Michael Fawcett wrote:

On Jan 30, 2008 5:23 AM, Barend Gehrels <barend@geodan.nl> wrote:

...

Maybe I should have stated more clearly that I'm a geographer and built this library from a GIS perspective. We (at least in my company) normally do not distinguish between polygon types, for example.

:) That's my current field as well, although I have a background in game development. I have often thought a Boost.GIS library would be an excellent addition.

I agree! However a "boost.GIS" library is much larger than a "boost.gis.geometry" library, it should probably contain projections, classification and symbolization, rendering, etc. We have such a library but that is not a boost-styled library and it is rather old, therefore we started restyling the geometry core and adapted the std:: / boost:: style.

...

Therefore, as in my other mail, we might change the namespace to "geospatial" or to "geospatial2d" to make this more clear.

I have a question (bare in mind I have not read your docs, so apologies in advance if this would have been obvious) - Do all of your algorithms expect Cartesian coordinates, and if so, do you provide conversion functions to transform from a particular geographic projection system to Cartesian?

They expect Cartesian coordinates indeed, and projection libraries are currently not included in the library.

What in your library makes it *more* "GIS" than "geometric"?

We started to call it "geometric" because it is only the geometry part (of our larger library) which is more or less ready for boost or OSS. However, there are many more ways to look at geometry than the way we look, from the GIS perspective. We have focus on linestrings and polygons, other geometry users look at triangles, trapeziums and circles. For example. Therefore, we now think that it is better to show the perspective and call it "geospatial::"

If a GIS library were to be proposed to Boost, I would like to see the point class carry with it the projection system it was in. This could probably be done with Boost.Units. That way, trying to compute distance between two points that were in different projection systems simply wouldn't compile.

We didn't do that although we considered adding the SRID. But I will have a relook and look better at boost.units for this case, good idea. Library users can use their own points, containing the SRID, and make algorithm specializations on them. There is an example showing that, because there have been a discussion before about latlong points. Barend

--Michael Fawcett _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

-- ------------------------------------- Barend Gehrels, Geodan Holding b.v., Amsterdam, The Netherlands, www.geodan.nl

Bernd: On Jan 30, 2008, at 5:23 AM, Barend Gehrels wrote:

Dear Hervé,

Thanks for your extensive review on my preview...

Maybe I should have stated more clearly that I'm a geographer and built this library from a GIS perspective. We (at least in my company) normally do not distinguish between polygon types, for example.

Therefore, as in my other mail, we might change the namespace to "geospatial" or to "geospatial2d" to make this more clear.

I agree that names of entities of your library (never heard of a linestring outside GIS, for instance) is slanted towards geospatial. However, many of the algorithms such as intersection, distance, convex hulls, etc. are much more general than that. I wonder if you could isolate the geometry part better without geospatial in mind, and perhaps have your own geospatial layer on top (in or out of boost). After all, it's it's truly generic, you shouldn't have problems / performance loss using it in your context. But I think it's not a good idea to craft a general-purpose geometry with names that belong to a particular domain.

For the rest I put my comments between yours. [snip] Maybe indeed more geometry libraries would be convenient because I think it is better to have two than none of them. I really miss things as point-in-polygon or area in boost, things which are very common and scattered over the internet but not yet in boost.

I agree that there definitely is a place for those oh-so-basic algorithms. But to be truly generic and useful to the maximum number of people, you should think about what there algorithms *require*. For instance, for area, all that is needed is the area of a triangle, and even (if it can be implemented more efficiently) the third point can be the origin (or a reference point). If the user can supply that primitive, there is no need to require coordinates, and indeed your area algorithm will work with latlong points, or in any other system of reference. (I've never thought how to compute the area of a triangle on the sphere, and it can't be too simple, bu surely there is a formula). The point (pun intended) is that you can decouple the algorithm from the geometric computation, and separately provide the computation for Euclidean, latlong, whatnot spaces. It makes the library much more useful. For convex hull, to take another example, all that is required is some notion of extremum (e.g. in x- or y- direction) and the orientation of three points. If you can compare points by some coordinate or somehow order them in an order that's compatible with the hull (i.e., makes any convex polygon monotone for that order), you're in business. I do not need to know how (i.e., with what specific formula) you compute the orientation or order the points. Here we are talking about an oriented space. Its a requirement that you did not have in the area computation (well, in fact you must have had it underneath, otherwise there would be no notion of inside/ outside, but the software requirement is different). This is not quite the direction that CGAL took, in fact it pushes their position a bit further because they have a monolithic kernel (as a concept, or set of requirements) that doesn't separate those requirements due to orientability, or area/metric computations, from e.g., the ability to define circular objects, to having specialized computations like in-circle testing. Otherwise, they already have the separation of representation (x,y in cartesion or lat,long in spherical or x,y,w in homogeneous coordinates) from the geometric predicates. And that I argue is a very desirable thing for a generic (i.e., maximally reusable) library. As for interaction with boost.gil, I am not familiar, and their documentation does not really do a good job at expressing concepts. But surely it's easy to write area_triangle(p,q,r) or area_reference_triangle(p,q) and orientation_triangle(p,q,r) in a way that require gil::Point2DConcept<Point>. Then you can reuse your algorithms. Hope those considerations give you food for thoughts, -- Hervé Brönnimann hervebronnimann@mac.com

-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Barend Gehrels Sent: Thursday, January 31, 2008 11:55 AM To: boost@lists.boost.org Subject: Re: [boost] preview of a template geometry library

Hervé,

Thanks for your reaction. I will consider the separation of core geometry and more GIS-like geometries, and will study on your idea of coordinate-free geometries.

We had the feeling that a library user or implementer can always speciliaze for other points than x-y, so it would work, but indeed if you have to redo all algorithms for latlong it is quite a job.

Another wrinkle for latlon conversion is that there are two different latitudes. This results from the earth being an ellipsoid rather than a sphere (centrifugal force makes the equator bulge out more than the poles). The "geodetic" latitude is the angle from the equator to a line perpendicular to the local earth surface. The "geocentric" latitude is the angle is from the equator to a line that intersects the center of the earth. The geodetic latitude is the one used most often but there are uses for the other one. -ges

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Friday 01 February 2008 07:33 am, Barend Gehrels wrote:

...

What do other people think of this? Is it OK to say that the code is not available at all, unless it is accepted? What are the precedents? Normally, if a library is rejected then people who wanted to use it still have the version submitted for review available to them. A review manager who rejected this library would prevent that sort of use, and that could skew their decision. I'm not going to look at the code until this is resolved (my lawyer wouldn't let me); these comments are based on the documentation.

Of course you can download and look at the sourcecode, no problem. It is stated like this because it is not yet open source, it is not yet submitted or accepted by boost and at no other open source site. Therefore I cannot state there that it is open source at this moment. However, for review purposes it is allowed to look in it. If this is not sufficient I can change the statement.

It sounds like you think you need to get the library accepted into boost before you can license it under the BSL. You don't need permission from anyone but the copyright owner to release your source code under the BSL. The boost license doesn't place any obligations on you to make any special arrangements for distribution of the source code. - -- Frank -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) iD8DBQFHo2nG5vihyNWuA4URApV4AJ0bVT5M+4o1pI72XK/rJ1CI0t3S+wCfbQBX TTTf+UXBwnHoYjowosVUnsA= =g5B3 -----END PGP SIGNATURE-----

Phil, Phil Endecott wrote:

[snip] Have a look at the string algorithms, for example to_upper. There are three variants:

template<typename WritableRangeT> void to_upper(WritableRangeT & Input, const std::locale & Loc = std::locale());

template<typename OutputIteratorT, typename RangeT> OutputIteratorT to_upper_copy(OutputIteratorT Output, const RangeT & Input, const std::locale & Loc = std::locale());

template<typename SequenceT> SequenceT to_upper_copy(const SequenceT & Input, const std::locale & Loc = std::locale());

So I can do it in-place (first), returning a copy (third), or to an output iterator (second). You could also imagine a copy-on-write version, but we would probably want to implement general-purpose copy-on-write containers or smart-pointers before trying that.

The algorithms are currently modelled conform the OGC specifications. This means they have an input and an output. We might add the other alternatives as well. However, many algorithms have already many variants. Consider "distance", there are at least 36 variants of "distance": 6 OGC geometries can be compared to each other. This "matrix" is symmetrical, many are just the other way round, but you might expect that the library contains both "distance(point, linestring) {...}" and "distance(linestring, point) {...}" for template reasons. To offer, for each algorithm, also these three variants, plus the variants taking an iterator, and the variants taking a whole geometry, and sometimes specializations for xy-points or latlong-points or indexed geometries, might seem to much, or an explosion. For some algorithms it certainly makes sense, for example for the line clipping algorithm as you mentioned. As soon as a line is finished it can be outputted. The algorithm "simplify" is recursive and there it will work less obvious. You then could still model it like that, making a temporary copy and call the output iterator. The std::sort algorithm, for example, works in place and doesn't make a copy, maybe because it is recursive. These are just considerations based on a few examples. However, I prefer to have the algorithms as consequent (with respect to input/output) as possible.

When I look at the OutputIterator variant, I like to imagine that it's possible to chain together a pipeline of operations using output iterators and input iterators. People have mentioned "dataflow" sometimes on this list. I have never thought through what's necessary to achieve this.

[snip] It's also interesting to consider how this could work in the context of more intelligent containers, e.g. polygons with bounding-boxes or with spatial indexing. Say I have a polygon that is the coastline of a continent, with millions of points, and I'm zoomed in on a bit of coast. How long does it take to get the clipped polygon to render? Say the container can iterate efficiently over a 2d range:

indexed_polygon continent_coastline = ...; box viewbox = ...; Clipper cl(viewbox); indexed_polygon::range2d r(continent_coastline,viewbox); for(range2d::const_iterator i = r.begin(); i != r.end(); ++i) { // We get each line from continent_coastline that is within, or crosses, the viewbox cl(*i); // Clip to the viewbox, do something with the resulting line-segments. ... }

That's quite straightforward, as long as the clipper does the right thing for all the peculiar cases. But if you have a whole-polygon-at-a-time clip algorithm, it's not clear how you do it:

indexed_polygon continent_coastline = ...; box viewbox = ...; polygon visible_outline = clip(viewbox,continent_coastline); // Could be efficient if the clip algorithm knew that continent_coastline had range2d, maybe? // Similarly, could be efficient for a polygon-with-bounding-box, if the clip algorithm // knew that it had it. This sounds like a case for specialisations with enable_if. // But most likely, clip() will not exploit the indexing in inexed_polygon and treat it // like a std::vector<point>.

[snip]

The polygon clipping, unlike the line clipping, is finished after the last segment has been processed. Intersections in the last segment of the last inner ring might change the output polygon started first. Therefore, it makes less sense. This is not changed when indexing them, but the processing is less of course. After all intersections are done, indeed they might be outputted one by one. (A polygon intersection has certainly advantage using indexes during the intersection process.)

This is all very interesting. But you should stop me from waffling about details, and instead focus on "what is the way forward?".

I appreciate all comments and these discussions are indeed very interesting. So you can go on. You, Hervé, Fernando and others have made me think about many things and alternatives and we will consider all those and try to enhance the design and implementation. The way forward is, I currently think, that we will change many things based on these and other comments and will make a new preview. I already started with the "point" issue raised by Hervé, points are changed and enhanced and I'm happy with it. However, it is unfinished yet. I also would appreciate it as someone experienced in geometry/gis and the boost process could give me a hand. I mean: in the sense that I could ask questions, discuss some things, show him/her code before preview. Best regards, Barend -- ------------------------------------- Barend Gehrels, Geodan Holding b.v., Amsterdam, The Netherlands, www.geodan.nl

Phil, I have thought about the output iterator. The output iterator would indeed be convenient for the Geometry Library. If the intersection algorithm(s) output their intersections with an output iterator, this eliminates the need of having the multi_polygon and multi_linestring as the output. This was one of the reasons to have the multi_polygon / multi_linestring. Other reasons are the OGC model, and that it is a standard GIS concept. These are still valid. However, many users of a Geometry Library might not be very interested in either ogc or gis. So it might be good to omit them as output result and use an output iterator instead. Outputting to a multi_polygon is then possible by using an appending outputiterator. So I will change this in the library. Then I thought, where do we then still need the multi versions of the geometries. There are still places where multi_polygon produce different results as single geometries. One of these places is the "union" algorithm. A union of a multi_polygon with a polygon might result in one polygon. So this is a valid reason for the existance of a multi_polygon. However, I've used, years ago, the union in one or more projects, but at that time I needed a combination of many (multi)polygons, so not one multi_polygon. Spatial aggregations work like that. So building the union algorithm with two iterators on a polygon container as their input, would in fact be more convenient than a union processing two multipolygons. So in the union case we can also do without multi_polygons. The Weiler Atherton algorithm works using two polygons, but will work as well using three or more at the same time (didn't work this out but I think that this must be the case). Another place is the "buffer" algorithm. A buffer of a multi_polygon with two polygons is different (an might be one polygon) from a buffer of two (the same) polygons. However, we could of course also model the buffer algorithm using begin/end iterators, which gives more flexibility. (By the way, it is not yet implemented). If we implement our library without the algorithm versions using multi geometries, the combination of versions per algorithm taking two geometries will by 9 instead of 36, which saves us work. The multi geometries will probably still be there because they are really a separate GIS entity, but the need to have them implemented in all algorithms is then not there. In my previous answer I said that there would be more combinations using the output iterator, now I think that number of the combinations will be less. Thanks.

Yes, polygons with holes are more complicated; I've never had to deal with them. I think it's worth defining separate concepts for solid and holey polygons so that algorithms can specify which they work with.

There are: a "solid polygon" is a "linear ring", a "polygon" can have holes. Many algorithms on polygon use the corresponding algorithms on rings. Barend -- ------------------------------------- Barend Gehrels, Geodan Holding b.v., Amsterdam, The Netherlands, www.geodan.nl