The tag has no usage guidance.

learn more… | top users | synonyms

7
votes
3answers
242 views

Generate equally sized areas in polygon

I am looking for a pseudo code logic that would find n equally sized areas in a given polygon. No space should be between or outside the matched areas. First valid match of areas should be returned. ...
2
votes
0answers
34 views

Polygon simplification that encloses original set of points

I have been trying to implement an optimization for 2D sprite rendering to fight the problem of limited fillrate on mobile devices. The idea is to render textured polygons instead of quads that will ...
-2
votes
0answers
19 views

Faster alternative to incremental Delaunay tesselation

I have a d-dimensional polytope. At first, it is gridded at each dimension. By Delaunay tesselation, the polytope is divided into a number of simplices. I need the information of simplices, as well as ...
1
vote
0answers
39 views

Graph grouping with criteria

I start with a list of adjacent tetrahedra, where there are tight seals to one another along faces for two tetrahedra that are adjacent. The vertices belonging to these faces for both tetrahedra are ...
4
votes
1answer
52 views

How to generalize the planar case of the closest pair problem to d dimensions?

I'm trying to create a solution for the Closest pair problem using d-dimensional points. I've done a thorough search on google but it seems that there is no explanation for the d-dimensional case ...
1
vote
1answer
48 views

How to synchronize segments in polylines?

My input are two polylines -- I had one polyline and I computed offset of it, similarly to polygons. Here is the useful post: ...
1
vote
1answer
537 views

Number of parallel lines in a given set of lines [closed]

I am given N lines, i.e, I am given a,b,c for N lines. And each line is of the form ax + by + c = 0. I need to find out the maximum number of lines that are parallel to each other. For this, first I ...
1
vote
0answers
68 views

distribute rectangles in order to do not overlap

I've a series of labels and icons inside the screen. A label is on the right of corresponding icon. I must perform a sort of declutter: when two or more labels overlap each other (or a label with an ...
2
votes
1answer
59 views

Which algorithm to find the shortest (nodes count) path that encompasses all polygons inside a larger polygon?

Inside a large polygon (say the USA boundaries) I need to find the shortest path that will encompass smaller polygons (say the following cities: Kansas city, St Louis, Memphis, Oklahoma City) By ...
3
votes
3answers
165 views

Find a line that is closest to scattered points

I came across the below interview question on Glassdoor: A scatter graph of points on a page, draw a horizontal line across the page such the the perpendicular y distance to the line from all ...
2
votes
0answers
47 views

Project a piece of image cut by N-vertex shape to a different N-vertex shape

I have an N-vertex shape that I cut out from an image, and I want to project it onto another shape with the same amount of vertices, but different. So, the image will get changed inside the ...
0
votes
1answer
101 views

How can I map a number of points of a polygon to matching points of a larger rectangle?

Suppose I have 2D polygon image and a larger 2D rectangle image and that I have a collection of points for each that I want to align. For Example the polygon has point collection: [PA(a, b), PB(c, ...
4
votes
3answers
253 views

How to determine if set of ordered coordinates form a simple curve?

I hope it is the right place to ask this. I wasn't sure if it belongs to Stack Overflow or Computer Science. Eventually this seemed more suitable. Anyway, some background first: A closed curve, is ...
0
votes
0answers
92 views

Finding all Triangular Hulls in a 2D Point Cloud

My question: Given a set of 2D points, enumerate all triples of points such that no other points is inside the triangle formed by those 3 points. I'm looking for something better than this: // The ...
3
votes
2answers
2k views

Efficient method for finding closest point to a line segment from a set of points including line segment's vertices

Let's say I have a list of points (in my case, point objects in a Python implementation). I then have a line segment connecting two of these points. I want to know if there's a way to efficiently ...
3
votes
3answers
189 views

Method for determining if a line segment is an external edge of a Delauney triangulation?

I've created a Delauney triangulation of a set of points. Now I want to iterate over the triangulation and remove any line segments/edges on the exterior for which the following are true: The ...
1
vote
0answers
214 views

Algorithm for sweeping a 2d shape along a curve?

I am trying to create a graphics application where the user can use an arbitrary shape as a "brush", which will be swept along the drawing path. The shape may be transformed along the path (rotated, ...
12
votes
2answers
1k views

How to calculate figure rotation efficiently?

I have a Figure represented through a matrix of bytes (bitmap-like matrix). Example Figure is shown on the Picture 1. The goal is to find the best rotation angle of some given Figure. When Figure ...
1
vote
1answer
149 views

Algorithm to “de-rasterize” a voxel image of a polyhedron

Rasterizing a polygon in this question consists of creating an array of binary pixels that "represent" the polygon. The reverse of this process is easy to approximate in linear time to the perimeter ...
0
votes
0answers
325 views

Approach for packing 2D shapes while minimizing total enclosing area

Not sure on my tags for this question, but in short .... I need to solve a problem of packing industrial parts into crates while minimizing total containing area. These parts are motors, or pumps, ...
1
vote
2answers
72 views

Adding a minimum rectangle overlap threshold

I have a function that works perfectly for detecting whether or not r1 overlaps with r2: boolean overlaps( Rectangle r1, Rectangle r2 ) { return r1.x < r2.x + r2.width && r1.x + ...
3
votes
2answers
593 views

Find points whose pairwise distances approximate a given distance matrix

Problem. I have a symmetric distance matrix with entries between zero and one, like this one: D = ( 0.0 0.4 0.0 0.5 ) ( 0.4 0.0 0.2 1.0 ) ( 0.0 0.2 0.0 0.7 ) ( 0.5 1.0 0.7 0.0 ) I would ...
2
votes
1answer
162 views

How to find out if a tile is being covered by a polygon?

Given a (intersecting) polygon, I'd like find out which tiles are being covered by the polygon. Example: Details: Tiles are square, 1 unit wide/high The grid begins in (0,0) The corners of the ...
2
votes
5answers
183 views

Selecting a point inside a non-convex polygon

There are a lot of algorithms which will tell you whether or not a given point is found inside a polygon. I'm looking to write an algorithm which, given a non-convex polygon, will return a point ...
6
votes
3answers
257 views

Maximizing number of nested triangles

There is a finite set of points on a plane (about 1500 points in the current task). I need to construct triangles on those points such as each triangle lies completely inside one larger triangle: ...
1
vote
2answers
646 views

2 closest points between 2 rectangles

On a 2D plane, I have 2 rectangles. I want to find the closest pair of points (one on each rectangle), which are closest to each other. By points I mean the corners of the rectangles. And no, they do ...
4
votes
1answer
143 views

How do I find which line connected two squares?

In the Permissive Field of View algorithm, a destination square is visible from a source square if any unobstructed line can be drawn from the source square to the destination square. The algorithm ...
4
votes
2answers
1k views

How to represent a geometric line programmatically?

I have been trying to design a library to do some simple geometric computations in an Euclidean space regardless of its dimension. While it is easy to represent points, vectors, hyperspheres and ...
10
votes
5answers
2k views

How to compare features of two curves?

I need to compare two curves f(x) and g(x). They are in the same x range (say -30 to 30). f(x) may have some sharp peaks or smooth peaks and valleys. g(x) may have the same peaks and valleys. If so I ...
4
votes
3answers
664 views

Intersection of geometric entities

I was trying to design a small C++ geometric API for learning purposes, but came across a problem when dealing with intersections of geometric entities. For example, the intersection of a line and a ...
1
vote
2answers
532 views

Drawing a biggest possible circle inside a polygon - JSXGRAPH

I manage to create a circle inside triangle with this code, but circle inside other polygons are not maximum size: var p1 = board.create("point", [0.0, 2.0]); var p2 = board.create("point", [2.0, ...
2
votes
0answers
243 views

Generate complex (non-convex) polyhedron UV mapping

I need to find an approach to the problem of generating texture maps for non-convex polyhedrons without using a design tool like Maya. Specifically, I am mapping simulation results data onto a 3D ...
1
vote
1answer
328 views

How to compute barycentric coordinates in a systematic and efficient way?

As part of a ray tracer implementation, I need to compute the barycentric coordinates in a triangle in 3D in order to decide if a ray hits the triangle or not. In theory this could be done by simply ...
2
votes
3answers
306 views

Trying to code the points on a circle [closed]

I am trying to understand this: I wrote a code for points on a circle of radius 1. Note that the first and last point intentionally coincide. do i=1,imax X(i,1) = ...
10
votes
2answers
5k views

Find the new coordinates using a starting point, a distance, and an angle

Okay, say I have a point coordinate. var coordinate = { x: 10, y: 20 }; Now I also have a distance and an angle. var distance = 20; var angle = 72; The problem I am trying to solve is, if I want ...
27
votes
9answers
13k views

How to check if 4 points form a square?

Assume I have 4 points (they are 2-dimension), which are different from each other, and I want to know whether they form a square. How to do it? (let the process be as simple as possible.)
0
votes
2answers
609 views

projective geometry: how do I turn a projection of a rectangle in 3D into a 2D view

So the problem is that I have a 3D projection of a rectangle that I want to turn into 2D. That is I have a photo of a sheet of paper laying on a table which I want to transform into a 2D view of that ...
2
votes
2answers
383 views

How to detect two moving shapes overlapped?

Given a list of circles with its coordinates (x and y) that are moving every second in different direction (South-East, South-West, North-East and North-West), and the circle will change direction if ...
-2
votes
1answer
598 views

What do ptLineDist and relativeCCW do? [closed]

I saw these methods in the Line2D Java Docs but did not understand what they do? Javadoc for ptLineDist says: Returns the distance from a point to this line. The distance measured is the ...
3
votes
3answers
2k views

Algorithm to calculate trajectories from vector field

I have a two-dimensional vector field, i.e., for each point (x, y) I have a vector (u, v), whereas u and v are functions of x and y. This vector field canonically defines a set of trajectories, i.e. ...
10
votes
1answer
232 views

How do graphics programmers deal with rendering vertices that don't change the image?

So, the title is a little awkward. I'll give some background, and then ask my question. Background: I work as a web GIS application developer, but in my spare time I've been playing with map ...
1
vote
3answers
647 views

Calculate Ellipse based on 4 points

I need to move an object based on 100 images rotating. The object needs to move in a path that is forming an ellipse when I'm rotating the image based on my gestures. I have 4 points, 2 pairs of ...
3
votes
4answers
1k views

Area calculation of irregular shapes

Is there any algo that can help splitting irregular shape into regular shapes, and eventually calculate the area of the main object by summing the areas of those regular objects?