12

As the polygon is convex, it is simple! Two vertices are consecutive if all other vertices are located on the same side of the line that goes through these two points. This means that the cross product of the vector feom one of the pionts to the other one with the vector from the first point to any other one in the polygon have the same sign (all negative or ...


5

Given that the polygon is convex, its centroid $C$ is in its interior. Test the gradients of the lines $CV$ for each vertex $V$. This gives a linear time test.


4

An alternative to OmG's answer (which is great) would be to sort your points into an ordered array where you can find any points neighbors by looking at the points on either side. This method would be very good if you need to work with the same polygon for many calculations as most work is done upfront but afterwards the cost of determining if two points are ...


2

I would use a winding number algorithm. There are a few, but the fastest goes like this:Imagine a line from your point along the positive x-axis. Now, for every edge of your polygon, determine if it crosses this line. if it crosses the line from below to above, then increment the winding number (which is initially zero), if it crosses going from above to ...


1

The quad tree suggestion by D.W. is interesting. I want to expand on it here. The principle of it is to break the area into big (and then progressively smaller) squares and check whether these squares are fully in or fully out of any polygon. Let's call these cases "black" and "white" respectively. If a big square is either black or white you do not have to ...


1

An alternative approach is to use a quad-tree. One approach is to store each polygon in the deepest node that corresponds to a region that wholly contains the polygon. Given a test point, you traverse the quad-tree, and when you visit a node, you do a point-in-polygon test for each polygon associated with that node. This then lets you do a smaller number ...


1

Without any assumptions on the input mesh, you cannot in general get a single b-spline surface that replicates an arbitrary polygon mesh. You would need the mesh to be connected, but you would also need some fairly significant assumptions about the mesh topology. At the very least, you would want the input mesh to be manifold. (It might be possible to ...


1

Here is one approach to identify all rotational symmetries of the graph: Pick any three vertices, $v_1,\dots,v_3$. Loop over all possible combinations of three vertices $w_1,\dots,w_3$. For each such combination, find the unique rotation that maps $v_1 \mapsto w_1,\dots,v_3 \mapsto w_3$, then check whether this is a rotational symmetry of the entire ...


Only top voted, non community-wiki answers of a minimum length are eligible