# Tag Info

### How can I determine if two vertices on a polygon are consecutive?

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

### Partial polygon matching

There is quite a bit of work on this important problem. Some of the most insightful work is by Helmut Alt and collaborators. He wrote a survey in 2009: Helmut Alt. "The computational geometry of ...

### How can I determine if two vertices on a polygon are consecutive?

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

Accepted

### Simplex Algorithm: Why must the optimal value of the LP lie on the face or vertex of a polyhedron?

Suppose $P = \lbrace x: Ax \leq b \rbrace$ is the polyhedra, where $x \in \mathbb{R}^n$. Further assume $P$ is full dimensional, then let $x_0$ be some interior point in P. Let $c \in \mathbb{R}^n$ (...
Accepted

### Selecting a polygon within an array of complex polygons

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

### Is Dual Graph of a Triangulation of a Polygon Tree?

Below is an example of a polygon with a single hole. The red area is the interior of the polygon, and the white triangle in the center is the hole (which lies outside the polygon). In the figure, I've ...
Accepted

### assign points to non-overlapping rectangles

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})$. ...
Accepted

### Finding the Point with Maximum Distance from the Boundary of a Closed Polygon in 2D Euclidean Space

The medial axis is the set of points in the interior of the shape that has two closest points on the boundary. Intuitively, the largest "incircle" in a polygon must touch the boundary at at ...
1 vote
Accepted

### Is there a computationally optimal point-in-polygon solution (for a dynamic scenario)?

I can list three candidate approaches. I'm not sure how to choose among them -- you might need to experiment among them to see which will work best in your situation. Approach #1: sweepline algorithm ...
1 vote

### Find an edge that is completely visible from point outside a polygon (Convex Hull)

It is not too hard. connect the point to the end-point of an edge. If none of these two segments has an intersection with convex-hull, it means you can see that edge completely (as you consider a ...
1 vote

### Joining points of polygon in correct order

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

### Efficient rasterisation of vector image with polygons

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

### Efficient rasterisation of vector image with polygons

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

### Convert a polygon mesh into a b-spline surface

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 ...
1 vote
Accepted

### Detecting rotational symmetries of spatial structures

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

1 vote

### Is there an efficient algorithm to extract the farthest ends of a thin contour?

Compute the topological skeleton of the black pixels. This will form a curved line one pixel wide (i.e., it will be isomorphic to a line). Use the two endpoints of this line as your answer. You can ...

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