# Tag Info

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

6

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 comparing shapes." Efficient Algorithms. Springer Berlin Heidelberg, 2009. 235-248. (Springer link.)           Image from Helmut Alt ...

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

3

The problem you describe is known as the red-blue intersection problem. Here, we have a red set of $n_1$ segments and a blue set of $n_2$ segments and we know that there are only intersections between segments of different colour. Although this special case has been extensively studied, the $O(n\log n + k)$ algorithm, with $n=n_1+n_2$ is still optimal1 when ...

3

Yes, there are more algorithms to do so in $\mathcal O(n)$. The first is dated back to ElGindy and Avis in 1981, Lee 1983 and Joe & Simpson in 1985. The visibility algorithms use stack (the first one three stacks, further only one) and process vertices in order they appear at boundary. The visibility algorithms described in book Art Gallery Theorems and ...

3

Call the center point $(c_x, c_y)$. The function $d(p_x,p_y) = \sqrt{(p_x-c_x)^2+(p_y-c_y)^2}$ computes the distance from the point $(p_x,p_y)$ to the center of the circle. For each edge of the polygon create its line equation from its two endpoints. If the two endpoints are $(a,b)$ and $(c,d)$ then this line is $y = (\frac{d-b}{c-a})\cdot(x-a) + b$. Solve ...

3

You have a 2D convex polygon $G$, and a 3D polyhedron $H$. Let $P_G$ denote the plane that the polygon is contained in. The following should work: Their intersection is a 2D polygon. You can find the edges of the intersection as follows: For each triangle of $H$: If the triangle intersects $G$, output this intersection. This procedure outputs the ...

3

After conducting more research I did find a solution, but first I will examine solutions suggested by posters and considered by myself and review why they didn't work. This problem reduces to finding all chordless cycles in a planar graph. This was one of my first thoughts early on, but this doesn't work when you consider the following: 5-------f----...

2

Run Flood Fill from any point and the farthest points in the both directions are your result. If you find that the distance in one of the directions is zero it means that it was one of them. Exploiting the very same idea, if you try finding pixels with the least number of surrounding pixels and apply limited BFS Flood Fill to find out where it can go - at ...

2

One reasonable approach is to use RANSAC to find a homography that causes many points to be aligned (or approximately aligned). You'd apply this procedure to align the set of vertices of the first polygon with the set of vertices of the second polygon. The homography captures translation, rotation, and scaling, so it allows correcting for all of them. ...

2

In the paper you reference, Theorem 5 is a claim about simple polygons, where Theorem 6 deals with convex polygons, which are a special kind of simple polygons. The 'As we have seen before, ...' refers to this line: 'As we have seen before, each such test can be done in $O(k)$ time.$^8$', where $8$ references another paper. However, even though I do not ...

2

Graham scan for a convex hull works if you have an ordering of points $a_1,a_2,...a_N$ such that you have a sequence $p_1 < p_2 <...< p_k$ where your convex hull is $a_{p_1}, a_{p_2},...,a_{p_k}$ of which it is not possible to have a winding number greater than $1$. In general for any polygon $P$ this might not work, but for a star shaped polygon, ...

2

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$ (and $c \neq 0$) be the objective function you are interested to minimize (say). Then since $x_0 \in int(P)$, there exists a ball $B$ centered at $x_0$ with ...

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

2

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 also drawn a triangulation of this polygon. The dual of this triangulation is a cycle with $6$ vertices, and this is not a tree. However, is this thing I've ...

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

2

Form a list of the $4n$ edges making up the $n$ rectangles. Delete every edge that appears twice. The edges that remain describe the outside of the polygon. If you want to list these edges in clockwise or anticlockwise order, that's easy enough to do -- just pick an arbitrary starting vertex and find one of the two edges it is incident on, then find the ...

1

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 This can be solved with a straightforward application of a sweepline algorithm. Sweep a vertical line from left to right, with increasing $x$-values. At any ...

1

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 convex polygon). To find the intersection, you can use a binary search and find that is there any intersection or not.

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

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

1

First, assume we already have a list $L$ with all segments in $P$ that are at least partially visible from $p$, ordered by the smallest angle $\theta$ such that a segment is visible from $p$ at angle $\theta$. (This can be done with a (angular) sweep line algorithm in $O(n\log n)$) Now, observe that if a line from $p$ to some point on the segment $s_i$ in $... 1 Build a graph, with one vertex per black pixel, and an edge between two pixels if they are adjacent. Compute all-pairs shortest-path distances$d(x,y)$. For each vertex$x$, compute $$f(x) = \max \{d(x,y) : y \in V\}.$$ Find the vertex (pixel)$x$with the maximum score for$f(x)$. This will be one endpoint of the shape. Find the other vertex$y$that ... 1 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 find the endpoints by using depth-first search, or (for a more robust solution) by computing the tangent line at each point$p$and checking for a neighbor ... 1 Your problem is a special case of planar point location. The algorithm/data structure you found by Snarak and Tarjan can answer point location (and thus point in polygon) queries in$O(\log n)$time using$O(n \log n)$preprocessing and$O(n)\$ space. That is optimal. There are two other data structures that achieve this: a data structure by Kirkpatrick and a ...

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