About Vatti's polygon clipping algorithm.

  • Permalink
  • submit to reddit
  • Email
  • Follow


Hi,

I need a polygon clip (boolean operate is better) algorithm, it must
support self-intersections, and support both even-odd and nonzero
rule. I think Vatti Clipping algorithm can do this (with some
modification and extend) , but I can't get the original paper.

Is there anyone can give me a paper of Vatti Clipping? Or, can suggest
me another algorithm.

0
Reply Xeranic (26) 6/26/2007 1:53:24 AM

See related articles to this posting

comp.graphics.algorithms 6639 articles. 1 followers. Post

0 Replies
90 Views

Similar Articles

[PageSpeed] 52


Reply:

Similar Artilces:

About Vatti's polygon clipping algorithm.
Hi, I need a polygon clip (boolean operate is better) algorithm, it must support self-intersections, and support both even-odd and nonzero rule. I think Vatti Clipping algorithm can do this (with some modification and extend) , but I can't get the original paper. Is there anyone can give me a paper of Vatti Clipping? Or, can suggest me another algorithm. ...

polygon clip algorithm/code
HI, I am looking for algorithms or source code for efficiently doing polygon clip in GIS software. It is a very basic function of GIS related to query or selection or overlay. I appreciate your advice and comments. binjiang wrote: > HI, I am looking for algorithms or source code for efficiently doing > polygon clip in GIS software. It is a very basic function of GIS > related to query or selection or overlay. I appreciate your advice and > comments. Sutherland-Hodgman Laing-Barsky Weiler algorithm read Computer Graphics, Principles and Practice, 2nd Edition, by Jame...

code for hodgman polygon clipping algorithm
Hi, does anyone have a good implementation of the hodgman's polygon clipping algorithm. The algorithm finds the area of intersection of a polygon in space and a cube. Ajmal ...

Fortran Code or Algorithm for Polygon Clipping ?
Dear list members, is there some code in Fortran available for the clipping of convex polygons ? Or do you know a description for an algorithm to cope with this task ? Thanks for your help in advance ! Klemens Hi, I implemented the two algorithms that come in the book of Cormen. I think it works fine. You can find the description in "Algorithms" of Cormen. If you need the code, write me to send it to you. Just a comment, comments are in Spanish :) . FJRA email: a19980403 @ pucp . edu . pe Klemens Barfus <klemens.barfus@forst.tu-dresden.de> wrote: > is there some cod...

3D polygon-polygon clipping in camera space
Hi - I'm writing a 3d scene exporter that's supposed to export polygons (preferably triangles) in a 3d scene to flat screen-space 2d polygons, while clipping the those 3d polygons that overlay each other from the point of view of the camera. Does anyone know of any utility that does this? If no tool exists, I'd appreciate suggestions as to how such a "clipper" may be implemented. (My initial thoughts go along the lines of projecting infinite volumes from the point of eye point of the camera to each vertex of each 3d polygon, in order to get a sense of which polygons part...

Polygon algorithms when polygons can contain arcs...
Hi! We are looking for some code for calculating with polygons. Like, distance between polygons, intersections, whether a point is within a polygon and all that stuff. Now the weird thing is that our polygons can consist of arcs too. Does anyone know of a library or a book or web ressource describing how to deal with those polygons? The library can be commercial. Lots of Greetings! Volker Volker Hetzer <volker.hetzer@ieee.org> wrote: > Now the weird thing is that our polygons can consist of arcs too. Then please do everybody a favour and stop calling them polygons. Mixing up d...

Need Cohen Sutherland Clipping Algorithm for 3D Clipping
hi ng, i need to find a working implementation of the cohen sutherland clipping algorithm. My own implementations don't work and neither google nor the search function of my newsgroup reader gives me good stuff. anyone of you knows a good implementation or example? (maybe in java in c++) or does anyone know a similar algorithm with implementation? thanks in advance! michael On Sat, 03 Jul 2004 16:57:04 +0200, Michael Heinold <michael_spamfrei_heinold@gmx.de> wrote: >i need to find a working implementation of the cohen sutherland >clipping algorithm. My own implementations ...

Polygon algorithms
I'm doing some simple maps using SAS/Graph (don't have SAS/GIS). I need to do some calculations such as calculating polygon areas and testing for bow-ties. Anyone have some sample code that they could share? The algorithm for polygon area doesn't look that hard to code. http://mathworld.wolfram.com/PolygonArea.html However this won't work if the polygon is self-intersecting (a bow- tie) so I need to check for that first. ...

polygon clipping
hey, can anyone give me polygon clipping algo or its implementation in c/c++ for 2d graphics?plz daxa wrote: > hey, can anyone give me polygon clipping algo or its implementation in > c/c++ for 2d graphics?plz Sorry, wrong newsgroup. -Herbert ...

Polygon clipping
Hello, I'm looking for visual basic demo source code for Cohen-Sutherland polygon clipping algorithm (or other algorithms). I know vb is not the correct language for these applications but I have to work with it :-( Thanks in advance Paul ...

Polygon Algorithm???
I am looking for an algorithm given polygon A and polygon B would return the following (1) the intersection points of A and B and (2) the polygon(s) of A created by removing the intersection polygon of A and B. I have found much info on the intersection points, but I am having problems with part 2. "E Berg" <bergman@NO.SPAM.comcast.net> wrote in message news:fP6dncWjHdNSkbrfRVn-tw@comcast.com... >I am looking for an algorithm given polygon A and polygon B would return >the > following (1) the intersection points of A and B and (2) the polygon(s) of > A > ...

polygon algorithms
Hi, some of you may already know GPC: http://www.cs.man.ac.uk/aig/staff/alan/software/ It is told to be the fatest implementation around, for handling polygon-data: having to polygons, i'd like to be abled to compute the - intersection - the XOR area - the difference - the union - ... The GPC-package is all about multi-polygons afaik. That means it describes arbitrary shaped areas by their outer polygon(s) and additional polygons which describe holes within the other polygons. I notices a strong similarity to the Java AWT API which provides the class Area, which also stores arbitrary s...

clipping algorithm
I looking for an efficient algorithm for clipping a line against a polygon in 2D. Source code in C/C++ Greg ...

Clipping Algorithms
Hodgman-Sutherland works on convex clipping regions, requiring additional code to decompose concave paths into multiple convex paths. Can operate upon a concave path. Weiler-Atherton works on concave clipping regions and concave paths. Vatti algorithm makes amazing claims, but I haven't dug up any useful details, yet. So far, I've just borrowed Cassleman's hodgman-sutherland code. It's not clear to me how to coordinate the two winding-rules with any of the above. Postscript, of course, offers all its relevant operators in pairs: fill/eofill, clip/eoclip....

Polygonal Approximation Algorithm
Hye, i'm from malaysia and now i'm doing for my project in image processing area. Actually i'm new in this area. I'm having a problem to start my research. So here are my problem: How to choose the suitable algorithm in using polygonal approximation to recognize closed curve for example blood shape? And, i just want to know where can i get database of blood shape? Sorry for my poor english. Hope u guys can help me tq ...

Algorithm of merging polygons
There are several polygons in an X-Y coordinate system. Each polygon is described by listing the coordinates of all the vertices sequentially. It's unpredictable whether there's overlap between each polygon. I wish to merge them, which means that if there's overlap or abutting between two polygons, then change them into one polygon which covers exactly same area and location as before. Is there any algorithm to implement this operation? Thanks. The term for this is "polygon clipping". E.g.: GPC at http://www.cs.man.ac.uk/~toby/alan/software// or CGAL at http://www.cgal...

polygon clipping lib
I do not know if this is the correct NG. I am looking for fast and accurate library for polygon clipping that is GPL or LGPL. Thanks in advance, "TekCat" <tek_catNOBS@hotmail.com> wrote in message news:epvqnh$ltk$1@aioe.org... >I do not know if this is the correct NG. I am looking for fast and >accurate library for polygon clipping that is GPL or LGPL. Thanks in >advance, Sounds like you really would like http://www.cs.man.ac.uk/~toby/alan/software/ Note: "The GPC library is free for *non-commercial* use", nothing on GPL (perhaps in the source ...

Convex polygon algorithm
Hi, I'm looking for an *exact* polygon filling algorithm which can handle convex, concave, and even self-intersecting polygons. By "exact," I mean that it needs to perform truly correct anti-aliasing. In other words, if the polygon covers exactly 30% of a given pixel, that pixel's color should be 30% (of the user-specified color parameter, or whatever). As a worst-case example, suppose I had a really complex, concave, self- intersecting polygon with hundreds of sides, and the entire polygon fit within a single pixel. I still want that pixel colored correctly, which ...

Ear clipping algorithm
Hi All, Do you know where I can find a C source of the "Ear clipping algorithm"? Need to implement it and didn't want to start from scratch. Thanks a lot, Alberto "devDept" <info@devdept.com> wrote in message news:1178522405.923661.189580@e51g2000hsg.googlegroups.com... > Do you know where I can find a C source of the "Ear clipping > algorithm"? Need to implement it and didn't want to start from > scratch. C++ code and a PDF describing this algorithm are at my web site. In the "Browse Libraries..." section, select the "...

Polygon algorithm needed
I have plane polygons with many sides. They are self-crossing to an arbitrary degree. For each vertex I need to know its "depth," that is, the smallest number of edges that must be crossed by a path, not necessarily straight, to get to the outside. A ray from the vertex far to the right will cross either an odd or even number of edges, but this tells me only whether the depth is odd or even, that is, its low order bit. Vertices with even depth can be on the outside (depth 0). I need the other bits too. I will appreciate any algorithms, references, or ideas about this. Thank you i...

Polygon algorithm needed
I have plane polygons with many sides. They are self-crossing to an arbitrary degree. For each vertex I need to know its "depth," that is, the smallest number of edges that must be crossed by a path, not necessarily straight, to get to the outside. A ray from the vertex far to the right will cross either an odd or even number of edges, but this tells me only whether the depth is odd or even, that is, its low order bit. Vertices with even depth can be on the outside (depth 0). I need the other bits too. I will appreciate any algorithms, references, or ideas about this. Thank...

Point in Polygon-Algorithm
Hi folks, I'm looking for an algorithm determining if a point is within a given polygon or not. I found some for plane geometry, but I need one in shperical geometry - i.e. working with GPS points. Any links or pointers appreciated! tia Roland What are the longest distances between your points? "Roland Spielhofer" <rspiel@gmx.net> wrote in message news:4lit6kF24gfsU1@individual.net... > Hi folks, > I'm looking for an algorithm determining if a point is within a given > polygon or not. I found some for plane geometry, but I need one in &...

Polygon Clipping Algo in IDL
Dear All, Does any one has written code for the polygon clipping ( Cohen Sutherland or Liang Baskey ) in IDL? or is there any direct function available in IDL? Regards Chintan This is a multi-part message in MIME format. --------------020505060102070902090104 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit raval.chintan@gmail.com wrote: > Dear All, > > Does any one has written code for the polygon clipping ( Cohen > Sutherland or Liang Baskey ) in IDL? or is there any direct function > available in IDL? > > Regards > Ch...

2D line clipping against polygon
I'm looking for algorithm for 2D line clipping against concave polygon with holes. Which algorithm is suitable? The most reliable i've found (to avoid missed intersections, special points, colinear segments) is: 1) Find all intersection points of line/ polygon (+ segments) and split the line in N lines 2) Check if the mid-point of the line is inside/outside the polygon /holes. To do 2, check each point on each polygon/hole. If the point is inside a even number of polygons, it's inside an hole so the line segment is invalid, else is inside the polygon. graphics@graffiti.co.il...

Weiler Atherton Clipping Algorithm
Hello, I need the Weiler-Atherton-Clipping algorithm within IDL. Can somebody submit any kind of ready-to-use code? I would really appreciate it. A good demonstration of the algorithm is shown here: http://research.cs.vt.edu/algoviz/Clip/clipping_applet.html Thank you and best regards Chris On Tue, 9 Sep 2008 01:46:21 -0700 (PDT), rogass@googlemail.com wrote: >Hello, >I need the Weiler-Atherton-Clipping algorithm within IDL. Can somebody >submit any kind of ready-to-use code? I would really appreciate it. A >good demonstration of the algorithm is shown here: >http://research...