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

Most spatial indexes should be good, especially if your rectangles are axis aligned. Spatial indexes typically have about $O(log{M})$ insertion time so you could build in index in $O(M * log{M})$. Lookup time is similar, so finding the best/correct rectangle for every point should be around $O(N * log{M})$. For rectangles, the simplest index is probably a ...


2

Your problem can be solved in linear time. This paper describes a method to solve a system of $n$ linear inequalities with at most two variables per inequality and $m$ distinct variables in total in $O(n m^3 \log m)$ time. (I am swapping the meaning of $n$ and $m$ with respect to the paper in order to keep the name $n$ consistent with your question). In ...


1

Start from the leftmost point $x_0$ (the one with minimum $x$-coordinate). If there are ties break them in favor of the point with minimum $y$ coordinate. Suppose for simplicity that there are no two points that are collinear with $x_0$ (this case can be handled by suitably breaking ties). Shoot a ray vertically at an angle of $-\frac{\pi}{2}$ radians. ...


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 ...


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