Jim Chen's Blog
0%

Posted on Edited on

The Douglas-Peucker (RDP) algorithm is excellent for simplifying polylines by removing points within a tolerance epsilon. However, standard RDP only guarantees geometric proximity — it doesn’t prevent topological violations like self-intersections, collapsed holes, or accidental crossings between nearby features.

In this post, we’ll explore what topology-preserving simplification means and how to implement it using RhinoCommon.

Read more »

Posted on

Visvalingam-Whyatt is an algorithm similar to Douglas-Peucker algorithm for approximating a list of points (Polyline), but it often produces results that are visually more pleasing because it iteratively removes the “least important” features based on area, rather than distance.

Concept

While RDP removes points based on perpendicular distance to a line segment (ignoring local geometry), Visvalingam-Whyatt (VW) focuses on Effective Area.
The “Effective Area” of a point is defined as the area of the triangle formed by the point and its two immediate neighbors.

  1. Calculate the triangular area for every internal point.
  2. Find the point with the minimum effective area.
  3. Remove that point.
  4. Update the effective areas of the adjacent points (since their neighbors have changed).
  5. Repeat until the desired number of points is left or the minimum area exceeds a tolerance.

Why Determinant?

The area of a triangle with vertices $A=(x_1, y_1)$, $B=(x_2, y_2)$, and $C=(x_3, y_3)$ can be calculated using the determinant of a matrix:

Graphically Meaning

Graphically, this is related to the Cross Product of two vectors. If we form vectors $\vec{AB}$ and $\vec{AC}$, their cross product represents the area of the parallelogram formed by them. The triangle area is exactly half of that parallelogram.

In 2D (or projected on XY plane), this magnitude corresponds to the determinant formula above. Points that form a straight line have an area of 0 (collinear). Points that form a sharp spike have a small area (if the base is narrow). This metric ensures we keep points that contribute significantly to the shape’s overall character.

Implementation with Priority Queue

A naive implementation would scan the entire list to find the minimum area point in every iteration, leading to $O(N^2)$ complexity.
To make this efficient, we can use a Priority Queue.

  • Initialization: Calculate areas for all points and insert them into a Min-Heap (Priority Queue).
  • Loop:
    1. ExtractMin() to get the point with the smallest area ($O(\log N)$).
    2. Mark it as removed.
    3. Recalculate areas for its left and right neighbors.
    4. Update their positions in the Priority Queue ($O(\log N)$).

This reduces the complexity to $O(N \log N)$.

Code

Below is a C# implementation using RhinoCommon. Note that since .NET 6, PriorityQueue<TElement, TPriority> is built-in. For older versions (like Rhino 7/Classic), you might need a custom MinHeap class, but logic remains the same. Here I use SortedSet as a makeshift priority queue for simplicity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
using System;
using System.Collections.Generic;
using Rhino.Geometry;

public Polyline SimplifyVisvalingamWhyatt(Polyline pl, int targetCount)
{
    if (pl.Count <= targetCount || pl.Count < 3) return pl;

    int count = pl.Count;
    var areas = new double[count];
    var left = new int[count];
    var right = new int[count];
    
    // 1. Initialize Linked List structure and Areas
    for (int i = 0; i < count; i++)
    {
        left[i] = i - 1;
        right[i] = i + 1;
        // Endpoints have infinite area (never removed)
        areas[i] = (i == 0 || i == count - 1) ? double.MaxValue : CalculateTriangleArea(pl[i - 1], pl[i], pl[i + 1]);
    }

    // 2. Build Priority Queue
    // SortedSet stores tuples of (Area, Index). It sorts by Area, then Index.
    var minHeap = new SortedSet<(double area, int index)>();
    
    for(int i = 1; i < count - 1; i++)
    {
        minHeap.Add((areas[i], i));
    }

    int removedCount = 0;
    int toRemove = count - targetCount;

    while (removedCount < toRemove && minHeap.Count > 0)
    {
        // 3. Extract Min
        var minItem = minHeap.Min;
        minHeap.Remove(minItem);
        int idx = minItem.index;

        // "Remove" the point by updating neighbors
        int prev = left[idx];
        int next = right[idx];

        if (prev < 0 || next >= count) continue; // Boundary check

        // Update Links
        right[prev] = next;
        left[next] = prev;

        // 4. Update Neighbors in Heap
        // We must remove the old neighbor entries from heap before updating their keys
        if (prev > 0)
        {
            minHeap.Remove((areas[prev], prev));
            areas[prev] = CalculateTriangleArea(pl[left[prev]], pl[prev], pl[next]);
            minHeap.Add((areas[prev], prev));
        }

        if (next < count - 1)
        {
            minHeap.Remove((areas[next], next));
            areas[next] = CalculateTriangleArea(pl[prev], pl[next], pl[right[next]]);
            minHeap.Add((areas[next], next));
        }

        removedCount++;
    }

    // Reconstruct Polyline
    Polyline simplified = new Polyline();
    int current = 0;
    while(current < count && current != -1)
    {
        simplified.Add(pl[current]);
        current = right[current];
        if (current >= count) break;
    }

    return simplified;
}

private double CalculateTriangleArea(Point3d a, Point3d b, Point3d c)
{
    // Cross Product magnitude / 2 (Shoelace Formula equivalent)
    // Area = |(Bx - Ax)(Cy - Ay) - (By - Ay)(Cx - Ax)| / 2
    return 0.5 * Math.Abs((b.X - a.X) * (c.Y - a.Y) - (b.Y - a.Y) * (c.X - a.X));
}

Posted on Edited on

Preface

It’s been a while that I updated my blog, and it’s about time. I spent some time learning Three.js recently. Before this, I only know basic html, css and javascript. Though some people might think that’s totally enough for being a front-end developer in the old days, there’s tons of great tools I needed to catch up with. I think I will catch up through doing some side projects.

To name a few, which at this point, I think I should definitely check them out in near future.

  • TypeScript
  • React
  • Webpack

FrontEnd - Roadmap

By a quick google search,
https://roadmap.sh/frontend

Though I am not sure if I will end up being a front-end developer, I want to put AEC models on web, so it kinda means I have to learn these…
I’ll do my best.

First Person Shooter

https://en.wikipedia.org/wiki/First-person_shooter

Basically, I was following this tutorial.
https://www.youtube.com/watch?v=Q_I0Tq61Ud8&t=744s

So, yeah.

The key ideas is to combine thess two parts.

  • PointerLockContorls
  • wasd control

https://threejs.org/docs/#examples/en/controls/PointerLockControls

PointerLockContorls

1
2
3
4
5
6
7
8
import {
  PointerLockControls
} from "three/examples/jsm/controls/PointerLockControls"

const controls = new PointerLockControls(camera, document.domElement);
window.addEventListener("click", () => {
  controls.lock();
});

wasd contorls

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//前進か後進か変数宣言
let moveForward = false;
let moveBackward = false;
let moveLeft = false;
let moveRight = false;

//移動速度と移動方向の定義
const velocity = new THREE.Vector3();
const direction = new THREE.Vector3();



const onKeyDown = (e) => {
  switch (e.code) {
    case "KeyW":
      moveForward = true;
      console.log(moveForward)
      break;
    case "KeyS":
      moveBackward = true;
      break;
    case "KeyA":
      moveLeft = true;
      break;
    case "KeyD":
      moveRight = true;
      break;
  }
};

const onKeyUp = (e) => {
  switch (e.code) {
    case "KeyW":
      moveForward = false;
      console.log(moveForward)
      break;
    case "KeyS":
      moveBackward = false;
      break;
    case "KeyA":
      moveLeft = false;
      break;
    case "KeyD":
      moveRight = false;
      break;
  }
};


document.addEventListener("keydown", onKeyDown);
document.addEventListener("keyup", onKeyUp);

let prevTime = performance.now();


function animate() {
  requestAnimationFrame(animate);

  const time = performance.now();


  // 前進後進判定
  direction.z = Number(moveForward) - Number(moveBackward);
  direction.x = Number(moveLeft) - Number(moveRight);


  //ポインターがONになったら
  if (controls.isLocked) {
    const delta = (time - prevTime) / 1000;

    // decline
    velocity.z -= velocity.z * 5.0 * delta;
    velocity.x -= velocity.x * 5.0 * delta;

    if (moveForward || moveBackward) {
      velocity.z -= direction.z * 200 * delta;
    }

    if (moveRight || moveLeft) {
      velocity.x -= direction.x * 200 * delta;
    }



    controls.moveForward(-velocity.z * delta);
    controls.moveRight(-velocity.x * delta);
  }
  prevTime = time;
  renderer.render(scene, camera);
}

animate();

Posted on Edited on

Preface

I have absolutely zero idea of the openCV library before watching this tutorial. I hope I can take away some useful knowledge by noting down some code here.

Reference

youtube
github

Reading Image and Video

Read Image

1
2
3
4
5
6
import cv2 as cv

img = cv.imread('../Resources/Photos/cats.jpg')
cv.imshow('Cats', img)

cv.waitKey(0)

Read Video

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
capture = cv.VideoCapture('../Resources/Videos/dog.mp4')

while True:
    isTrue, frame = capture.read()
    
    # if cv.waitKey(20) & 0xFF==ord('d'):
    # This is the preferred way - if `isTrue` is false (the frame could 
    # not be read, or we're at the end of the video), we immediately
    # break from the loop. 
    if isTrue:    
        cv.imshow('Video', frame)
        if cv.waitKey(20) & 0xFF==ord('d'):
            break            
    else:
        break

capture.release()
cv.destroyAllWindows()

Resizing and Rescaling

We often resize and rescale the image to relieve the computational strain.

Drawing Shapes and Putting Texts

5 Essential Function in OpenCV

  • Converting to grayScale
  • Blur
  • Edge Cascade
  • Dilating the image
  • Eroding
  • Resize

Converting to grayScale

1
gray = cv.cvtColor(img, cv.COLOR2GRAY)

Blur

1
blur = cv.GussianBlur(img, (7,7), cv.BORDER_DEFAULT)

Edge Cascade

1
2
canny = cv.Canny(img, 125, 175,)
canny = cv.Canny(cv.GussianBlur(img, (7,7), cv.BORDER_DEFAULT, 125,175) # passing blur image

Dilating the image

1
dilated = cv.dilated(canny, (3,3), iteration=1)

Eroding

1
eroded = cv.erode(dilated, (3,3), iteration=3)

Resize

1
resized = cv.resized(img, (500, 500), interpolation=cv.INTER_CUBIC)

Cropping

1
cropped = img[50:200, 200:400]

Image Transformation

  • Translation
  • Rotation
  • Resizing
  • Flipping
  • Cropping

Contour detection

Posted on Edited on

Preface

In grasshopper, there’s one component called shift_list and basically it did things like Rotate_Array. People can plug in one number and make the list shift/rotate with that number.
Recently, I am trying to catch up some algorithms from Leetcode, and Rotate_Array is one of them.

Example:
Input:
[1,2,3,4,5]
3

Output:
[4,5,1,2,3]

There are obviously some solution for this question. The one I am looking for is the one can acchieve in_place property.

1
2
3
4
5
6
7
8
public:
    void rotate(vector& nums, int k) {
        k %= nums.size();
        reverse(nums.begin(),nums.end());
        reverse(nums.begin(),nums.begin()+k);
        reverse(nums.begin()+k,nums.end());
    }
};

Reference

https://leetcode.com/problems/rotate-array/
https://www.geeksforgeeks.org/array-rotation/
https://leetcode.com/problems/rotate-array/discuss/1729976/C%2B%2B-or-O(N)-or-GCD-or-GCD)

Posted on Edited on

Preface

Happy new year, it’s 2022 now. It’s been a while since the last time I updated my blog. Though I didn’t write something in a quite long period of time, I still check some interesting fellows’ work. There’s an open source project from Arup was released on github, so I decided to give it a look.

Reference

https://github.com/arup-group/Custom-Grasshopper-UI-Components

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
using Grasshopper.Kernel;
using Rhino.Geometry;
using System;
using System.Collections.Generic;

// In order to load the result of this wizard, you will also need to
// add the output bin/ folder of this project to the list of loaded
// folder in Grasshopper.
// You can use the _GrasshopperDeveloperSettings Rhino command for that.

namespace CustomGhComponents
{
    public class ComponentWithDropDown : GH_Component
    {
        /// 
        /// Each implementation of GH_Component must provide a public 
        /// constructor without any arguments.
        /// Category represents the Tab in which the component will appear, 
        /// Subcategory the panel. If you use non-existing tab or panel names, 
        /// new tabs/panels will automatically be created.
        /// 
        public ComponentWithDropDown()
          : base("DropDownComponent", "DropDown",
              "A component with dropdown menus",
              "Category", "Subcategory")
        {
        }

        //This region overrides the typical component layout
        public override void CreateAttributes()
        {
            if (first)
            {
                FunctionToSetSelectedContent(0, 0);
                first = false;
            }
            m_attributes = new CustomUI.DropDownUIAttributes(this, FunctionToSetSelectedContent, dropdowncontents, selections, spacerDescriptionText);
        }

        public void FunctionToSetSelectedContent(int dropdownListId, int selectedItemId)
        {
            // on first run we create the combined dropdown content
            if (dropdowncontents == null)
            {
                // create list to populate dropdown content with
                dropdowncontents = new List>(); //clear all previous content
                selections = new List();

                dropdowncontents.Add(dropdownTopLevelContent); //add Top Level content as first list
                selections.Add(dropdownTopLevelContent[0]);

                dropdowncontents.Add(dropdownLevel2_A_Content); //add level 2 first list as default on first run
                selections.Add(dropdownLevel2_A_Content[0]);

                // add the lists corrosponding to top level content order
                dropdownLevel2_Content.Add(dropdownLevel2_A_Content);
                dropdownLevel2_Content.Add(dropdownLevel2_B_Content);
                dropdownLevel2_Content.Add(dropdownLevel2_C_Content);
                dropdownLevel2_Content.Add(dropdownLevel2_D_Content);
            }

            if (dropdownListId == 0) // if change is made to first list
            {
                // change the content of level 2 based on selection
                dropdowncontents[1] = dropdownLevel2_Content[selectedItemId];

                // update the shown selected to first item in list
                selections[1] = dropdowncontents[1][0];
            }

            if (dropdownListId == 1) // if change is made to second list
            {
                selections[1] = dropdowncontents[1][selectedItemId];

                // do something with the selected item
                System.Windows.Forms.MessageBox.Show("You selected: " + dropdowncontents[1][selectedItemId]);
            }

            // for Grasshopper to redraw the component to get changes to dropdown menu displayed on canvas:
            Params.OnParametersChanged();
            ExpireSolution(true);
        }

        #region dropdownmenu content
        // this region is where (static) lists are created that will be displayed
        // in the dropdown menus dependent on user selection.

        List> dropdowncontents; // list that holds all dropdown contents
        List> dropdownLevel2_Content = new List>(); // list to hold level2 content

        List selections; // list of the selected items 
        bool first = true; // bool to create menu first time the component runs
        
        readonly List spacerDescriptionText = new List(new string[]
        {
            "TopLevel List",
            "Level2 Items"
        });
        readonly List dropdownTopLevelContent = new List(new string[]
        {
            "ListA",
            "ListB",
            "ListC",
            "ListD"
        });
        // lists longer than 10 will automatically get a vertical scroll bar
        readonly List dropdownLevel2_A_Content = new List(new string[]
        {
            "Item A1",
            "Item A2",
            "Item A3",
            "Item A4",
            "Item A5",
            "Item A6",
            "Item A7",
            "Item A8",
            "Item A9",
            "Item A10",
            "Item A11",
            "Item A12",
            "Item A13",
        });

        readonly List dropdownLevel2_B_Content = new List(new string[]
        {
            "Item B1",
            "Item B2",
            "Item B3",
            "Item B4",
            "Item B5",
            "Item B6",
            "Item B7",
            "Item B8",
            "Item B9",
        });

        readonly List dropdownLevel2_C_Content = new List(new string[]
        {
            "Item C1",
            "Item C2",
            "Item C3",
            "Item C4",
            "Item C5",
            "Item C6",
            "Item C7",
            "Item C8",
            "Item C9",
            "Item C10",
            "Item C11",
            "Item C12",
            "Item C13",
            "Item C14",
            "Item C15",
            "Item C16",
        });

        readonly List dropdownLevel2_D_Content = new List(new string[]
        {
            "Item D1",
            "Item D2",
            "Item D3",
            "Item D4",
            "Item D5",
            "Item D6",
        });
        #endregion

        /// 
        /// Registers all the input parameters for this component.
        /// 
        protected override void RegisterInputParams(GH_Component.GH_InputParamManager pManager)
        {
            pManager.AddGenericParameter("Input1", "I1", "First Input", GH_ParamAccess.item);
            pManager[0].Optional = true;
        }

        /// 
        /// Registers all the output parameters for this component.
        /// 
        protected override void RegisterOutputParams(GH_Component.GH_OutputParamManager pManager)
        {
            pManager.AddGenericParameter("Output1", "O1", "First Output", GH_ParamAccess.item);
        }

        /// 
        /// This is the method that actually does the work.
        /// 
        /// The DA object can be used to retrieve data from input parameters and 
        /// to store data in output parameters.
        protected override void SolveInstance(IGH_DataAccess DA)
        {
            // set output to selected
            DA.SetData(0, selections[1]);
        }

        /// 
        /// Provides an Icon for every component that will be visible in the User Interface.
        /// Icons need to be 24x24 pixels.
        /// 
        protected override System.Drawing.Bitmap Icon
        {
            get
            {
                // You can add image files to your project resources and access them like this:
                //return Resources.IconForThisComponent;
                return null;
            }
        }

        /// 
        /// Each component must have a unique Guid to identify it. 
        /// It is vital this Guid doesn't change otherwise old ghx files 
        /// that use the old ID will partially fail during loading.
        /// 
        public override Guid ComponentGuid
        {
            get { return new Guid("020959db-8b03-4a62-9a25-5b34e4e44812"); }
        }
    }
}

Skills

THIS PAGE IS NOT YET FINISHED

Posted on Edited on

Preface

Apparently, we can develop APIs with LISP and .NET . Though I have been checking some articles mentioning the pros and cons for using one another, it is still unclear to me, which scenario suit for which development method. I think I might realize the answer of this question along my development journey. Few weeks ago, I learned some basic LISP, but the materials that I checked wasn’t completed. LISP is the second oldest programming language that still exist, which make the programmer like me a bit hard to catch up easily. Since I spent more time developing in C#, it won’t hurt if I learn a bit how to develop AutoCAD API in .NET framework.

DLLs

  • ACMGD.DLL
  • ACDBGD.DLL
  • ACCOREMGD.DLL

using lines

1
2
3
4
5
using Autodesk.AutoCAD.ApplicationServices;
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.Runtime;
using Autodesk.AutoCAD.Geometry;
using Autodesk.AutoCAD.EditorInput;

Workflow

  1. Create the Class Library(.NET framework)
  2. Add those 3 dlls listed above
  3. Add the using lines
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

using System;
using Autodesk.AutoCAD.ApplicationServices;
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.Runtime;
using Autodesk.AutoCAD.Geometry;
using Autodesk.AutoCAD.EditorInput;

namespace DrawObject{
    public class DrawObject{
        [CommandMethod("DrawLine")]
        public void DrawLine(){
            
        }
    }

}

Reference

https://amdlaboratory.com/amdblog/autocad%E3%81%AEaddin%E3%82%92c%E3%81%A7%E4%BD%9C%E3%82%8B%E6%96%B9%E6%B3%95/

Posted on Edited on

Introduction

A Priority Queue is an extension of a normal Queue. In a standard Queue (FIFO - First In First Out), the “next” item is always the one that arrived earliest. However, in a Priority Queue, the “next” item is the one with the highest priority.

Think of a hospital emergency room:

  • Queue: Patients are treated in the order they walked in.
  • Priority Queue: A patient with a heart attack is treated before someone with a sprained ankle, even if the heart attack patient arrived later.

The Binary Heap

While a Priority Queue is an Abstract Data Type (ADT)—meaning it defines behavior—a Binary Heap is the most common Data Structure used to implement it efficiently.

A Binary Heap is a Binary Tree with two specific properties:

  1. Shape Property: It is a Complete Binary Tree. All levels are fully filled except possibly the last level, which is filled from left to right. This allows us to store it efficiently in an Array.
  2. Heap Property:
    • Min Heap: The value of each node is $\le$ the values of its children. The root is the minimum element.
    • Max Heap: The value of each node is $\ge$ the values of its children. The root is the maximum element.

Array Representation

Because of the “Complete Tree” property, we don’t need point-and-node classes. We can map the tree directly to an index-based array which is cache-friendly.

Given a node at index i:

  • Parent: $\lfloor \frac{i-1}{2} \rfloor$
  • Left Child: $2i + 1$
  • Right Child: $2i + 2$

Core Operations

The magic of the Heap lies in how it maintains the Heap Property efficiently during modification. Operations typically take $O(\log N)$ time, which is the height of the tree.

1. Insert (Push) - “Bubble Up”

When we add a new element:

  1. Place the new element at the end of the array (the first empty spot in the tree).
  2. Compare it with its Parent.
  3. If it violates the heap property (e.g., in a MinHeap, it’s smaller than the parent), swap them.
  4. Repeat step 2-3 until the property is restored or the root is reached.

2. Extract Min/Max (Pop) - “Bubble Down”

When we remove the root (the highest priority item):

  1. Replace the root with the last element in the array.
  2. Remove the last element.
  3. Compare the new root with its Children.
  4. Swap it with the smaller/larger child (depending on Min/Max heap type).
  5. Repeat until the property is restored or a leaf is reached.

Complexity Analysis

Operation Array (Unsorted) Array (Sorted) Binary Heap
Peek (Get Top) $O(N)$ $O(1)$ $O(1)$
Insert $O(1)$ $O(N)$ (shift items) $O(\log N)$
Extract $O(N)$ (find max) $O(N)$ (shift items) $O(\log N)$

The Heap provides the best balance. It’s not as fast as a sorted array for peeking, but insertion and deletion are strictly logarithmic, making it scalable for millions of items.

C# Implementation

Here is a clean implementation of a Min-Heap in C#.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
using System;
using System.Collections.Generic;

public class MinHeap<T> where T : IComparable<T>
{
    private List<T> elements = new List<T>();

    public int Count => elements.Count;

    public void Push(T item)
    {
        elements.Add(item);
        BubbleUp(elements.Count - 1);
    }

    public T Pop()
    {
        if (elements.Count == 0) throw new InvalidOperationException("Heap is empty");
        
        T result = elements[0];
        // Move last item to root
        elements[0] = elements[elements.Count - 1];
        elements.RemoveAt(elements.Count - 1);
        
        if (elements.Count > 0)
            BubbleDown(0);
            
        return result;
    }

    private void BubbleUp(int index)
    {
        while (index > 0)
        {
            int parentIndex = (index - 1) / 2;
            if (elements[index].CompareTo(elements[parentIndex]) >= 0)
                break;

            Swap(index, parentIndex);
            index = parentIndex;
        }
    }

    private void BubbleDown(int index)
    {
        while (true)
        {
            int childIndex = 2 * index + 1;
            if (childIndex >= elements.Count) break;

            // Find smaller child
            int rightChild = childIndex + 1;
            if (rightChild < elements.Count && 
                elements[rightChild].CompareTo(elements[childIndex]) < 0)
            {
                childIndex = rightChild;
            }

            if (elements[index].CompareTo(elements[childIndex]) <= 0)
                break;

            Swap(index, childIndex);
            index = childIndex;
        }
    }

    private void Swap(int i, int j)
    {
        T temp = elements[i];
        elements[i] = elements[j];
        elements[j] = temp;
    }
}

Modern .NET 6+ Note

If you are using .NET 6 or later (which you likely are for modern development), you no longer need to roll your own class! C# now includes a built-in System.Collections.Generic.PriorityQueue<TElement, TPriority>.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Example using built-in .NET 6 PriorityQueue
var pq = new PriorityQueue<string, int>();

pq.Enqueue("Low Priority Task", 10);
pq.Enqueue("Critical Task", 1);
pq.Enqueue("Medium Task", 5);

while (pq.TryDequeue(out string item, out int priority))
{
    Console.WriteLine($"Processing {item} (Priority: {priority})");
}
// Output: 
// Processing Critical Task (Priority: 1)
// Processing Medium Task (Priority: 5)
// Processing Low Priority Task (Priority: 10)

Applications

  1. Graph Algorithms:
    • Dijkstra’s Algorithm: Finds the shortest path in a weighted graph. It always explores the “closest” node next, which is efficiently retrieved using a Min-Heap.
    • Prim’s Algorithm: Used for Minimum Spanning Trees.
  2. Geometry Processing:
    • Visvalingam-Whyatt: As mentioned in my Visvalingam-Whyatt post, we process triangles with the smallest area first.
    • Sweepline Algorithms: Processing events (intersections, start/end points) in order of their X-coordinate.
  3. Systems:
    • Task Scheduling: CPU scheduling processes based on priority levels.

Reference

Posted on Edited on

Reference

  • entsel : prompts the user to select a single object(entity) by specifying a point
  • car
  • cdr
  • entget

entsel

1
(setq en1 (entsel))

If you want to prompt user with a sentence

1
(setq e (entsel "Please choose an object: "))

More about entsel

Return value:

A list whose first element is the entity name of the chosen object and whose second element is the coordinates (in terms of the current UCS) of the point used to pick the object.

The pick point returned by entsel does not represent a point that lies on the selected object.

car

1
(car en1)

In the previos example, (car en1) here will return the first element in the list, which is the EntityName

cadr

1
(cadr en1)

In the previos example, (car en1) here will return the second element in the list, which is the point location

entget

Retrieves an object’s (entity’s) definition data

1
(setq en1_data (entget (car en1)))

If the entity you selected is in the different types, entget may return different geometry infomation.

群碼分析表

Group Codes by Name

If the graph info pair separated by ., (1 . “ABC”) for example, we need to use cdr to retrieve the secend element, instead of cadr

1
(cons 1 "ABC")

can create an dot pair, (1 . “ABC”)

How to revise the data?

  1. entget to get the entity information

  2. assoc to find the correct group_code string pair. The new string pair can be created by cons

  3. subst to swap/change the new/old string pairs

  4. entmod to renew the autocad canvas and show the new string pair

  5. !ent_data

  6. (setq oldr (assoc 40 en1_data))

  7. (setq newr (cons 40 23.8))

  8. (setq en1_data (subst newr oldr en1_data))

  9. (entmod en1_data)

  • entget
  • assoc: Searches an association list for an element and returns that association list entry
  • subst: Searches a list for an old item and returns a copy of the list with a new item substituted in place of every occurrence of the old
  • entmod