Suppose you have a set of segments in R^2 (call it S). Every segment is contained in a box of dimension WxH (so, the set S has four additional segments, one for each side of the box) and a segment s to be addedd to S. The segment s starts from point A (that will belong to one of the segment in S) and ends at point B. What i want to compute is the point B' such that B'belongs to one of the segment in S and A-B' does not intersect any other segment in S. Is there a wat to compute B' without using a brute-force algorithm (that is, intersecting AB with every other segment in S)?
Speeding up segment/set of segment intersection
148 Views Asked by Marco Masci At
1
There are 1 best solutions below
Related Questions in COMPUTATIONAL-GEOMETRY
- Come up with a method to find the smallest circle that covers two points with its center in x axis
- Catmull-Rom interpolation on SVG Paths
- Smallest Rectangular Box that surrounds a polyhedron
- Detect hole in geometry
- find area of 3D polygon
- What is most efficient way to find the intersection of a line and a circle in python?
- How to find third point coordinates given variables
- seeking approximate algorithm to find largest clear circle in an area
- Check intersection of Segment_2 from Gmpq kernel with a Circle in CGAL
- How can I create an internal spiral for a polygon?
- Reconstructing a 2D shape from its projection in 1D
- Expanding Convex Hull to Reduce Sides
- How to model particle bouncing off of a curved surface in 3D?
- How can I specify tolerance for floating point operation in CGAL library?
- Number of triangles with N points inside
Related Questions in INTERSECTION
- Math/Physics: Given angle and vector find point of intersection?
- Java 2D game random rectangles
- How can I find a common volume of three cones intersecting each other in MATLAB?
- creating polygons based on intersection
- Ray/Rectangle intersection in 3D space
- Intersecting many Points with many Polygons
- Program not outputting data correctly
- Getting Geometry of Intersection of Road SQL and Inserting Into Table
- Finding n numbers common over N lists
- Intersection of data in oracle
- How to split a self-intersection polygon to multipolygon
- Find the Intersection points of 2 rectangles
- how to check if two points are on the same line in postgis
- How to Check intersection between two images on a specific location?
- SVG intersection of elements with transforms
Related Questions in LINE-SEGMENT
- Sorting and grouping array of line segments that describes polygons
- Transfering line segments from a plot to another with corresponding points on different coordinates
- THREE.js LineSegments with multimaterial support
- Paraview create line segments from CSV with "width" data
- Generating a lattice graph from line segments
- Ramer Douglas Peucker Algorithmn (Python)
- Determining Number of Line Segment Intersections
- Line segmentation detection line draw by hand
- Speeding up segment/set of segment intersection
- Trying to find an algorithm to detect rectangles in images
- Clustering similar lines with HDBSCAN
- How to find intersections of all line segments built on polygon vertices?
- Three.js remove holes / inner lines in LineSegments
- Why do we need to round when computing x-intercept of horizontal line in Cohen-Sutherland clipping algorithm?
- How to realize the conversion animation of two LineSegments in Three.js
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
"Real-time Collision Detection" by Ericson (table of contents) is a great resource for solving problems like this. Chapter 7 spatial partitioning lists a number of methods suitable for solving such problems.
Consider starting with Octrees, KD-Trees or spatial hashing. They are all reasonably easy to implement, and will make the problem go from O(n^2) to (from memory) O(n log n)