# Questions tagged [geometry]

The tag has no usage guidance.

63 questions
Filter by
Sorted by
Tagged with
17 views

### Feedback on API design of a HalfEdge Data structure

Background Sometimes also referred to as doubly connected edge list, the HalfEdge data structure allows programmers to efficiently and easily modify topological and geometric properties of a mesh. ...
• 261
239 views

### Why sort the points acc to y coordinates in closest point divide and conquer method?

The divide and conquer strategy for closest point problem sorts the points according to x coordinates so that the median could be found. But what does sorting the strip (strip array contains all the ...
• 109
193 views

### Algorithm to find if a square is removable from a group of squares without disconnection

I have a group of squares on a 2d grid, here's an example I need an algorithm to find out whether we are able to remove a square while keeping the entire group connected. Below is an image where I ...
• 115
2k views

### Algorithm to split a grid of squares into equally sized sections

I have a grid of squares, let's say 12x12. I want to split this grid into equal sections of 8 squares, which is 18 total sections. There is no requirement for sections being convex or compact, and ...
• 115
1 vote
188 views

### Rectangle packing / Bin packing with multiple frames

I have multiple rectangular frames, with different fixed heights. The width should be minimized and there is a maximum width. Then there are many different smaller rectangles. These should be packed ...
1k views

### How can I calculate the radius of an arc given by a series of points

Given a series of points, I need to assert that the plotted points form an arc (with a certain level of confidence), and I need to approximate the radius of the arc. For example, the following points ...
457 views

### What is a good Object-Oriented design for geometry objects when building libraries dealing with geometry operations?

I am trying to design an object-oriented library to handle geometric calculations. However, I am trying to exaggerate on being "tightly" object-oriented and applying relevant "best practices". I know ...
• 2,472
1 vote
901 views

### Algorithm to simplify 2D convex hull at the cost of extra area

Are there any algorithms related to the following problem that could be usefull for solving it? I have a convex hull built on some point set. I would like to simplify it (reduce number of points) by ...
• 356
277 views

### Which class should have the `intersects` method?

I have a Circle class and a LineSegment class, and I want to implement a method that returns two points (or one, or none) for the intersections. How do I know which class to put this method in? Would ...
• 163
76 views

### Should a LineSegment class disallow approximately equal endpoints in its constructor?

Imagine a LineSegment class that represents a line segment using two arbitrary endpoints. Should the constructor throw if it is passed two approximately equal endpoints? Obviously this would require ...
1 vote
318 views

### How do you usually implement right triangles in programming

When I want to implement axis aligned 2d rectangles I always go with {x, y, w, h}, because that is the natural approach to it. With 3d axis aligned rectangles you need {x, y, z, w, h, d(depth)}. For a ...
• 811
820 views

### Find nearest best fit for circle

Below is an example image, if I have a point of the white dot in the middle and I want to find the nearest possible location for the blue circle (which is obviously at the location where I placed it) ...
• 129
1 vote
314 views

### How to detect thin extrusions from a polygon?

I want to create a minimal polygon which approximates the boundary of an arbitrary (semi-random) shape. By "minimal" I mean, "as few points as possible". The original shape (to be bounded) is in ...
• 3,417
1 vote
55 views

### Check if a point is deviating from a path made by a set of line segments

I'd like to know or have other ideas --other than my solution-- about how to check if a car on a given position (lat, lng) is getting away (let's say a distance D away) from the path where the car ...
2k views

### Calculate largest square in rectangle with a given vertex

There are two points (x1, y1) and (x2, y2), each of which can be any real integer pair. These define a rectangle R with vertices {(x1, y1), (x2, y2), (x1, y2), (x2, y1)}. The rectangle exists in a ...
• 101
215 views

### Effecient ways to find the squares enclosed by a path on their edges

If we have a 2d grid (e.g. points at every (x,y) such that x and y are integers) and a closed path on this grid, such that a point on the path (x,y) could only be followed by a point in [(x+1,y), (x-1,...
• 11
268 views

### Building 3D from 2D

If you have an image sheet of facets and data to indicate which point on each facet should connect with other points on the other facets, is it possible to position those facets in 3D space based on ...
• 447
595 views

### Algorithm for lines comparison

I'm working on the import of land-use data into Openstreetmap. Unfortunately I've encountered a problem that has delayed my time table. Take a look at the picture below: the red line is the main road ...
• 147
163 views

### Place circle such that it overlaps the most possible other circles

Given a list of circles (each with parameters (x,y,radius) ) I want to place another circle with a fixed radius such that it overlaps the maximum possible circles from the list of circles. As long ...
• 233
2k views

### Storing a straight line equation

How to store a straight line (infinite length, not a line segment) efficiently? This is not a duplication of How to represent a geometric line programmatically?, because the linked question is about ...
• 708
38 views

### Find whether or not current location is near other locations with given radii

tl;dr: "Am I, with any given location, inside of any number of circles with varying radii" Assume you have a database full of locations (coordinates) with arbitrary radii. Now the user enters and ...
• 103
1 vote
805 views

### tiling algorithm for maximum size of equal-sized tiles

I'm trying to fit an arbitrary number of HD videos on screen so that they all have equal size, maximizing the size of the videos, with no scrollbars appearing. Given N number of tiles of equal aspect ...
• 119
346 views

### Neighbourhood points (2d)

I have a 2d coordinates system with some points on it, like this one: Now I am looking for an algorithm (or just some approach) to find neighboured points. So, if you have the coordinates of one ...
• 171
363 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. ...
• 199
143 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 ...
• 131
1k 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,180
228 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: https://stackoverflow.com/questions/1109536/an-algorithm-for-inflating-...
• 1,526
1k 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
1k 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 ...
• 123
124 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 ...
• 129
2k 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 ...
66 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 projection....
• 293
221 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, d)...
• 101
3k 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 ...
17k 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 ...
• 123
2k 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 outside ...
• 123
1 vote
1k 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, ...
• 203
3k 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 is ...
• 585
1 vote
494 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 ...
• 263
1k 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, ...
• 8,247
1 vote
225 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 + r1....
4k 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 ...
720 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 ...
• 121
2k 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 ...
• 521
390 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: Now ...
• 163
4k 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 ...
• 225
233 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 ...
• 291
4k 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 ...
• 1,766
10k 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 ...
• 111