2012年1月31日火曜日

What Is Polygon Vertacy

what is polygon vertacy

Night #4: Sorting the Vertices of a Polygon

The following problem came up in my ICM course this year. A student was working on a sketch that involved tiling polygons arbitrarily drawn by a user. Allowing a user to set the vertices of a polygon should be easy enough, right? But what if the user does not happen to draw them in a nice clock-wise (or counter clock-wise) order?

Imagine for a moment, you have an ArrayList of PVectors called "vertices." When the user clicks, the mouse you could add that mouse location to that ArrayList.

void mousePressed() {   vertices.add(new PVector(mouseX,mouseY)); }

You could then draw that list as a polygon using beginShape() and endShape().


void draw() {   beginShape();   for (PVector v : vertices) {     vertex(v.x, v.y);   }    endShape(CLOSE); }

But depending on how the user set the vertices, you might end up with:

when what you really want is the following:

One solution for solving this problem is to always sort all of the vertices according to their relative angle from the center. Let's say you calculate the center of the polygon as the average location of all vertices.


  PVector centroid = new PVector();   for (PVector v : vertices) {     centroid.add(v);   }    centroid.div(vertices.size());

You can then make a vector that points from the center to each vertex and get its direction (using PVector's heading2D() method).


  for (PVector v : vertices) {     PVector dir = PVector.sub(v, centroid);     float a = dir.heading2D() + PI;   }

Note how we add PI to the angle. The heading2D() function will return an angle between -PI and PI and it'll be easier to sort if we just have an angle between 0 and TWO_PI. One way to sort an ArrayList is called a Selection Sort. In the example below, you'll find a variation of the selection sort. The code iterates through the ArrayList, finds the element with the highest angle, removes that element and sticks it at the end of a new ArrayList. It does this again and again until the original ArrayList is empty. The result is a new ArrayList in sorted order.


Following is that example which implements all of the above into a class. If you are looking for an exercise, try allowing the user to move or delete existing vertices. Also, how you would make a system of these polygons so that the user can draw more than one?

Source: PolygonVertexSorting.zip



These are our most popular posts: what is polygon vertacy

Copying a polygon attribute to vertices

This question came up last weekend (on si-community and xsibase): how do I copy a polygon attribute to a point attribute? As Chris TC and gray pointed out, a point can be associated with multiple polygons. So you use ... read more

18 glasses 3d 3ds

glass1: 400 polygons, 386 vertices glass2: 304 polygons, 290 vertices glass3: 304 polygons, 290 vertices glass4: 320 polygons, 306 vertices ... glass7: 336 polygons, 322 vertices ... glass10: 368 polygons, 354 vertices ... read more

Networked Politics » Blog Archive » Where to purchase buckballs on ...

The framework on this is like a football basketball composed of 20 hexagons along with twelve pentagons with a carbon dioxide atom in the vertices of every polygon and also a sure together each and every polygon side. read more

How to automate deleting polygon vertices that are closer than 2cm ...

I have a large polygon feature class that has many vertices which are *almost* co-located i.e. less than 2cm apart and I would like to delete one of them. I am able to find them using a Python Script but havent ventured into ... read more

Related Posts



0 コメント:

コメントを投稿