Menu
A Computational Geometry problem:
The point P0 is chosen randomly on an edge (e.g.,EB) of a polygon (e.g.,BCDE), to find possible points (i.e., P1,P2,P3,...) on other edges based on the given distance (i.e., r). The following demonstration shows a solution by finding intersections between the circle centered on the point P0 and the edges of polygon. So the problem basically could be solved by Circle--Line-Segment intersection analysis.
I wonder is there any more efficient method for this very simple problem in terms of computation cost? The process will be evaluated several million times so any improvemnt is of interest.
Updates:
Thanks for your comments. Please consider my comments on comments which helps to clarify the question more. Not willing to repeat them here, encouraging to consider all comments and answers ;).
I just implemented the method of Circle--Line-Segment Intersection based on the algorithm found [here]. Actually I adapted it to work with line-segments. The benchmark of the algorithm implemented in Python is as follows:
The number of line segments is: 100,000 and the system is usual desktop. The elapsed time is: 15 seconds. Hope these are helpful to give some idea of computation cost. Implementation of core in Fortan could improve the performance significantly.
However the translation is the last step.
713
The intersections of two circles determine a line known as the radical line. If three circles mutually intersect in a single point, their point of intersection is the intersection of their pairwise radical lines, known as the radical center.
We can determine a region in which the points for each polygon lie, and this line is a separating axis if these regions do not overlap. If, after checking each line from both polygons, no separating axis was found, it has been proven that the polygons intersect and something has to be done about it.
That is, a polygon is concave when at least one of its inside angles is greater than 180 degrees. Notice that no matter where you place two points within a circle, the line connecting the two points never goes outside the circle. Therefore, a circle is not concave; when a shape is not concave, we call it convex.
Description and Derivation. As we can see in above diagram, for each pair of circles, there can be maximum two intersection points.
For intersection between line (or line-segment) and a circle (sphere in 3D) there is a bit more explanation, implementation details and also Python, C etc sample codes in [this link]. You may try them for your problem.
The idea is basically the same as you have already found in [here].
127
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
