Forgive me, I thought we had to assign coordinates to point and boundary data.

If the locations for the inny and outy points, along with the boundary points is given, and if the boundary is closed, it should be quick and easy to determine if a data point is inside or outside the boundary.

The procedure would be like this. If the point is inside the boundary, the x coordinate of the point in question, will have a minimum of two common x coordinates in the boundary table on that axis. As long as the data point is within the inner range of the boundary points on that axis........it's inside.

Now do the same to the y coordinate. As long as both of the data point coordinates are inside the inner range of the matching boundary coordinates..................on both axis..........the point would be on the inside.

If both of these conditions are not met....the point is on the outside.

Even if the boundary is a multi shaped manifold, this should be easy....because in and out alternate with boundary. Then just check if point is inside one of the inside ranges.

This can all be done with just the data and boundary coordinates.

Does that make any sense?

 

Forgive me, I thought we had to assign coordinates to point and boundary data.

If the locations for the inny and outy points, along with the boundary points is given, and if the boundary is closed, it should be quick and easy to determine if a data point is inside or outside the boundary.

The procedure would be like this. If the point is inside the boundary, the x coordinate of the point in question, will have a minimum of two common x coordinates in the boundary table on that axis. As long as the data point is within the inner range of the boundary points on that axis........it's inside.

Now do the same to the y coordinate. As long as both of the data point coordinates are inside the inner range of the matching boundary coordinates..................on both axis..........the point would be on the inside.

If both of these conditions are not met....the point is on the outside.

Even if the boundary is a multi shaped manifold, this should be easy....because in and out alternate with boundary. Then just check if point is inside one of the inside ranges.

This can all be done with just the data and boundary coordinates.

Does that make any sense?

Could you provide a graphic example?

 

Take the first coordinate of the point. Let's say that x = -4. Now look at the boundary table. If there is not at least two entries of the boundary table with -4 as it's x coordinate.......the point is out.

Let's say we found two entries of the boundary table with -4 as x. So it is possible that we are on the inside. To confirm, we look at y coordinate. If the y coordinate of the point, is between the two y values of the boundary table, we are inside. If the y point is outside the boundary spread, we are outside.

Fast and simple.

 

Forgive me, I thought we had to assign coordinates to point and boundary data.

If the locations for the inny and outy points, along with the boundary points is given, and if the boundary is closed, it should be quick and easy to determine if a data point is inside or outside the boundary.

The procedure would be like this. If the point is inside the boundary, the x coordinate of the point in question, will have a minimum of two common x coordinates in the boundary table on that axis. As long as the data point is within the inner range of the boundary points on that axis........it's inside.

Now do the same to the y coordinate. As long as both of the data point coordinates are inside the inner range of the matching boundary coordinates..................on both axis..........the point would be on the inside.

Since you won't provide a drawing, I guess I'll have to do it for you.



Since both of your conditions are met, I guess you are claiming that the red point is within the black shape.

Even if the boundary is a multi shaped manifold, this should be easy....because in and out alternate with boundary. Then just check if point is inside one of the inside ranges.

This can all be done with just the data and boundary coordinates.

Does that make any sense?

Now you are talking about things alternating, which leads me to think that you are on the right track (or at least a valid one), and the approach you are describing here is essentially the same as the one I recommended clear back in Post #3 (or so). Except you are checking at least 4x as many things as you need to.

All you need to do is pick ANY direction and see if the line segment going in that direction from the point in question crosses the boundary an even or odd number of times. You don't need to check both directions in the X and then both directions in the Y to accomplish this -- ANY ONE direction will work just find.

The shapes in question here (go back and look at the OP) are defined by a finite set of vertex points with straight line segments connecting them.

 

Take the first coordinate of the point. Let's say that x = -4. Now look at the boundary table. If there is not at least two entries of the boundary table with -4 as it's x coordinate.......the point is out.

Let's say we found two entries of the boundary table with -4 as x. So it is possible that we are on the inside. To confirm, we look at y coordinate. If the y coordinate of the point, is between the two y values of the boundary table, we are inside. If the y point is outside the boundary spread, we are outside.

Fast and simple.

Where is this boundary table coming from?

As you describe it, you would have to have thousands of entries in your "boundary table" just to deal with a simple square that is 500 units on a side. Even then, what if the x-coordinate of the first point is -4.017463 ?

 

Let's use the following toy data set.

Boundary vertices:

#|X|Y
1|-3.4 | 2.9
2|-1.2 | 6.3
3|2.15 | 4.19
4|1.35 | -2.57
5|-1.78 | -1.78
6|0.25 | 4.75
7|-1.5 | 5.5
8|-3 | -2.9
9|-3.4 | 2.9

Candidate Points

#|X|Y
1| 0.1 | 4.6
2| -1.9 | 4.9
3| -2.1 | 5.5
4| -1.5 | -1.6
5| -1.1 | -2.4
6| -2.5 | -1.9
7| 1.5 | 5.1
8| -3.1 | -2.2
9| -2 | 2

Show the execution of your algorithm on this data set to determine which of these candidate points are within the shape defined by the vertices.

Start with Point #1 and show that in detail. The just show the results of running your algorithm on the rest of the data set.

 

I thought you and the TS had the boundary coordinates.

I believe my way would solve the image in post #64.

No one, nor any math will tell you if a point is in or out, if you don't define the boundary.

You can not do anything with this problem, until it is defined.

So the real problem is defining the boundary.

If you fudge in a series of small straight segments for the boundary, you could introduce small errors in point count near the boundary.

To be accurate, I would find the highest resolution of point data. I would assemble my boundary data to the same resolution.

As you say, with the high resolution, the boundary will be a large data set. But once the table is set, there should be no errors and can be accessed quickly.

This will take some memory(cheap), but hardly any processing.

 

Then, by all means, please demonstrate your algorithm, in detail, for Point #1 of the data set I provided.

 

Ok W, I'm back. Here's my take on the problem being analyzed.

​

1. Choose the vertex that is closest to the point in question
2. Construct a vector starting at that vertex and ending at the point.
3. Use the Atan2 function to:
   • Find the angle between the two vectors defined by the previous vertex and the selected vertex, and the selected vertex and the next vertex. We call that angle Ø
     
   • Find the angle between the two vectors defined by the previous vertex and the selected vertex, and the selected vertex and the point. Let's call that angle Φ
4. Using the method I described in post #35, find out in which direction the figure was drawn.
   
5. If the figure is drawn CCW then:
   • If Φ < Ø then the point is inside
   • If Φ > Ø then the point is outside
6. The previous conditions are inverted if the figure was drawn CW

Three observations about this method:

1. I admit that it's probably too computationally demanding
2. But it has the advantage of being extremely simple to understand
3. I'm pretty sure that it can be further simplified. Don't know yet how, though.

Truth being told... I still have to thoroughly read what you previously proposed, because I haven't quite understood it 100%. But I promise you I'll soon do that.

Alright... those are my cards , show me what you've got.

 

Alright... those are my cards View attachment 89232 , show me what you've got. View attachment 89233 View attachment 89234

So.... is Point #1 inside or outside the figure according to your algorithm?

Let's see if it is based on my algorithm.

Step 0: (Optional) Sort the edges based on smallest y-coordinate of defining vertices.
Note that Pt 1 and Pt 9 are the same point just so that the figure closes when plotting in something like Excel, so there's really only eight vertices.

Sorted Edges

Edge|V1|V2|y1|Y2|x1|x2
1|8|1|-2.9|2.9|-3|-3.4
2|8|7|-2.9|5.5|-3|-1.5
3|4|5|-2.57|-1.78|1.35|-1.78
4|4|3|-2.57|4.19|1.35|2.15
5|5|6|-1.78|4.75|-1.78|0.25
6|1|2|2.9|6.3|-3.4|-1.2
7|3|2|4.19|6.3|2.15|-1.2
8|6|7|5.75|5.5|0.25|-1.5

Note that only the first two columns (Edge is the index, not a data column) are needed as they can be used as indices into the existing vertex array.

Step 1: Initialize INSIDE = FALSE

Step 2: FOR EACH candidate point:
Step 2.1: Get the <x,y> coordinates Point #N: (We are only interested in Point N=1)
// XSEG = 0.1; YSEG = 4.6

Step 2.2: UNTIL: y-coordinate of the first vertex point in the edge is greater than YSEG (or all edges if Step 0 not performed).
// This condition will mean that we eliminate Edge 8, leaving {1, 2, 3, 4, 5, 6, 7}.

Step 2.2.1: IF the y-coordinate of the second vertex is less than YSEG:
Step 2.2.1.1: Proceed to the next vertex point.
// This condition will eliminate Edges {1, 3, 4}, leaving {2, 5, 6, 7}.

Step 2.2.2: IF the x-coordinates of both the vertices are less than XSEG:
Step 2.2.2.1: Proceed to the next vertex point.
// This condition will eliminate Edges {2, 6}, leaving {5, 7}.

Step 2.2.3: IF the x-coordinates of both the vertex and the following are greater than XSEG:
Step 2.2.3.1 INSIDE = !INSIDE
Step 2.2.3.2 Proceed to the next vertex point.
// This condition doesn't apply to any of the remaining edges.

Step 2.2.4: Find vector along boundary segment: <(x2 - x1), (y2 - y1)>
// Edge 5: <2.03, 6.53>; Edge 7: <-3.35, 2.11>.

Step 2.2.5: Find vector from first vertex to Point N: <(XSEG - x_{N}), (YSEG - y_{N})>
// Edge 5: <1.88, 6.38>; Edge 7: <-2.05, 0.41>.

Step 2.2.6: Find cross product of boundary vector and point vector:
// Edge 5: 0.675; Edge 7: 2.952

Step 2.2.7: IF cross product is greater than zero:
Step 2.2.7.1: INSIDE = !INSIDE
// Both edges are positive, so INSIDE is toggled twice, leaving it FALSE.

Step 2.4: IF INSIDE is TRUE:
Step 2.4.1: Add candidate point to list of points inside the shape.
// This point is NOT inside the shape.

 

So.... is Point #1 inside or outside the figure according to your algorithm?

Let's see if it is based on my algorithm.

Step 0: (Optional) Sort the edges based on smallest y-coordinate of defining vertices.
Note that Pt 1 and Pt 9 are the same point just so that the figure closes when plotting in something like Excel, so there's really only eight vertices.

Sorted Edges

Edge|V1|V2|y1|Y2|x1|x2
1|8|1|-2.9|2.9|-3|-3.4
2|8|7|-2.9|5.5|-3|-1.5
3|4|5|-2.57|-1.78|1.35|-1.78
4|4|3|-2.57|4.19|1.35|2.15
5|5|6|-1.78|4.75|-1.78|0.25
6|1|2|2.9|6.3|-3.4|-1.2
7|3|2|4.19|6.3|2.15|-1.2
8|6|7|5.75|5.5|0.25|-1.5

Note that only the first two columns (Edge is the index, not a data column) are needed as they can be used as indices into the existing vertex array.

Step 1: Initialize INSIDE = FALSE

Step 2: FOR EACH candidate point:
Step 2.1: Get the <x,y> coordinates Point #N: (We are only interested in Point N=1)
// XSEG = 0.1; YSEG = 4.6

Step 2.2: UNTIL: y-coordinate of the first vertex point in the edge is greater than YSEG (or all edges if Step 0 not performed).
// This condition will mean that we eliminate Edge 8, leaving {1, 2, 3, 4, 5, 6, 7}.

Step 2.2.1: IF the y-coordinate of the second vertex is less than YSEG:
Step 2.2.1.1: Proceed to the next vertex point.
// This condition will eliminate Edges {1, 3, 4}, leaving {2, 5, 6, 7}.

Step 2.2.2: IF the x-coordinates of both the vertices are less than XSEG:
Step 2.2.2.1: Proceed to the next vertex point.
// This condition will eliminate Edges {2, 6}, leaving {5, 7}.

Step 2.2.3: IF the x-coordinates of both the vertex and the following are greater than XSEG:
Step 2.2.3.1 INSIDE = !INSIDE
Step 2.2.3.2 Proceed to the next vertex point.
// This condition doesn't apply to any of the remaining edges.

Step 2.2.4: Find vector along boundary segment: <(x2 - x1), (y2 - y1)>
// Edge 5: <2.03, 6.53>; Edge 7: <-3.35, 2.11>.

Step 2.2.5: Find vector from first vertex to Point N: <(XSEG - x_{N}), (YSEG - y_{N})>
// Edge 5: <1.88, 6.38>; Edge 7: <-2.05, 0.41>.

Step 2.2.6: Find cross product of boundary vector and point vector:
// Edge 5: 0.675; Edge 7: 2.952

Step 2.2.7: IF cross product is greater than zero:
Step 2.2.7.1: INSIDE = !INSIDE
// Both edges are positive, so INSIDE is toggled twice, leaving it FALSE.

Step 2.4: IF INSIDE is TRUE:
Step 2.4.1: Add candidate point to list of points inside the shape.
// This point is NOT inside the shape.

You have too much time in your hands, my friend... tomorrow I'll take a closer look at what you've just posted... although I have no difficulty believing that you've just pointed to yet another flaw in my reasoning.
No worries... only thing to be done here is for me to write the code... then we can test it to your heart's desire.

Thanks for forcing me to learn something

in the meantime, nighty night

 

W... this is a preliminary

This is how the shape in your post #66 looks like:

​

Its is a valid shape, it will most probably pass my reasoning, along with your test points. We'll have to wait and see... The black point in the middle of the graph is coordinate 0,0 btw. The blue points are the candidate points to be analyzed.

I didn't quite get what you were trying to say in post #70 . If things were drawn the way I understand them, they would look like this:

​

Most probably my bad... I do not understand your nomenclature...

In my algorithm, vertexes are not supposed to be sorted, they're supposed to be in a sequential array in the same order in which they're drawn. But it doesn't matter which is the first one, all that matters is that their order is preserved, that it is a closed shape (an edge is formed between the first and last vertex), that only straight lines are being used, and that the edges do not intersect one another. Other than that, the edges no longer play part in my argument.

 

My algorithm doesn't require that the edges be sorted (which is why it is marked as optional). If they are sorted then you increase the efficiency of the algorithm.

I do not understand what is so hard to understand about my algorithm. The basis is very, very, very simple. Starting from the candidate point you proceed outward toward infinity (which merely means far enough to guarantee that you are outside the shape) keeping track of how many times you cross the boundary in doing so. Each time you cross a boundary your status changes from inside to outside or vice-versa. Since you know that you will eventually end up outside the shape, if you cross the boundary an odd number of times you will know that you started out inside the shape while if you cross an even number of times you started out outside the shape. That's all there is to it.

So at it's core you have a line segment that starts at the candidate point and extends to a point outside the shape. You then merely need to test that line segment against every border segment to see if they intersect (within their extents) and count the number of border segments that do. You can test if two line segments cross a number of ways. The most obvious is to determine the equations for the lines that contain them, find the intersection of those lines, and then see if that point is within the extents of both line segments. But this is very computationally expensive. An alternative is to use the vector cross product to determine if the endpoints of each line segment lie on opposite sides of the other segment. This would involve performing four cross product evaluations, each of which involves two multiplications and one addition, plus some final checks to determine the answer.

You then have to perform this check against every border segment. Or do you? If you can determine that some segments either can't intersect or must intersect, then there is no reason to check them further. That is the key to improving the computational efficiency of the algorithm given. Since we can extend our line segment in any direction, we choose to extend it in the positive x-direction. When we consider a border segment, if both of the y-coordinates of the end points are below the candidate point, we know that it cannot cross our line segment. Similarly, if both are above we know that it can't cross. That latter case is the motivation for sorting the border segments according to the smallest y-coordinate of that segment -- as we walk through this array as soon as we encounter a segment whose smallest y-coordinate is bigger than the candidate point, we know that it and all of the segments after it in the list are strictly above the candidate point and therefore can't intersect our horizontal line. These simple and efficient tests will eliminate the majority of border segments from further consideration. At this point we are left with border segments for which we KNOW that the endpoints lie on opposite sides of our horizontal segment. Now, if both of the x-coordinates are less than the x-coordinate of the candidate point we know that it cannot cross the horizontal segment while if both are greater we know that it must (and so we count them). That leaves us with only those segments that have one x-coordinate to the left and one to the right of the candidate point and we must test this case to see if they actually intersect. But we don't need to check all four points because three of the four conditions are already guaranteed to be satisfied -- we only need to check if the candidate point is to the left of the boarder segment and, if it is, then the two segments cross and we have to count it.

 

My algorithm doesn't require that the edges be sorted (which is why it is marked as optional). If they are sorted then you increase the efficiency of the algorithm.

I do not understand what is so hard to understand about my algorithm. The basis is very, very, very simple. Starting from the candidate point you proceed outward toward infinity (which merely means far enough to guarantee that you are outside the shape) keeping track of how many times you cross the boundary in doing so. Each time you cross a boundary your status changes from inside to outside or vice-versa. Since you know that you will eventually end up outside the shape, if you cross the boundary an odd number of times you will know that you started out inside the shape while if you cross an even number of times you started out outside the shape. That's all there is to it.

So at it's core you have a line segment that starts at the candidate point and extends to a point outside the shape. You then merely need to test that line segment against every border segment to see if they intersect (within their extents) and count the number of border segments that do. You can test if two line segments cross a number of ways. The most obvious is to determine the equations for the lines that contain them, find the intersection of those lines, and then see if that point is within the extents of both line segments. But this is very computationally expensive. An alternative is to use the vector cross product to determine if the endpoints of each line segment lie on opposite sides of the other segment. This would involve performing four cross product evaluations, each of which involves two multiplications and one addition, plus some final checks to determine the answer.

You then have to perform this check against every border segment. Or do you? If you can determine that some segments either can't intersect or must intersect, then there is no reason to check them further. That is the key to improving the computational efficiency of the algorithm given. Since we can extend our line segment in any direction, we choose to extend it in the positive x-direction. When we consider a border segment, if both of the y-coordinates of the end points are below the candidate point, we know that it cannot cross our line segment. Similarly, if both are above we know that it can't cross. That latter case is the motivation for sorting the border segments according to the smallest y-coordinate of that segment -- as we walk through this array as soon as we encounter a segment whose smallest y-coordinate is bigger than the candidate point, we know that it and all of the segments after it in the list are strictly above the candidate point and therefore can't intersect our horizontal line. These simple and efficient tests will eliminate the majority of border segments from further consideration. At this point we are left with border segments for which we KNOW that the endpoints lie on opposite sides of our horizontal segment. Now, if both of the x-coordinates are less than the x-coordinate of the candidate point we know that it cannot cross the horizontal segment while if both are greater we know that it must (and so we count them). That leaves us with only those segments that have one x-coordinate to the left and one to the right of the candidate point and we must test this case to see if they actually intersect. But we don't need to check all four points because three of the four conditions are already guaranteed to be satisfied -- we only need to check if the candidate point is to the left of the boarder segment and, if it is, then the two segments cross and we have to count it.

Very, very well explained. I finally understand. Thank you. Gonna mull it for a while, and then I'll get back to you.

 

Ok Bahn,
Here's my understanding of your algorithm.

I've modified one of the vertex in your original figure (vertex #6), so as to make the test meet the extreme condition of having one of the vertices have an equal Y value to the point being evaluated. Also, the algorithm considers a point that lies exactly in an edge or a vertex as being inside the figure.

​

1. Build a database of all the edges in the shape, structured in two X,Y pairs, each pair representing each vertex in the given edge.
2. Discard the edges that meet the following conditions:
   • Both vertices lie at the same vertical level or above the point, That is, both Y values are greater than or equal to the Y value of point in question
   • 
     
   • Both vertices lie below the point. That is, both Y values are less than the Y value of the point in question
   • 
     
   • Both vertices are at the same horizontal level or to the left of the point. That is, both X values are less than or equal to the X value of the point in question. I this case, the figure remains the same as in the previous step.
3. We now calculate the horizontal intersection for each of the remaining edges with the horizontal line traced on the point.
   • 
4. Discard those edges whose X intersection point lies at, or to the left of the point in question.
   • 
5. If what we are left with is an odd number of edges, then the point lies inside the shape. If the remaining number of edges is even, then the point lies outside the shape.

In the last example, we're left with an odd number of edges, and the point lies inside the shape, so the algorithm passes the test.

Now let me explain my hardheadedness on why I insisted on viewing the problem the way I did:
I'm an AutoCAD expert, and the way a complex line shape (they're called polylines) are stored in its database is as a sequence of vertices. For example, the above figure looks like this in AutoCAD's database:

((-1 . <Entity name: 7ef03e08>) (0 . "LWPOLYLINE") (330 . <Entity name: 7ef01cf8>)
(5 . "4E9") (100 . "AcDbEntity") (67 . 0) (410 . "Model") (8 . "0") (100 . "AcDbPolyline")
(90 . 8) (70 . 1) (43 . 0.0) (38 . 0.0) (39 . 0.0) (10 -3.4 2.9) (40 . 0.0) (41 . 0.0)
(42 . 0.0) (91 . 0) (10 -1.2 6.3) (40 . 0.0) (41 . 0.0) (42 . 0.0) (91 . 0) (10 2.15 4.19)
(40 . 0.0) (41 . 0.0) (42 . 0.0) (91 . 0) (10 1.35 -2.57) (40 . 0.0) (41 . 0.0) (42 . 0.0)
(91 . 0) (10 -1.78 -1.78) (40 . 0.0) (41 . 0.0) (42 . 0.0) (91 . 0) (10 0.25 4.75) (40 . 0.0)
(41 . 0.0) (42 . 0.0) (91 . 0) (10 -1.5 5.5) (40 . 0.0) (41 . 0.0) (42 . 0.0) (91 . 0)
(10 -3.0 -2.9) (40 . 0.0) (41 . 0.0) (42 . 0.0) (91 . 0) (210 0.0 0.0 1.0))

This is called DXF code, and it's defined as a list of sublists and dot-separated pairs. For our purpose, the only sublists that matter are those ones whose first element is a 10. These sublists represent the coordinate of each vertex in the shape. In a simplified view, our shape's definition looks like this:

((10 -3.4 2.9) (10 -1.2 6.3) (10 2.15 4.19) (10 1.35 -2.57) (10 -1.78 -1.78)
(10 0.25 4.75) (10 -1.5 5.5) (10 -3.0 -2.9))

You can easily see that all the vertices of your shape are in there.

Now, I normally try to save memory space by working with AutoCAD's database as it is... why would I want to create another list of points representing the shape, when that list is already in AutoCAD's database? All I have to do is retrieve it every time I want to apply some logic process to it.
What hadn't occurred to me, is to actually create my own structured list of edges (instead of vertices) and apply the simple elimination logic process that you mentioned. Your process seems to be far more efficient computationally speaking, but it also uses more memory than mine. In the end, I'd say your process is better anyway, since it would most probably be faster than mine.

I guess that your phrase "If the only tool you own is a hammer, every problem looks suspiciously like a nail." perfectly applies to me in this case...

If you have any more observations, I'd be happy to hear them.

Thanks, it's been fun.

 

Ok Bahn,
Here's my understanding of your algorithm.

I've modified one of the vertex in your original figure (vertex #6), so as to make the test meet the extreme condition of having one of the vertices have an equal Y value to the point being evaluated. Also, the algorithm considers a point that lies exactly in an edge or a vertex as being inside the figure.

Keep in mind that I pointed out, a few times I think, that there are some special cases, such as vertex points that exactly line up either vertically or horizontally, with the candidate point. There's also the case of a candidate point that lies exactly on a boundary segment -- should it be considered inside or outside?

For a vertex that is exactly aligned to the right of a candidate point, you have two boundary segments and you want to count exactly one crossing if one segment goes down and the other segment goes up while you want to count either zero segments or two segments if both segments go down or both segments go up. I think you can accomplish this by carefully choosing how the test conditions deal with equality. If not, then you have to add a special check when this situation arises.

Note that, in your diagram, you don't need to find the intersection of the horizontal line segment with the edges 1-2 or 6-7. Because the x-coordinates of both vertices are to the right of the candidate point, they are guaranteed to intersect the line segment. The only ones that need to be calculated are 2-3 and 4-5.

 

Guess what I found while browsing through some of the programs I wrote almost 20 years ago... I found this LISP routine that I wrote to find if a point lies inside an arc belonging to a polyline in AutoCAD... I'm going to post it there for posterity's sake, and then get back later to see if I can expand on it. Please excuse the comments in spanish:

;determina si un punto pt se encuentra dentro del arco descrito por
;el segmento de polilínea que va del punto a al b, con bulge
;se ha evitado el uso de la función angle deliberadamente, para
;facilitar su posterior traducción a Visual Basic
;el valor de reporte es 'T o nil

(defun c:intarc () ; (a b bulge); / r d arco pc dr rt lf pt fuzz
 (setq

  pt (getpoint "\nPunto a analizar: ")
  e (entget (car (entsel)))

  e (entget (entnext (dxf -1 e)))
  a (dxf 10 e)
  bulge (dxf 42 e)
  e (entget (entnext (dxf -1 e)))
  b (dxf 10 e)

  fuzz 0.000000001
  rt '(0 0 1)   ;vector para obtener offset derecho
  lf '(0 0 -1)  ;vector para obtener offset izquierdo

  d (distance a b)

  ;el valor del radio podría llegar a ser negativo
  r 
   (abs
    (/
     (* d (1+ (expt bulge 2)))
     (* 4.0 bulge)
    ) ; /
   ) ;abs

  arco (* 2.0 (atan (/ d (- (* 2.0 r) (* d (abs bulge))))) (sgn bulge))

  ;corrige la dirección del arco en caso de que éste sea mayor a 180 grados
  arco
   (if (> (abs bulge) 1.0)
    (* (- (* 2.0 pi) (abs arco)) (sgn bulge))
    arco
   ) ;if

  ;dirección del vector indicador al centro, 
  ;a partir del punto medio de la cuerda
  dr (if (> (* (- (abs arco) pi) bulge) 0) 1 -1)

  ;punto central
  pc
   (addvec
    (mid a b)
    (sclvec
     (mulvec (univec a b) (sclvec rt dr))
     (sqrt (- (expt r 2.0) (expt (/ d 2.0) 2.0)))
    ) ;sclvec
   ) ;addvec

 ) ;setq

 (print pc)
 (print r)
 (print arco)
 (princ)

 ;analiza si el punto dado se encuentra dentro del arco
 ;la distancia del punto al centro debe ser igual al radio calculado
 ;la determinante formada por los vectores centro-p1, centro-p2 y centro-punto debe
 ;ser cero para comprobar que se encuentran en el mismo plano

 (if (equal (distance pc pt) r fuzz)
  (progn
   (if (or (equal pt a fuzz) (equal pt b fuzz))
    'T  ;punto=a o punto=b
    (cond
     ;arco de 180 grados
     ((equal arco pi fuzz)
     ) ;(equal arco pi)
     ;arco < 180 grados
     ((< arco pi)
     ) ;(< arco pi)
     ;arco > 180 grados
     ((> arco pi)
     ) ;(> arco pi)
    ) ;cond
   ) ;if (or (equal pt a) (equal pt b))
  ) ;progn
  nil
 ) ;if (equal (distance pc pt) r)

) ;defun

;-----------------------------------------------------------------------------------
;reporta -1 si el numero es negativo y 1 si es positivo
(defun sgn (num)
 (if (< num 0) -1 1)
) ;defun

;-----------------------------------------------------------------------------------
;encuentra el punto medio entre dos puntos
(defun mid (j k)
 (list
  (- (car j) (/ (- (car j) (car k)) 2.0))
  (- (cadr j) (/ (- (cadr j) (cadr k)) 2.0))
  (- (caddr j) (/ (- (caddr j) (caddr k)) 2.0))
 ) ;list
) ;defun

;-----------------------------------------------------------------------------------
;muestra el vector resultante de multiplicar 2 vecores, tomando los datos de 2 líneas
(defun c:mp () ;/ a b v1 v2 v3
 (setq
  a (entget (car (entsel)))
  b (entget (car (entsel)))
  v1 (univec (dxf 10 a) (dxf 11 a))
  v2 (univec (dxf 10 b) (dxf 11 b))
  v3 (mulvec v1 v2)
 ) ;setq

) ;defun