.NET
cancel
Showing results for 
Show  only  | Search instead for 
Did you mean: 

How to know the orientation of a polyline

30 REPLIES 30
SOLVED
Reply
Message 1 of 31
ccalvo12
6640 Views, 30 Replies

How to know the orientation of a polyline

Hello. A query, any of you know any method or function that tells me the orientation of a polyline, if it is clockwise or counter-clockwise

 

Thanks

30 REPLIES 30
Message 2 of 31
hgasty1001
in reply to: ccalvo12

Hi,

 

Search google for Signed Area, depending on convention, if the signed area is positive then you have a ccw, if not cw, and if is 0 then is a degenerated polyline (just a line).

 

Gaston Nunez

 

 

Message 3 of 31
Hallex
in reply to: ccalvo12

Try Clockwise function written by _gile from this page:

http://www.acadnetwork.com/topic-250.msg447.html#msg447

_____________________________________
C6309D9E0751D165D0934D0621DFF27919
Message 4 of 31
ccalvo12
in reply to: ccalvo12

Many thanks:

Using the formula for finding areas using determinants i was able to develop a simple function.

Greetings and thanks

 

Private Function SentidoPoli(ByVal pto3DPoli As Point3dCollection) As Boolean
        Dim r As Integer = pto3DPoli.Count
        Dim Matris(r, 2) As Double
        Dim rrIz As ArrayList = New ArrayList
        Dim rrDe As ArrayList = New ArrayList
        Dim sumaIz As Double = 0
        Dim sumaDe As Double = 0
        Dim area As Double = 0
        For i As Integer = 0 To r - 1
            Matris(i, 0) = pto3DPoli.Item(i).X
            Matris(i, 1) = pto3DPoli.Item(i).Y
            Matris(i, 2) = pto3DPoli.Item(i).Z
        Next
        For i As Integer = 0 To r - 2
            rrIz.Add(Matris(i, 0) * Matris(i + 1, 1))
            rrDe.Add(Matris(i + 1, 0) * Matris(i, 1))
        Next
        For i As Integer = 0 To rrIz.Count - 1
            sumaIz += rrIz.Item(i)
            sumaDe += rrDe.Item(i)
        Next
        area = 0.5 * ((sumaIz) - (sumaDe))
        If area > 0 Then
            Return True
        Else
            Return False
        End If
    End Function

 

Message 5 of 31
DouceDeux
in reply to: ccalvo12

How about comparing the start and end points for only the first 2 line segments?

Message 6 of 31

Are you sure that's a good idea?

Відповідь корисна? Клікніть на "ВПОДОБАЙКУ" цім повідомленням! | Do you find the posts helpful? "LIKE" these posts!
Находите сообщения полезными? Поставьте "НРАВИТСЯ" этим сообщениям!
На ваше запитання відповіли? Натисніть кнопку "ПРИЙНЯТИ РІШЕННЯ" | Have your question been answered successfully? Click "ACCEPT SOLUTION" button.
На ваш вопрос успешно ответили? Нажмите кнопку "УТВЕРДИТЬ РЕШЕНИЕ"


Alexander Rivilis / Александр Ривилис / Олександр Рівіліс
Programmer & Teacher & Helper / Программист - Учитель - Помощник / Програміст - вчитель - помічник
Facebook | Twitter | LinkedIn
Expert Elite Member

Message 7 of 31

Hmmm, you made me doubt my suggestion. Let's see.

I'm writing this whiling analizing the cases, so I won't know my final conclusion until the end of the post.

 

The succession of polyline segments are created in 1 of 4 cases. I'm attaching the image describing those 4 cases.

Note: case 4 is the most comon case.

In all cases the point for the end of segment 1 is the same as the start of segment 2, so comparing them won't give us any information. That is why I suggested comparing the start point of segment 1 and the end point of segment 2.

Let's analize the cases:

Let's call the coordinates Seg1Start.X, Seg1Start.Y, Seg2Start.X and Seg2Start.Y.

Case 1:

  • The Seg1Start.X is higher than Seg2End.X and Seg1Start.Y lower than Seg2End.Y, that means Seg1Start is to the right and below of Seg2End. Seg2 can be as long as you want. The angle can go from 0 to 180 degrees. If the angle is 0 and if Seg2End and Seg1Start are the same, the result of comparing them would be ambiguous, something that would have to be controlled. If the angle is 180. Seg2End would be left of Seg1Start, making the polyline clockwise. Anything out of that angle range would make Case1 turn into Case3. Case 1 is clockwise.

Case 2:

  • Anything out of angle range turns it into Case4. Overlapping of Seg1Start and Seg2End points must be controlled for ambiguity. Case2 is counter-clockwise.

Case 3:

  • Anything out of angle range turns it into Case1. Overlapping of Seg1Start and Seg2End points must be controlled for ambiguity. Case3 is counter-clockwise.

Case 4:

  • Anything out of angle range turns it into Case2. Overlapping of Seg1Start and Seg2End points must be controlled for ambiguity. Case4 is clockwise.

I might be missing something (validation for weird cases). It's just a quick look at the problem.

Can you take a look at my post about hatches?

I always create threads and no one replies with ideas or advise @.@My hatch post

Message 8 of 31

25-02-2013 16-34-38.png

 

First two segment are idetical...

Відповідь корисна? Клікніть на "ВПОДОБАЙКУ" цім повідомленням! | Do you find the posts helpful? "LIKE" these posts!
Находите сообщения полезными? Поставьте "НРАВИТСЯ" этим сообщениям!
На ваше запитання відповіли? Натисніть кнопку "ПРИЙНЯТИ РІШЕННЯ" | Have your question been answered successfully? Click "ACCEPT SOLUTION" button.
На ваш вопрос успешно ответили? Нажмите кнопку "УТВЕРДИТЬ РЕШЕНИЕ"


Alexander Rivilis / Александр Ривилис / Олександр Рівіліс
Programmer & Teacher & Helper / Программист - Учитель - Помощник / Програміст - вчитель - помічник
Facebook | Twitter | LinkedIn
Expert Elite Member

Message 9 of 31

Well, we'd have to establish the criteria to clasify a polygon as clockwise or counter-clockwise.

I thought it depended on the order of the vertices of the polygon.

It's a matter that requires a bit of reading time I don't have right now.

You are right, that's another case. I think I was just considering quadrilaterals XDDD

 

I found this: http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clock...

 

and this: http://debian.fmi.uni-sofia.bg/~sergei/cgsr/docs/clockwise.htm

Message 10 of 31
_gile
in reply to: DouceDeux

Hi,

 

As said gasty1001, you can use the algebraic area (signed area) with non self crossed polylines.

 

Here's a little static class defining extension methods (works with arc segment polyline too).

    public static class AlgebraicArea
    {
        public static double GetArea(Point2d pt1, Point2d pt2, Point2d pt3)
        {
            return (((pt2.X - pt1.X) * (pt3.Y - pt1.Y)) -
                        ((pt3.X - pt1.X) * (pt2.Y - pt1.Y))) / 2.0;
        }

        public static double GetArea(this CircularArc2d arc)
        {
            double rad = arc.Radius;
            double ang = arc.IsClockWise ?
                arc.StartAngle - arc.EndAngle :
                arc.EndAngle - arc.StartAngle;
            return rad * rad * (ang - Math.Sin(ang)) / 2.0;
        }

        public static double GetArea(this Polyline pline)
        {
            CircularArc2d arc = new CircularArc2d();
            double area = 0.0;
            int last = pline.NumberOfVertices - 1;
            Point2d p0 = pline.GetPoint2dAt(0);

            if (pline.GetBulgeAt(0) != 0.0)
            {
                area += pline.GetArcSegment2dAt(0).GetArea();
            }
            for (int i = 1; i < last; i++)
            {
                area += GetArea(p0, pline.GetPoint2dAt(i), pline.GetPoint2dAt(i + 1));
                if (pline.GetBulgeAt(i) != 0.0)
                {
                    area += pline.GetArcSegment2dAt(i).GetArea(); ;
                }
            }
            if ((pline.GetBulgeAt(last) != 0.0) && pline.Closed)
            {
                area += pline.GetArcSegment2dAt(last).GetArea();
            }
            return area;
        }
    }

 

Using example:

        [CommandMethod("Test")]
        public void ClockwisePolyline()
        {
            Document doc = AcAp.DocumentManager.MdiActiveDocument;
            Database db = HostApplicationServices.WorkingDatabase;
            Editor ed = doc.Editor;
            using (Transaction tr = db.TransactionManager.StartTransaction())
            {
                BlockTableRecord btr =
                    (BlockTableRecord)db.CurrentSpaceId.GetObject(OpenMode.ForWrite);
                PromptEntityOptions peo = new PromptEntityOptions("\nSelect a polyline: ");
                peo.SetRejectMessage("Selected object is not a polyline.");
                peo.AddAllowedClass(typeof(Polyline), false);
                while (true)
                {
                    PromptEntityResult per = ed.GetEntity(peo);
                    if (per.Status != PromptStatus.OK) break; ;
                    Polyline pline = (Polyline)per.ObjectId.GetObject(OpenMode.ForRead);
                    double area = pline.GetArea();
                    Application.ShowAlertDialog(
                        string.Format("{0}\nArea = {1}", area < 0 ? "CW" : "CCW", area));
                }
                tr.Commit();
            }
        }

 

 



Gilles Chanteau
Programmation AutoCAD LISP/.NET
GileCAD
GitHub

Message 11 of 31
hgasty1001
in reply to: _gile

Hi,

 

Nice code Gilles, just want to say that if performance is important, you don't need to divide by 2 the area, just the sign matters for the test, may be I'm wrong, but I think the same apply for arcs, it doesn't matter the area of them just the start and end point order.

 

Gaston Nunez

Message 12 of 31
_gile
in reply to: hgasty1001

Thanks Gaston,

 

I know that, but as these extension methods may be reusable, I prefered let them return the right area.

About performance issue, I think (without testing) this won't be sensible until you're looping through many polylines having a great number of vertices...



Gilles Chanteau
Programmation AutoCAD LISP/.NET
GileCAD
GitHub

Message 13 of 31


@hgasty1001 wrote:
...but I think the same apply for arcs, it doesn't matter the area of them just the start and end point order...

Are you sure? Smiley Wink

26-02-2013 8-29-15.png

Відповідь корисна? Клікніть на "ВПОДОБАЙКУ" цім повідомленням! | Do you find the posts helpful? "LIKE" these posts!
Находите сообщения полезными? Поставьте "НРАВИТСЯ" этим сообщениям!
На ваше запитання відповіли? Натисніть кнопку "ПРИЙНЯТИ РІШЕННЯ" | Have your question been answered successfully? Click "ACCEPT SOLUTION" button.
На ваш вопрос успешно ответили? Нажмите кнопку "УТВЕРДИТЬ РЕШЕНИЕ"


Alexander Rivilis / Александр Ривилис / Олександр Рівіліс
Programmer & Teacher & Helper / Программист - Учитель - Помощник / Програміст - вчитель - помічник
Facebook | Twitter | LinkedIn
Expert Elite Member

Message 14 of 31

Hi Alexander,

 

No, I was not sure, that's why I started with: "may be I'm wrong". Thanks for the counterexample.

 

Gaston Nunez

Message 15 of 31
BKSpurgeon
in reply to: _gile

Hi Gilles

 

I am getting an error with your above code:

 

"extension method must be defined in a top level static class; AlgebraicArea is a nested class" error.

 

It is probably very easy to fix if one knows how. 

 

any ideas?

 

 

Message 16 of 31
_gile
in reply to: BKSpurgeon

Hi,

 

All is said in the error message: the AlgebraicArea static class have to be a top level class instead of a nested class.

 

SomeNamespace
{
    OneTopLevelClass
    {
        // ...
       SomeNestedClass
        {
            // ...
        }
    }
    AnotherToplevelClass
    {
        // ...
    }
}


Gilles Chanteau
Programmation AutoCAD LISP/.NET
GileCAD
GitHub

Message 17 of 31

 

Document doc = Application.DocumentManager.MdiActiveDocument;
Database db = doc.Database;
Editor ed = doc.Editor;

 

using (Transaction acTrans = doc.TransactionManager.StartTransaction())
{


foreach (ObjectId plineId in plineIds)
{
Boolean isCCW = false;
Polyline acPoly = (Polyline)acTrans.GetObject(plineId, OpenMode.ForRead);

VladUtils.qacBB.BoundingBox bbtempoPline = VladUtils.qacBB.GetBoundingBox(plineId, acTrans);
qNGeom.qContour points = qacPoints.GetEntPoints(plineId);
//no bulges
if (!acPoly.HasBulges)
{
isCCW = points.IsCCW(precision);
}
else
//bulges
{

int LowestRightestPointInd = vldplUniversalPolylines.IntersectionAnalytics.GetLowestRightestPointInd(points, precision);
//arc arenot lower points
if (qNMath.IsSameNumbers(points.Contour[LowestRightestPointInd].y, bbtempoPline.minPoint.y, precision))
{
isCCW = points.IsCCW(precision);
}
else
{
for(int i=0; i< acPoly.NumberOfVertices; i++)
{
double curbulge = acPoly.GetBulgeAt(i);
if (!qNMath.IsZero(curbulge, precision))
{
CircularArc2d ccc = acPoly.GetArcSegment2dAt(i);


if (qNMath.IsSameNumbers(ccc.OrthoBoundBlock.BasePoint.Y, bbtempoPline.minPoint.y, precision))
{
isCCW = !ccc.IsClockWise;
break;
}
}
}
}
}
string result = (isCCW) ? "isCCW" : "NOT isCCW";
ed.WriteMessage("\n " + result);

Message 18 of 31

public static Boolean IsCCW(Transaction acTrans, ObjectId plineId, double precision)
{
Polyline acPoly = (Polyline)acTrans.GetObject(plineId, OpenMode.ForRead);

VladUtils.qacBB.BoundingBox bbtempoPline = VladUtils.qacBB.GetBoundingBox(plineId, acTrans);
qNGeom.qContour points = qacPoints.GetEntPoints(plineId);
//no bulges
if (!acPoly.HasBulges)
{
return points.IsCCW(precision);
}
else
//bulges
{

int LowestRightestPointInd = vldplUniversalPolylines.IntersectionAnalytics.GetLowestRightestPointInd(points, precision);
//arc arenot lower points
if (qNMath.IsSameNumbers(points.Contour[LowestRightestPointInd].y, bbtempoPline.minPoint.y, precision))
{
return points.IsCCW(precision);
}
else
{
if (acPoly.NumberOfVertices == 2 && !qNMath.IsZero(acPoly.GetBulgeAt(0), precision) && !qNMath.IsZero(acPoly.GetBulgeAt(1), precision))
{
if(acPoly.GetArcSegment2dAt(0).Radius> acPoly.GetArcSegment2dAt(1).Radius)
{
return !acPoly.GetArcSegment2dAt(0).IsClockWise;
}
else
{
return !acPoly.GetArcSegment2dAt(1).IsClockWise;
}
}
else
{
for (int i = 0; i < acPoly.NumberOfVertices; i++)
{
double curbulge = acPoly.GetBulgeAt(i);
if (!qNMath.IsZero(curbulge, precision))
{
CircularArc2d ccc = acPoly.GetArcSegment2dAt(i);


if (qNMath.IsSameNumbers(ccc.OrthoBoundBlock.BasePoint.Y, bbtempoPline.minPoint.y, precision))
{
return !ccc.IsClockWise;

}
}
}
}
}
}
return false;
}

Message 19 of 31

@VladPaly

 

Paste please the formatted code:

2017-10-13_0-15-13.png

 

 

Відповідь корисна? Клікніть на "ВПОДОБАЙКУ" цім повідомленням! | Do you find the posts helpful? "LIKE" these posts!
Находите сообщения полезными? Поставьте "НРАВИТСЯ" этим сообщениям!
На ваше запитання відповіли? Натисніть кнопку "ПРИЙНЯТИ РІШЕННЯ" | Have your question been answered successfully? Click "ACCEPT SOLUTION" button.
На ваш вопрос успешно ответили? Нажмите кнопку "УТВЕРДИТЬ РЕШЕНИЕ"


Alexander Rivilis / Александр Ривилис / Олександр Рівіліс
Programmer & Teacher & Helper / Программист - Учитель - Помощник / Програміст - вчитель - помічник
Facebook | Twitter | LinkedIn
Expert Elite Member

Message 20 of 31
ActivistInvestor
in reply to: VladPaly


@VladPaly wrote:

 

<snip>

 

VladUtils.qacBB.BoundingBox bbtempoPline = VladUtils.qacBB.GetBoundingBox(plineId, acTrans);

 

<snip>

 


What is the purpose of posting code here that calls other code that isn't included???

Can't find what you're looking for? Ask the community or share your knowledge.

Post to forums  

Autodesk DevCon in Munich May 28-29th


Autodesk Design & Make Report

”Boost