Detecting self-intersecting polylines (without the API)

Scripting
,
1

Hi,

I’m looking for a clever way to determine whether a polyline is self-intersecting or not!

Screenshot 2021-03-30 at 11.18.32
Screenshot 2021-03-30 at 11.18.32740×747 11.3 KB

Is there a more clever way than comparing each line segment to all other segments and determining intersections that are not at the end points?

Any ideas?

Thanks.

2

SelSelfIntersectingCrv ? Or is this uniquely a scripting question?

https://developer.rhino3d.com/api/RhinoCommon/html/M_Rhino_Geometry_Intersect_Intersection_CurveSelf.htm

3

No for a generic case. But instead of doing a simple loop like this (in C#):

for(int i = 0; i< pln.SegmentCount; i++)
{
   var si = pln.SegmentAt(i);
   for(int    j = 0;    j<pln.SegmentCount; j++)
   {
       var sj = pln.SegmentAt(j);
       // line line intersection
   }
}

i0 j0, i0 j1… i0 jn
i1 j0, i1 j1… i1 jn
…
in j0, in j1… in jn

you can improve efficiency by avoiding duplicate comparisons:

for(int i = 0; i< pln.SegmentCount; i++)
{
   var si = pln.SegmentAt(i);
   for(int    j = i+1;     j<pln.SegmentCount; j++)
   {
       var sj = pln.SegmentAt(j);
       // line line intersection
   }
}

i0 j1, i0 j2… i0 jn
i1 j2, i1 j3… i1 jn
…
in-2 jn-1, in-2 jn
in-1 jn

1 Like
4

I need to accomplish it without using the API as mentioned above!

Thanks for the suggestion. And avoiding rechecking segments that already have been probed is a great idea! :slight_smile:

5

I don’t know what your are really referring to when you use the term API…

I posted the Rhino native command solution plus the RhinoCommon method…

6

Sounds like a coding interview problem?

What are your constraints? ( time and money?) Try to keep your solution to O ( log n). In other words if you not only ignore, but also remove elements from a collection you can achieve this. You can implement a HashTable which has O(1) time complexity on lookups ( on a good day, i.e no hash collisions).

7

No worries! By “API” I mean RhinoCommon or related libraries (i.e. rhinoscriptsyntax, etc.). I want to implement it from scratch myself. :slight_smile:

Haha, could be, but in my case not really. :slight_smile: It’s rather something that I’m interested in for a small project of mine.

There are none, but coding it shouldn’t take forever. If I first need to come up with 10 other algorithms only to finally gain 1 or 2 seconds, it currently isn’t worth the time investment for me.

I appreciate your input, but what would the role of the hash table be exactly here?

8

How are you going to do that? First to have access to elements in Rhino you need to use some sort of code to get the GUIDS and then the geometry from them. So you are already using some RhinoCommon or other “API”. Next, yes, if they are just lines (i.e. two connected points in space) you could possibly use some relatively simple equations or trig to figure out if they intersect somewhere. Otherwise it’s fairly complex math as far as I understand.

The C# code above by @Dani_Abalde has lots of “API” like pln.SegmentAt() or pln.SegmentCount(), not to mention // line line intersection…

9

Not really! I’m approaching it from another angle. :wink: I’ve implemented everything I need already. Point, vector, line, plane, polyline, etc.! Plus a translation layer from my custom classes to RhinoCommon, to preview stuff in Rhino, export geometry through Rhino, and so fourth.

Yes, I have that part already! Finite line-line-intersections are pretty easy to figure out. There is lots of documentation online and in maths books.

I’ve implemeted most of what I need. Don’t worry about it! My polyline may not have a SegmentAt() method, but there are other ways to get a desired line segment.

What I am curious about is how polyline self-intersections, like shown above, are usually detected!

10

There are ways of speeding it up, like sorting the end points in one direction and going through in order only checking for intersections between segments that overlap in that axis. If your polylines only have a few segments I doubt this matters much for speed compared to simply checking all against all though - a line-line intersection check should be fairly cheap.
http://geomalgorithms.com/a09-_intersect-3.html#Shamos-Hoey-Algorithm

I’m curious what this is for - does it have to run somewhere without Rhino?

1 Like
11

Yes, it’s for an artsy thing - a media installation if you want - that has to be able to run on a small, arm-based computer like a Raspberry Pi, and since there is no Rhino for Linux, I’ve written a very basic geometry framework in C++ that can communicate with Rhino through Python and ctypes. ctypes is a Python library that lets you extend Python with C++.
Rhino will be used to compose a big geometry scene of what happened over a certain period of time that the installation has run and collected data, if that make sense, thus the translation layer.

Thanks for the link! :slight_smile:

12

Hmm assuming your space is longer than it is wide you could sort the segments in that direction and stop once you have passed the end of your segment… that said sorting may take a long time if you have to implement your own sort algorithm :thinking: The bisect module in (micro)python might help you maintain a sorted list

1 Like
13

You could use a ray plane intersection which is rather fast and easy to solve analitically, your rays would be something like points[i+1] - points[i] and your planes would be a similar access pattern that start from the other way around createPlaneFromTwoVectorsOrSomething( points[points.Length - i] - points[points.Length - i - 1], new Vector( 0., 0., 1 ) ). Never tried it but it sound plausible in my head.
EDIT: the linked article defines the plane from a normal and a starting point so, the mentioned access pattern to calculate the cross product between that vector and and up vector (if you are only dealing with 2d stuff). Also to get a quad instead of a plane I think that clamping/restricting the ranges of the plane would suffice.

1 Like
14

See this

1 Like
15

If the polylines are planar, as in your examples, you could use a standard drawing algorithm, and mark each “pixel” with some way to tell which segments hit it. Then intersect any pair of non-adjacent pairs that hit the same pixel. I guess this would still work for non-planars.

1 Like
16

Thanks for pointing out the bisect module. I didn’t know about that and it sure will come in handy in the future. In don’t exactly follow how your sorting in a dominant spacial direction would facilitate intersecting? Could you maybe expand on that?
C++ has most common sorting algorithms in its standard library. There’s no need to implement any unless something custom is needed.

This is a great suggestion! Thank you. I even have most necessary functions already setup. I’m dealing with planar, thus locally two-dimensional polylines but in 3D space.

Sounds like a great idea! Thanks. :slight_smile:

17

If you sort your previous curves in max(x_coordinate) order then once you have passed the max_x of your new curve you can stop counting and avoid having to check intersections on every other curve. If your curves are very short compared to the domain then this could save a lot of time, especially if you do a bisection search rather than starting from the beginning, but depending on the situation you may have to maintain two lists max(x) and min(x).

If the pixel approach works for you, and if you can implement a hash table to find existing pixels, then that sounds perfect.

1 Like