topic Re: How do I know whether the polyline overlap itself? in .NET Forum

How do I know whether the polyline overlap itself?

Anonymous — Wed, 05 Oct 2011 14:41:38 GMT

Hi Guys，

I have a polyline and need to check whether it overlap itself. What do I need to do in vb.net?

Thanks

Yaqi

Re: How do I know whether the polyline overlap itself?

chiefbraincloud — Thu, 06 Oct 2011 18:02:46 GMT

There are several IntersectWith methods available from various classes, but I can recall that some or all of those methods have the specific limitation of not discovering self-intersecting polylines. So without spending a bunch of time checking the help for each one of them, I would suggest getting the individual line segments (and/or arc segments) and checking each one of those for intersections with each of the others. I can probably work something up pretty quick, if you need it.

Re: How do I know whether the polyline overlap itself?

abdul.rafee — Tue, 26 Feb 2013 07:46:08 GMT

Please help me to send that code to my mail id if possible.

my mail id id abdulrfaee.gis@gmail.com

Thank you.

Re: How do I know whether the polyline overlap itself?

chiefbraincloud — Wed, 27 Feb 2013 07:18:59 GMT

To provide code that actually works, we would need to know the version of AutoCAD you are working with, in particular wether you are working with 2010-2012/or 2013 or greater. If you are working with older than 2010, that may make a difference as well.

Also, if you could provide the code you have, along with the specific problem you have, we could help you fix it.

Lastly, regardless of the previous suggestions, I would only post my code to this forum. If I email it to you, then only you can benefit from it, but if I post it here then others can also find it.

it is clear that your first language is not English, so I hope you can understand or translate what I am saying properly.

Re: How do I know whether the polyline overlap itself?

Anonymous — Wed, 27 Feb 2013 13:30:03 GMT

I have an idea.

How about getting the start and end points for the line segments and using linear algebra to check if any of those lines intersect O.o? But if you have arcs in the polyline... then I wouldn't know what to do XD

Re: How do I know whether the polyline overlap itself?

DiningPhilosopher — Thu, 28 Feb 2013 06:28:05 GMT

@Anonymous wrote:
I have an idea.
How about getting the start and end points for the line segments and using linear algebra to check if any of those lines intersect O.o? But if you have arcs in the polyline... then I wouldn't know what to do XD

Or, he could just P/Invoke this:

bool acdbIsRealSelfIntersectEntity(class AcDbEntity *)

Re: How do I know whether the polyline overlap itself?

Alexander.Rivilis — Thu, 28 Feb 2013 12:22:01 GMT

Tony! You dug another undocumented function?

Re: How do I know whether the polyline overlap itself?

Anonymous — Thu, 28 Feb 2013 14:45:36 GMT

Now that I think about it, you could create an approximate function for the curve (arc) and with a margin error, check if the polyline intersects itself.

I just wonder how the function tells the polyline intersects itself. I'm sure it would be much easier for that value to be calculated just once everytime the polyline changes and then just be accessed instead of it being calculated everytime a method be called. both scenarios have their prons and cons >.<

Re: How do I know whether the polyline overlap itself?

chiefbraincloud — Thu, 28 Feb 2013 23:05:21 GMT

There is no need for that. If you simply break the polyline down into its components, using GetSegmentType to tell you whether to call GetArcSegmentAt or GetLineSegmentAt, then you will have a collection of CircularArc3d, and LineSegment3d. then you can loop through that collection calling IntersectWith on all the other objects in the collection, and make sure to ignore any intersections that may appear because of the coincident start and end points of adjacent segments.

You could probably even make it logically simpler, but programmatically messier, by calling explode on the polyline to get a collection of Lines and Arcs.

That said, the PInvoke mentioned above is intriguing, but I don't see the function documented in the 2012 Arx SDK, so I'll have to do some digging to see if I can find it, unless Tony would like to elaborate on the signature.

Re: How do I know whether the polyline overlap itself?

DiningPhilosopher — Fri, 01 Mar 2013 02:20:57 GMT

@chiefbraincloud wrote:

That said, the PInvoke mentioned above is intriguing, but I don't see the function documented in the 2012 Arx SDK, so I'll have to do some digging to see if I can find it, unless Tony would like to elaborate on the signature.

The function isn't documented, meaning the standard caveat applies: Use it at your own risk.

Of course, one can't help but wonder why the public API of a $4K CADD product can't answer a simple question like the one asked by the subject line of this thread.

The entry point signature is platform-dependent, and you can find it acdbxx.dll, by using Depends.exe or dumpbin.

Re: How do I know whether the polyline overlap itself?

DiningPhilosopher — Fri, 01 Mar 2013 02:36:11 GMT

@chiefbraincloud wrote:
There is no need for that. If you simply break the polyline down into its components, using GetSegmentType to tell you whether to call GetArcSegmentAt or GetLineSegmentAt, then...

I'm not sure there's any need for that either, at least, in the most common usage cases.

// Excerpts from CurveExtensionMethods.cs  (C)  2009-2012   Tony Tanzillo
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Autodesk.AutoCAD.Geometry;

namespace Autodesk.AutoCAD.DatabaseServices
{
   public static class PolylineExtensionMethods
   {
      /// <summary>
      /// Returns true if the given Polyline is self-intersecting.
      /// 
      /// This API defines self-intersection as follows:
      /// 
      /// The Polyline is self-intersecting if any of the
      /// following conditions are true:
      /// 
      /// 1.  Any segment intersects any other segment.
      /// 
      /// 2.  Any interior vertex lies directly on any segment.
      ///     or is coincident with any other vertex.
      /// 
      /// 3.  If the polyline is effectively-closed (e.g.,
      ///     the first and last vertices are coincident, but
      ///     the PolyLine's Closed property is false), the
      ///     polyline is considered self-intersecting.
      ///     
      ///  4. A Closed polyline with < 3 vertices
      ///     is considered to be self-intersecting.
      ///     
      /// The definition is intended to be consistent with the 
      /// REGION command's definition of self-intersecting.
      ///     
      /// You may wish to interpret any of the above differently 
      /// depending on your specific functional requirements.
      /// 
      /// </summary>

      public static bool IsSelfIntersecting( this Polyline pline )
      {
         int numverts = pline.NumberOfVertices;
         if( numverts < 3 )
         {
            return pline.Closed;
         }

         Point3dCollection points = new Point3dCollection();

         pline.IntersectWith( pline, Intersect.OnBothOperands, points, 
            IntPtr.Zero, IntPtr.Zero );

         if( ! pline.Closed )
            numverts -= 2;

         return points.Count != numverts;
      }
   }
}

Re: How do I know whether the polyline overlap itself?

chiefbraincloud — Fri, 01 Mar 2013 03:35:22 GMT

I saw that you had posted that code earlier, and if it works, that's great. I can't test it at the moment, so I don't know.

My previous statements, as I had indicated in my first reply back in Oct 2011, were based on the fact that I thought Entity.IntersectWith did not work with Self Intersecting polylines (my recollection would be that I read it somewhere in the docs, but I looked at a few things earlier today, and I can't seem to find where I read it.)

Re: How do I know whether the polyline overlap itself?

DiningPhilosopher — Fri, 01 Mar 2013 04:03:07 GMT

The version I posted earler and removed doesn't care about effectively-closed polylines because for my own purposes, the code was only used for checking polylines used to create regions, and the region API accepts effectively-closed polylines. But I can't assume that's what the OP is doing, and decided to revise the code to be more consistent with the more general use case and definition of self-intersecting, where effectively-closed polyines are considered self-intersecting.

As far as the question of whether it works, that depends on the specific use case, and in-turn on what precisely 'self-intersecting' means. It doesn't necessarily have a consistent definition beyond the most simple case of segments intersecting other segments, which as far as I can tell, was the only thing that the other proposed solutions actually check for.